The Complexity of Approximate Pattern Matching on De Bruijn Graphs

Daniel Gibney, Sharma V. Thankachan, Srinivas Aluru

Aligning a sequence to a walk in a labeled graph is a problem of fundamental importance to Computational Biology. For finding a walk in an arbitrary graph with $|E|$ edges that exa…