Approximate all-pairs suffix/prefix overlaps

DOI10.1016/J.IC.2012.02.002MaRDI QIDQ418172zbMATHOpenAlexFDO

Authors Niko Välimäki, Susana Ladra, Veli Mäkinen

Publication date 24 May 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2012.02.002

zbMATH Keywords

approximate pattern matchingsuffix/prefix matching

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Recommendations

• Approximate All-Pairs Suffix/Prefix Overlaps
• Least random suffix/prefix matches in output-sensitive time
• Fast and simple computations using prefix tables under Hamming and edit distance
• scientific article; zbMATH DE number 2087050
• An improved algorithm for the all-pairs suffix-prefix problem

Cites work

• scientific article; zbMATH DE number 176144 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Algorithms on Strings, Trees and Sequences
• An Eulerian path approach to DNA fragment assembly
• Approximate All-Pairs Suffix/Prefix Overlaps
• Bit-parallel witnesses and their applications to approximate string matching
• Combinatorial algorithms for DNA sequence assembly
• Compressed representations of sequences and full-text indexes
• Dictionary matching and indexing with errors and don't cares
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes
• Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem
• Faster filters for approximate string matching
• Indexing compressed text
• Suffix Arrays: A New Method for On-Line String Searches
• The theory and computation of evolutionary distances: Pattern recognition
• Unified View of Backward Backtracking in Short Read Mapping

Cited in

(8)

• Least random suffix/prefix matches in output-sensitive time
• Approximate All-Pairs Suffix/Prefix Overlaps
• Hierarchical overlap graph
• An improved algorithm for the all-pairs suffix-prefix problem
• Fast and simple computations using prefix tables under Hamming and edit distance
• Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads
• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Efficient Construction of Hierarchical Overlap Graphs

Describes a project that uses

Uses Software

• Soap
• Velvet
• BWA

This page was built for publication: Approximate all-pairs suffix/prefix overlaps

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