Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis

DOI10.1007/978-3-319-89929-9_14OpenAlexW2794525315MaRDI QIDQ5881357

Sharma V. Thankachan, Unnamed Author, S. Chockalingam, Srinivas Aluru

Publication date: 9 March 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-89929-9_14

zbMATH Keywords

approximate sequence matchingheavy pathalgorithmic frameworkaverage common substring (ACS)longest common substring problem

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Related Items

Efficient computation of sequence mappability ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Dynamic and internal longest common substring ⋮ Faster algorithms for 1-mappability of a sequence ⋮ Longest property-preserved common factor: a new string-processing framework ⋮ Longest common substring made fully dynamic

Uses Software

• Soap
• ALFRED
• Bowtie 2
• BWA

Cites Work

• Unnamed Item
• Sequence similarity measures based on bounded Hamming distance
• Approximate all-pairs suffix/prefix overlaps
• A data structure for dynamic trees
• Comparison of alignment free string distances for complete genome phylogeny
• Efficient Alignment Free Sequence Comparison with Bounded Mismatches
• Longest Common Prefix with Mismatches
• Maximal Words in Sequence Comparisons Based on Subword Composition
• Dictionary matching and indexing with errors and don't cares
• A Space-Economical Suffix Tree Construction Algorithm
• A Fast Merging Algorithm
• Algorithms on Strings, Trees and Sequences
• Consequences of Faster Alignment of Sequences
• More Applications of the Polynomial Method to Algorithm Design
• Research in Computational Molecular Biology