On the Complexity of Sequence-to-Graph Alignment
Chirag Jain, Haowen Zhang, Yu Gao, Srinivas Aluru
Abstract
Availability of extensive genetic data across multiple individuals and populations is driving the growing importance of graph-based reference representations. Aligning sequences to graphs is a fundamental operation on several types of sequence graphs (variation graphs, assembly graphs, pan-genomes, etc.) and their biological applications. Although research on sequence-to-graph alignments is nascent, it can draw from related work on pattern matching in hypertext. In this article, we study sequence-to-graph alignment problems under Hamming and edit distance models, and linear and affine gap penalty functions, for multiple variants of the problem that allow changes in query alone, graph alone, or in both. We prove that when changes are permitted in graphs either standalone or in conjunction with changes in the query, the sequence-to-graph alignment problem is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:math> -complete under both Hamming and edit distance models for alphabets of size ≥2. For the case where only changes to the sequence are permitted, we present an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mstyle mathvariant="bold"> <mml:mi>O</mml:mi> </mml:mstyle> <mml:mrow> <mml:mo class="MathClass-open">(</mml:mo> <mml:mrow> <mml:mo class="MathClass-rel">|</mml:mo> <mml:mi>V</mml:mi> <mml:mo class="MathClass-rel">|</mml:mo> <mml:mo class="MathClass-bin">+</mml:mo> <mml:mi>m</mml:mi> <mml:mo class="MathClass-rel">|</mml:mo> <mml:mi>E</mml:mi> <mml:mo class="MathClass-rel">|</mml:mo> </mml:mrow> <mml:mo class="MathClass-close">)</mml:mo> </mml:mrow> </mml:math> time algorithm, where m denotes the query size, and V and E denote the vertex and edge sets of the graph, respectively. Our result is generalizable to both linear and affine gap penalty functions, and improves upon the runtime complexity of existing algorithms.