A fast algorithm for approximate string matching on gene sequences

DOI10.1007/11496656_8MaRDI QIDQ5713571zbMATH OpenOpenAlexFDO

Authors Zheng Liu, Xin Chen, James Borneman, Tao Jiang

Publication date 14 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b137128

Mathematics Subject Classification ID

Approximation algorithms (68W25) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Recommendations

• Approximate string matching with reduced alphabet
• Approximate Boyer-Moore string matching for small alphabets
• Boyer-Moore approach to approximate string matching
• Very fast and simple approximate string matching
• Improved single and multiple approximate string matching

Cited in

(7)

• A randomized numerical aligner (rNA)
• Approximate Boyer-Moore string matching for small alphabets
• On-line string matching in highly similar DNA sequences
• Average complexity of backward \(q\)-gram string matching algorithms
• Efficient privacy-preserving variable-length substring match for genome sequence
• String searching with mismatches using AVX2 and AVX-512 instructions
• Efficient computation of shortest absent words in a genomic sequence

This page was built for publication: A fast algorithm for approximate string matching on gene sequences

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