A practical semi-external memory method for approximate pattern matching

DOI10.1016/J.ENTCS.2016.09.010MaRDI QIDQ529654zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Saad Nogueira Nunes, Mauricio Ayala-Rincón

Publication date 19 May 2017

Full work available at URL https://doi.org/10.1016/j.entcs.2016.09.010

zbMATH Keywords

approximate pattern matchingLandau-Vishkin algorithmsemi-external memory methodspace-efficient algorithmstring-matching

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Improving an algorithm for approximate pattern matching
• Fast approximate dictionary matching
• Faster approximate string matching
• Fast and practical approximate string matching
• Faster approximate string matching for short patterns

Cites work

• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• Approximate String Matching: A Simpler Faster Algorithm
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Fast parallel and serial approximate string matching
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Suffix Arrays: A New Method for On-Line String Searches
• The longest common extension problem revisited and applications to approximate string searching
• The theory and computation of evolutionary distances: Pattern recognition
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

Cited in

(2)

• Approximate search of short patterns with high error rates using the 01^ 0 lossless seeds
• A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching

This page was built for publication: A practical semi-external memory method for approximate pattern matching

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