SYSTEMS AND METHODS FOR ADAPTIVE LOCAL ALIGNMENT FOR GRAPH GENOMES

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.