Chaining of maximal exact matches in graphs

DOI10.1007/978-3-031-43980-3_29MaRDI QIDQ6545445zbMATH OpenFDO

Authors Nicola Rizzo, Manuel O. Cáceres, Veli Mäkinen

Publication date 29 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-43980-3_29

zbMATH Keywords

longest common subsequencesequence-to-graph alignmentsparse dynamic programming

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Algorithms on strings (68W32)

Recommendations

• Finding maximal exact matches in graphs
• Enumeration of maximal common subsequences between two strings
• Polynomial-delay enumeration of maximal common subsequences
• Directed acyclic subsequence graph -- overview
• Searching subsequences

Cites work

• A linear-time parameterized algorithm for computing the width of a DAG
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 7651116 (Why is no real title available?)
• scientific article; zbMATH DE number 7788491 (Why is no real title available?)
• Linear-time string indexing and analysis in small space
• On the Complexity of String Matching for Graphs
• Parameterized algorithms for string matching to DAGs: funnels and beyond
• Sequence to graph alignment using gap-sensitive co-linear chaining
• Solving string problems on graphs using the labeled direct product
• Sparse dynamic programming on DAGs with small width
• Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time

Cited in

(2)

• Solving string problems on graphs using the labeled direct product
• Finding maximal exact matches in graphs

This page was built for publication: Chaining of maximal exact matches in graphs

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