A fast bit-vector algorithm for approximate string matching based on dynamic programming

DOI10.1145/316542.316550zbMath1065.68663DBLPjournals/jacm/Myers99OpenAlexW2100751585WikidataQ29030245 ScholiaQ29030245MaRDI QIDQ3158541

Gene Myers

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/316542.316550

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Information storage and retrieval of data (68P20)

Related Items (28)

Approximate pattern matching and transitive closure logics. ⋮ Fast and compact regular expression matching ⋮ Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Approximate string matching with compressed indexes ⋮ Co-linear chaining with overlaps and gap costs ⋮ Practical and flexible pattern matching over Ziv-Lempel compressed text. ⋮ A new filtration method and a hybrid strategy for approximate string matching ⋮ Lossless Seeds for Searching Short Patterns with High Error Rates ⋮ Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment ⋮ Approximate all-pairs suffix/prefix overlaps ⋮ Approximate Boyer-Moore string matching for small alphabets ⋮ From cascade decompositions to bit-vector algorithms. ⋮ DNA-Seq Error Correction Based on Substring Indices ⋮ VECTOR ALGORITHMS FOR APPROXIMATE STRING MATCHING ⋮ Faster approximate string matching for short patterns ⋮ Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching ⋮ NR‐grep: a fast and flexible pattern‐matching tool ⋮ Nested Counters in Bit-Parallel String Matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate string matching on Ziv--Lempel compressed text ⋮ A robust algorithm for identification of proteins in a database ⋮ Indexing text with approximate \(q\)-grams ⋮ Bit-parallel approximate string matching algorithms with transposition ⋮ Practical algorithms for transposition-invariant string-matching ⋮ BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS ⋮ A fast and practical bit-vector algorithm for the longest common subsequence problem

This page was built for publication: A fast bit-vector algorithm for approximate string matching based on dynamic programming