SYSTEMS AND METHODS FOR PROVIDING ASSISTED LOCAL ALIGNMENT

1 . A method of aligning a data sequence to one or more reference sequences represented as a sequence variation graph (SVG), the method comprising the steps of:

receiving one or more alignment candidate regions and corresponding ordered seeding information for seeds in each of the one or more alignment candidate regions, each of the alignment candidate regions representing a subset of the SVG identified based on a query data sequence; and

for each of the received alignment candidate regions:

(i) determining a current seed, the current seed being a next-in-order unprocessed seed based on the ordered seeding information;

(ii) traversing data paths in the alignment candidate region that start after the current seed determined in step (i) to find potential next seeds relative to the current seed;

(iii) if at least one potential next seed is found in step (ii), selecting a next seed from among the potential next seeds, and generating alignment results by applying a local alignment procedure to align (a) query data in portions of the query data sequence located between the current seed and the next seed, and (b) reference data in portions of the alignment candidate region located between the current seed and the next seed;

(iv) if at least one potential next seed is not found in step (ii), generating a concatenated result by concatenating the alignment results and returning the concatenated result as a next alignment; and

(v) if there is at least one unprocessed seed in the alignment candidate region, returning to step (i).

2 . The method of claim 1 , wherein if more than one seed is found in step (ii) during the traversal of the reference graph, the next seed is selected in accordance with one or more priority rules.

3 . The method of claim 2 , wherein the next-in-order unprocessed seed has a highest priority based on the one or more priority rules.

4 . The method of claim 2 , wherein at least one of the one or more priority rules takes into account one or more of the estimated probability of a seed being correctly placed in the SVG and the length of a seed.

5 . The method of claim 4 , wherein seeds having a length shorter than a length threshold and/or having an ambiguous placement determined based on the estimated probability of being correctly placed in the SVG, are excluded from consideration such that they are not considered as current seeds or as potential next seeds.

6 . The method of claim 1 , further comprising scoring the concatenated result.

7 . The method of claim 6 , wherein scoring the concatenated result comprises calculating an edit distance between the concatenated result and the corresponding portions of the alignment candidate region.

8 . The method of claim 1 , wherein the concatenated result is further analyzed for plausibility.

9 . The method of claim 1 , wherein the one or more alignment candidate regions and the ordered seeding information are determined using a global search algorithm.

10 . The method of claim 1 , wherein the local alignment procedure is a graph local alignment.

11 . The method of claim 1 , wherein the query data sequence comprises nucleotide/acid sequences and the reference graph represents reference nucleotide/acid data, such that the applying of the local alignment procedure is performed on the query data sequence and the reference graph.

12 . The method of claim 1 , wherein the method is applied for fuzzy text data matching.

13 . The method of claim 1 , further comprising:

for each of the received alignment candidate regions, determining whether the ordered seeding information corresponds to the 5′-3′ direction of the data sequence.

14 . A system for aligning a data sequence to one or more reference sequences represented as a sequence variation graph (SVG), the system comprising:

at least one processor operable to:

receive one or more alignment candidate regions and corresponding ordered seeding information for seeds in each of the one or more alignment candidate regions, each of the alignment candidate regions representing a subset of the SVG identified based on a query data sequence; and

for each of the received alignment candidate regions:

(i) determine a current seed, the current seed being a next-in-order unprocessed seed based on the ordered seeding information;

(ii) traverse data paths in the alignment candidate region that start after the current seed determined in (i) to find potential next seeds relative to the current seed;

(iii) if at least one potential next seed is found in (ii), select a next seed from among the potential next seeds, and generate alignment results by applying a local alignment procedure to align (a) query data in portions of the query data sequence located between the current seed and the next seed, and (b) reference data in portions of the alignment candidate region located between the current seed and the next seed;

(iv) if at least one potential next seed is not found in (ii), generate a concatenated result by concatenating the alignment results and return the concatenated result as a next alignment; and

(v) if there is at least one unprocessed seed in the alignment candidate region, return to (i).

15 . The system of claim 14 , wherein if more than one seed is found in (ii) during the traversal of the reference graph, the next seed is selected in accordance with one or more priority rules.

16 . The system of claim 15 , wherein the next-in-order unprocessed seed has a highest priority based on the one or more priority rules.

17 . The system of claims 15 , wherein at least one of the one or more priority rules takes into account one or more of the estimated probability of a seed being correctly placed in the SVG and the length of a seed.

18 . The system of claim 17 , wherein seeds having a length shorter than a length threshold and/or having an ambiguous placement determined based on the estimated probability of being correctly placed in the SVG, are excluded from consideration such that they are not considered as current seeds or as potential next seeds.

19 . The system of claim 14 , wherein the processor is further operable to score the concatenated result.

20 . The system of claim 19 , wherein scoring the concatenated result comprises calculating an edit distance between the concatenated result and the corresponding portions of the alignment candidate region.