The Complexity of Approximate Pattern Matching on de Bruijn Graphs.

Daniel Gibney Sharma V. Thankachan Srinivas Aluru

Published in: RECOMB (2022)

Keyphrases

approximate pattern matching
graph structure
pattern matching
computational complexity
directed graph
polynomial time complexity
multi dimensional
decision trees
search algorithm
pairwise
high dimensional
probabilistic model
upper bound
np complete
document collections
similarity search