Co-linear chaining with overlaps and gap costs

DOI10.1007/978-3-031-04749-7_15MaRDI QIDQ2170153zbMATH OpenOpenAlexFDO

Authors Chirag Jain, Daniel Gibney, Sharma V. Thankachan

Publication date 30 August 2022

Full work available at URL https://doi.org/10.1007/978-3-031-04749-7_15

zbMATH Keywords

alignmentedit distanceco-linear chaining

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20)

Recommendations

• Multiple genome alignment: chaining algorithms revisited
• Chaining algorithms for multiple genome comparison
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Linear-space algorithms that build local alignments from fragments
• Publication:4886031

Cites work

• scientific article; zbMATH DE number 910858 (Why is no real title available?)
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences
• Algorithms for approximate string matching
• Chaining algorithms for multiple genome comparison
• Computational geometry. Algorithms and applications.
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Sparse dynamic programming I
• Sparse dynamic programming II
• Sparse dynamic programming on DAGs with small width
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

Cited in

(5)

• Multiple genome alignment: chaining algorithms revisited
• Sequence to graph alignment using gap-sensitive co-linear chaining
• Chaining algorithms for multiple genome comparison
• Co-linear chaining on pangenome graphs
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended

Describes a project that uses

Uses Software

• MUMmer4
• CoCoNUT
• lra
• Edlib
• essaMEM
• Winnowing
• Minimap2
• AVID

This page was built for publication: Co-linear chaining with overlaps and gap costs

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