Systems and methods for use of known alleles in read mapping

Abstract

The invention generally relates to genomic studies and specifically to improved methods for read mapping using identified nucleotides at known locations. The invention provides methods of using identified nucleotides at known places in a genome to guide the analysis of sequence reads from that genome by excluding potential mappings or assemblies that are not congruent with the identified nucleotides. Information about a plurality of SNPs in the subject's genome is used to identify candidate paths through a genomic directed acyclic graph (DAG). Sequence reads are mapped to the candidate paths.

What is claimed is: 
     
       1. 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 human 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 and an object stores a list of pointers specifying one or more locations in the memory where one or more adjacent objects are stored; 
 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 one or more 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 the at least one substantially entire sequence of at least one human chromosome, to identify a nucleotide sequence of at least a portion of the genome. 
 
     
     
       2. The method of  claim 1  wherein mapping the sequence reads comprises aligning the sequence reads to the plurality of candidate paths. 
     
     
       3. The method of  claim 2 , wherein aligning the sequence reads to the plurality of candidate paths comprises determining at least one score for one or more traces through a multi-dimensional matrix. 
     
     
       4. The method of  claim 3 , wherein determining the at least one score for the one or more traces comprises using the computer system to calculate match scores between the sequence reads and the nucleotide sequences represented by at least some of the nodes, and looking backwards to predecessor nodes in the genomic DAG. 
     
     
       5. The method of  claim 1 , further comprising:
 obtaining probabilities for additional SNPs based on the one or more SNPs, wherein the probabilities are obtained from measures of linkage disequilibrium between ones of the additional SNPs and ones of the one or more SNPs; and 
 using the obtained probabilities in mapping the sequence reads to the plurality of candidate paths. 
 
     
     
       6. The method of  claim 1 , wherein the genetic information identifying the one or more SNPs is received as results from a microarray assay. 
     
     
       7. 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 human 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 and an object stores a list of pointers specifying one or more locations in the memory where one or more adjacent objects are stored; 
 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 one or more 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 human chromosome, to identify a nucleotide sequence of at least a portion of the genome. 
 
 
     
     
       8. The system of  claim 7 , wherein each of the plurality of candidate paths defines a path through the genomic DAG. 
     
     
       9. The system of  claim 7 , wherein mapping the sequence reads comprises aligning the sequence reads to the plurality of candidate paths. 
     
     
       10. The system of  claim 9 , wherein aligning the sequence reads to the plurality of candidate paths comprises determining at least one score for one or more traces through a multi-dimensional matrix. 
     
     
       11. The system of  claim 9 , further operable to: obtain probabilities for additional SNPs based on the one or more SNPs; and use the obtained probabilities in aligning the sequence reads to the plurality of candidate paths. 
     
     
       12. The system of  claim 11 , wherein the probabilities are obtained from measures of linkage disequilibrium between ones of the additional SNPs and ones of the one or more SNPs. 
     
     
       13. The system of  claim 7 , wherein each of the plurality of candidate paths defines a path through the genomic DAG and wherein the system is operable to map the sequence reads by aligning the sequence reads to the plurality of candidate paths. 
     
     
       14. The system of  claim 13 , wherein aligning the sequence reads to the plurality of candidate paths comprises determining one or more traces through the genomic DAG by:
 calculating match scores between the sequence reads and the nucleotide sequences represented by at least some of the nodes in the genomic DAG; and 
 dereferencing pointers to read predecessor objects storing prior nodes in the genomic DAG from their referenced locations in the memory, wherein a path through the genomic DAG includes one or more of the prior nodes and the match scores are used in determining the one or more traces. 
 
     
     
       15. 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 human chromosome, the genomic DAG stored in the at least one 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 memory and an object stores a list of pointers specifying one or more locations in the memory where one or more adjacent objects are stored; 
 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 one or more 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. 
 
     
     
       16. The at least one non-transitory computer readable storage device of  claim 15 , wherein filtering paths through the genomic DAG comprises using conditional information to exclude paths in the genomic DAG containing the second node. 
     
     
       17. The at least one non-transitory computer readable storage device of  claim 16 , wherein the conditional information comprises probabilistic information. 
     
     
       18. The at least one non-transitory computer readable storage device of  claim 15 , wherein the instructions further cause the at least one computer system to perform generating a reduced DAG having the plurality of candidate paths, wherein the reduced DAG has fewer nodes than the genomic DAG, and storing the reduced DAG in the at least one computer system. 
     
     
       19. The at least one non-transitory computer readable storage device of  claim 15 , wherein mapping the sequence reads to the plurality of candidate paths further comprises dereferencing at least one pointer to access data stored at one or more locations in the memory associated with the at least one pointer.