Systems and methods for adaptive local alignment for graph genomes

Abstract

Systems and methods for analyzing genomic information can include obtaining a sequence read including genetic information; identifying, within a graph representing a reference genome, a plurality of candidate mapping positions that relate to the genetic information, the graph comprising nodes representing genetic sequences and edges connecting pairs of nodes; determining, by means of a computer system, whether an alignment with the graph surrounding each of the plurality of candidate mapping positions is advanced or basic; and performing for each candidate mapping position, by means of the computer system, a local alignment based on whether the local alignment is advanced or basic. The advanced local alignment can include a first-local-alignment algorithm, and the basic local alignment includes a second-local-alignment algorithm. Based on the local alignments, the mapped position of the sequence read can be identified within the genome.

What is claimed is: 
     
         1 . A method, comprising:
 obtaining a sequence read including genetic information;   identifying, within a graph representing a reference genome, a plurality of candidate mapping positions that relate to the genetic information, the graph comprising nodes representing genetic sequences and edges connecting pairs of nodes;   determining, by means of a computer system, whether an alignment with the graph surrounding each of the plurality of candidate mapping positions is advanced or basic;   performing for each candidate mapping position, by means of the computer system, a local alignment based on whether the local alignment is advanced or basic, wherein:
 the advanced local alignment includes a first-local-alignment algorithm, and 
 the basic local alignment includes a second-local-alignment algorithm; and 
   based on the local alignments, identifying an optimal mapped position of the sequence read within the reference genome.   
     
     
         2 . The method of  claim 1 , wherein the first-local-alignment algorithm is different from the second-local-alignment algorithm. 
     
     
         3 . The method of  claim 1 , further comprising determining whether the local alignment is advanced or basic based on at least one of: a length of the graph, a variability of the graph, a total processing time, a remaining processing time, and a number of repeating elements. 
     
     
         4 . The method of  claim 1 , further comprising determining whether the local alignment is advanced or basic based, at least in part, on a complexity of the graph. 
     
     
         5 . The method of  claim 4 , further comprising determining whether the local alignment is advanced or basic based, at least in part, on a complexity of a subset of the graph surrounding each candidate mapping position. 
     
     
         6 . The method of  claim 5 , wherein the local alignment is advanced if the complexity of a subset of the graph surrounding a candidate mapping position is 10 or more nodes. 
     
     
         7 . The method of  claim 5 , wherein the local alignment is basic if the complexity of a subset of the graph surrounding a candidate mapping position is 5 or fewer nodes. 
     
     
         8 . The method of  claim 1 , wherein the second-local-alignment algorithm comprises a pattern matching algorithm. 
     
     
         9 . The method of  claim 8 , wherein the pattern matching algorithm is selected from the group consisting of: a Boyer-Moore algorithm, a Horspool algorithm, and a Tarhio-Ukkonen algorithm. 
     
     
         10 . The method of  claim 1 , wherein performing a basic local alignment comprises:
 linearizing a subset of the graph surrounding each candidate mapping position into a plurality of linear sequences, and   performing a basic local alignment of the sequence read against each of the plurality of linear sequences using the second-local-alignment algorithm.   
     
     
         11 . The method of  claim 10 , wherein linearizing a subset of the graph surrounding each candidate mapping position into a plurality of linear sequences comprises enumerating the number of unique paths through the subset of the graph, and associating a linear sequence with each enumerated path. 
     
     
         12 . The method of  claim 10 , wherein linearizing a subset of the graph surrounding each candidate mapping position into a plurality of linear sequences comprises performing a depth first search of the subset of the graph. 
     
     
         13 . The method of  claim 1 , wherein the first-local-alignment algorithm comprises a graph aware algorithm. 
     
     
         14 . The method of  claim 13 , wherein the graph aware algorithm is a modified Smith Waterman algorithm. 
     
     
         15 . The method of  claim 1 , further comprising ranking each of the candidate mapping positions based on a quality of the local alignment. 
     
     
         16 . The method of  claim 15 , further comprising re-aligning the sequence read using a third-local-alignment algorithm if the quality of the highest ranking local alignment is low. 
     
     
         17 . A system for determining a subject's genetic information, the system comprising:
 a computer system comprising a processor coupled to memory and operable to:
 receive identities of a plurality of nucleotides at known locations on a reference genome; 
 receive sequence reads from a sample from a subject; and 
 map the sequence reads to the reference genome, thereby identifying a corresponding location on the reference genome, the mapping comprising:
 identifying, within a graph representing a reference genome, a plurality of candidate mapping positions that relate to the genetic information, the graph comprising nodes representing genetic sequences and edges connecting pairs of nodes; 
 determining, by means of a computer system, whether an alignment with the graph surrounding each of the identified plurality of candidate mapping positions is advanced or basic; 
 performing for each candidate mapping position, by means of the computer system, a local alignment based on whether the local alignment is advanced or basic, wherein:
 the advanced local alignment includes a first-local-alignment algorithm, and 
 the basic local alignment includes a second-local-alignment algorithm; and 
 
 
 based on the local alignments, identify the mapped position of the sequence read within the reference genome. 
   
     
     
         18 . The system of  claim 17 , wherein the computer system is further operable to determine whether the local alignment is advanced or basic based, at least in part, on a complexity of a subset of the graph surrounding each candidate mapping position. 
     
     
         19 . The system of  claim 17 , wherein the first-local-alignment algorithm comprises a graph aware alignment algorithm, and the second-local-alignment algorithm comprises a linear alignment algorithm. 
     
     
         20 . The system of  claim 17 , wherein performing a basic local alignment comprises:
 linearizing a subset of the graph surrounding each candidate mapping position into a plurality of linear sequences, and   performing a basic local alignment of the sequence read against each of the plurality of linear sequences using the second-local-alignment algorithm.