HotCSE Seminar
Computational Science & Engineering
Wednesday Mar 27, 12pm-1pm, Pettit 102A

On the complexity of sequence to graph alignment

Haowen Zhang
Advisor: Prof. Srinivas Aluru


Availability of extensive genetics 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. Though research on sequence to graph alignments is nascent, it can draw from related work on pattern matching in hypertext. In this work, 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 NP-complete under both Hamming and edit distance models for alphabets of size greater than or equal to 2. For the case where only changes to the sequence are permitted, we present an O(|V|+m|E|) 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 run-time complexity of existing algorithms.


Haowen Zhang is a 2nd-year CSE Ph.D. student at Georgia Tech working with Prof. Srinivas Aluru. His current research focuses on designing provably good algorithms for sequencing data analysis and building computational biology tools with good performance in practice.