Approximate all-pairs suffix/prefix overlaps

DOI10.1016/J.IC.2012.02.002zbMATH Open1254.68361OpenAlexW2062266313MaRDI QIDQ418172FDOQ418172

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

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

zbMATH Keywords

approximate pattern matchingsuffix/prefix matching

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)