AStarix: Fast and Optimal Sequence-to-Graph Alignment
Ivanov, P.; Bichsel, B.; Mustafa, H.; Kahles, A.; Rätsch, G.; Vechev, M.
Show abstract
We present an algorithm for the optimal alignment of sequences to genome graphs. It works by phrasing the edit distance minimization task as finding a shortest path on an implicit alignment graph. To find a shortest path, we instantiate the A[*] paradigm with a novel domain-specific heuristic function that accounts for the upcoming subsequence in the query to be aligned, resulting in a provably optimal alignment algorithm called ASO_SCPLOWTARIXC_SCPLOW. Experimental evaluation of ASO_SCPLOWTARIXC_SCPLOW shows that it is 1-2 orders of magnitude faster than state-of-the-art optimal algorithms on the task of aligning Illumina reads to reference genome graphs. Implementations and evaluations are available at https://github.com/eth-sri/astarix.
Matching journals
The top 2 journals account for 50% of the predicted probability mass.