Systems and methods for use of known alleles in read mapping

A method for determining a genomic sequence, the method comprising:

• receiving, at a computer system, genetic information identifying one or more single nucleotide polymorphisms (SNPs) at one or more respective positions in a genome of a subject;
• receiving a plurality of genomic sequences as a genomic directed acyclic graph (DAG) that represents at least two alternative sequences per position at multiple positions and comprises a list of non-compossible node pairs, wherein at least one path through the genomic DAG corresponds to at least one substantially entire sequence of at least one chromosome, the genomic DAG stored in the computer system and comprising a plurality of nodes and edges, the nodes representing nucleotide sequences, and the edges connecting pairs of the nodes, wherein each of the one or more SNPs is represented by at least one node in the genomic DAG, wherein the plurality of nodes and edges is stored as objects in a memory of the computer system;
• identifying a plurality of candidate paths through the genomic DAG that include the one or more SNPs by identifying a node in the list of non-compossible node pairs using one of the plurality of SNPs, identifying a second node paired to the identified node in the list of non-compossible node pairs, and excluding paths containing the second node;
• receiving sequence reads obtained by sequencing a biological sample from the subject;
• and
• mapping the sequence reads to the plurality of candidate paths, including one or more of the at least one path through the genomic DAG corresponding to at least one substantially entire sequence of at least one chromosome, to identify a nucleotide sequence of at least a portion of the genome.

A system for determining a genomic sequence, the system comprising:

• a computer system comprising a processor coupled to memory and operable to:
• receive genetic information identifying one or more single nucleotide polymorphisms (SNPs) at one or more respective positions in a genome of a subject;
• receive a plurality of genomic sequences as a genomic directed acyclic graph (DAG) that represents at least two alternative sequences per position at multiple positions and comprises a list of non-compossible node pairs, wherein at least one path through the genomic DAG corresponds to at least one substantially entire sequence of at least one chromosome, the genomic DAG stored in the computer system and comprising a plurality of nodes and edges, the nodes representing nucleotide sequences, and the edges connecting pairs of the nodes, wherein each of the one or more SNPs is represented by at least one node in the genomic DAG, wherein the plurality of nodes and edges is stored as objects in the memory;
• identify a plurality of candidate paths through the genomic DAG that include the one or more SNPs by identifying a node in the list of non-compossible node pairs using one of the plurality of SNPs, identifying a second node paired to the identified node in the list of non-compossible node pairs, and excluding paths containing the second node;
• receive sequence reads obtained by sequencing a biological sample from the subject;
• and
• map the sequence reads to the plurality of candidate paths, including one or more of the at least one path through the genomic DAG corresponding to at least one substantially entire sequence of at least one chromosome, to identify a nucleotide sequence of at least a portion of the genome.

At least one non-transitory computer readable storage device storing instructions that, when executed, cause at least one computer system to perform:

• receive genetic information identifying one or more single nucleotide polymorphisms (SNPs) at one or more respective positions in a genome of a subject;
• receive a plurality of genomic sequences as a genomic directed acyclic graph (DAG) that represents at least two alternative sequences per position at multiple positions and comprises a list of non-compossible node pairs, wherein at least one path through the genomic DAG corresponds to at least one substantially entire sequence of at least one chromosome, the genomic DAG stored in the computer system and comprising a plurality of nodes and edges, the nodes representing nucleotide sequences, and the edges connecting pairs of the nodes, wherein each of the one or more SNPs is represented by at least one node in the genomic DAG, wherein the plurality of nodes and edges is stored as objects in the memory;
• identify a plurality of candidate paths through the genomic DAG that include the one or more SNPs by identifying a node in the list of non-compossible node pairs using one of the plurality of SNPs, identifying a second node paired to the identified node in the list of non-compossible node pairs, and excluding paths containing the second node;
• receive sequence reads obtained by sequencing a biological sample from the subject;
• and
• map the sequence reads to the plurality of candidate paths, including one or more of the at least one path through the genomic DAG corresponding to at least one substantially entire sequence of at least one chromosome, to identify a nucleotide sequence of at least a portion of the genome.