A new filtration method and a hybrid strategy for approximate string matching

DOI10.1016/j.tcs.2013.02.022zbMath1291.68438OpenAlexW4246671164MaRDI QIDQ385045

Chin Lung Lu, Chia Wei Lu, Richard Chia-Tung Lee

Publication date: 29 November 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.02.022

zbMATH Keywords

filtrationapproximate string matchinghybrid\(q\)-gram

Mathematics Subject Classification ID

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

Cites Work

• Very fast and simple approximate string matching
• Approximate string-matching with \(q\)-grams and maximal matches
• Faster approximate string matching
• Sublinear approximate string matching and biological applications
• Bit-parallel witnesses and their applications to approximate string matching
• Fast and practical approximate string matching
• On-line construction of suffix trees
• A fast string searching algorithm
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Finding approximate patterns in strings
• Approximate Boyer–Moore String Matching
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching
• The String-to-String Correction Problem
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Average-optimal single and multiple approximate string matching
• Improving an algorithm for approximate pattern matching