The complexity of approximate pattern matching on de Bruijn graphs

DOI10.1007/978-3-031-04749-7_16MaRDI QIDQ2170154zbMATH OpenOpenAlexFDO

Authors Daniel Gibney, Sharma V. Thankachan, Srinivas Aluru

Publication date 30 August 2022

Full work available at URL https://arxiv.org/abs/2201.12454

zbMATH Keywords

approximate pattern matchingcomputational complexityde Bruijn graphssequence alignment

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Developmental biology, pattern formation (92C15) Protein sequences, DNA sequences (92D20)

Abstract: 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 exactly matches a pattern of length $m$, a lower bound based on the Strong Exponential Time Hypothesis (SETH) implies an algorithm significantly faster than $O(|E|m)$ time is unlikely [Equi et al., ICALP 2019]. However, for many special graphs, such as de Bruijn graphs, the problem can be solved in linear time [Bowe et al., WABI 2012]. For approximate matching, the picture is more complex. When edits (substitutions, insertions, and deletions) are only allowed to the pattern, or when the graph is acyclic, the problem is again solvable in $O(|E|m)$ time. When edits are allowed to arbitrary cyclic graphs, the problem becomes NP-complete, even on binary alphabets [Jain et al., RECOMB 2019]. These results hold even when edits are restricted to only substitutions. The complexity of approximate pattern matching on de Bruijn graphs remained open. We investigate this problem and show that the properties that make de Bruijn graphs amenable to efficient exact pattern matching do not extend to approximate matching, even when restricted to the substitutions only case with alphabet size four. We prove that determining the existence of a matching walk in a de Bruijn graph is NP-complete when substitutions are allowed to the graph. In addition, we demonstrate that an algorithm significantly faster than $O(|E|m)$ is unlikely for de Bruijn graphs in the case where only substitutions are allowed to the pattern. This stands in contrast to pattern-to-text matching where exact matching is solvable in linear time, like on de Bruijn graphs, but approximate matching under substitutions is solvable in subquadratic $O(nsqrtm)$ time, where $n$ is the text's length [Abrahamson, SIAM J. Computing 1987].

Recommendations

• Complexity issues of string to graph approximate matching
• On the complexity of approximately matching a string to a directed graph
• On the complexity of sequence to graph alignment
• On the Sound Covering Cycle Problem in Paired de Bruijn Graphs
• scientific article; zbMATH DE number 2044948

Cites work

• Complexity issues of string to graph approximate matching
• Dynamic alignment-free and reference-free read compression
• Generalized String Matching
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Improved approximate pattern matching on hypertext
• On the complexity of sequence to graph alignment
• On the complexity of string matching for graphs
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Pattern Matching in Hypertext
• Scaling metagenome sequence assembly with probabilistic de Bruijn graphs
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Subtree isomorphism revisited
• The complexity of approximate pattern matching on de Bruijn graphs
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(7)

• On the complexity of approximately matching a string to a directed graph
• The complexity of approximate pattern matching on de Bruijn graphs
• Edge minimization in de Bruijn graphs
• On the complexity of string matching for graphs
• On the Complexity of String Matching for Graphs
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• Complexity issues of string to graph approximate matching

Describes a project that uses

Uses Software

• BlastGraph
• deBGA
• BrownieAligner
• IDBA-Tran
• IDBA
• DARRC
• Velvet
• MEGAHIT

This page was built for publication: The complexity of approximate pattern matching on de Bruijn graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170154)