The complexity of approximate pattern matching on de Bruijn graphs
From MaRDI portal
Publication:2170154
DOI10.1007/978-3-031-04749-7_16zbMath1494.92086arXiv2201.12454OpenAlexW4285294379MaRDI QIDQ2170154
Sharma V. Thankachan, Srinivas Aluru, Daniel Gibney
Publication date: 30 August 2022
Full work available at URL: https://arxiv.org/abs/2201.12454
Protein sequences, DNA sequences (92D20) Developmental biology, pattern formation (92C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
The complexity of approximate pattern matching on de Bruijn graphs ⋮ On the Complexity of String Matching for Graphs ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs
Uses Software
Cites Work
- Unnamed Item
- Complexity issues of string to graph approximate matching
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Improved approximate pattern matching on hypertext
- Wheeler graphs: a framework for BWT-based data structures
- Dynamic alignment-free and reference-free read compression
- Space efficient merging of de Bruijn graphs and Wheeler graphs
- The complexity of approximate pattern matching on de Bruijn graphs
- On the complexity of sequence to graph alignment
- Generalized String Matching
- Subtree Isomorphism Revisited
- Scaling metagenome sequence assembly with probabilistic de Bruijn graphs
- Pattern Matching in Hypertext
- On the Hardness and Inapproximability of Recognizing Wheeler Graphs
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
This page was built for publication: The complexity of approximate pattern matching on de Bruijn graphs
