Comparison of Online Searching Algorithms for IUPAC Nucleotide Sequences
Author:
Open Access
- 29 December 2025
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 19 (1) , 30
Abstract
We consider online pattern matching algorithms for IUPAC nucleotide sequences. We present an experimental comparison of search algorithms while allowing 3% degenerate symbols. In addition, we introduce two new algorithms, one utilizing SIMD instructions for short patterns and another for long patterns. A BNDM variation with 6-grams turned out to be the best general method to search IUPAC sequences.Keywords
This publication has 10 references indexed in Scilit:
- Practical KMP/BM style pattern-matching on indeterminate stringsDiscrete Applied Mathematics, 2025
- Searching long patterns with BNDMSoftware: Practice and Experience, 2024
- Technology beats algorithms (in exact string matching)Software: Practice and Experience, 2017
- The exact online string matching problemACM Computing Surveys, 2013
- Improving practical exact string matchingInformation Processing Letters, 2010
- Alternative Algorithms for Bit-Parallel String Matching2003
- Fast and flexible string matching by combining bit-parallelism and suffix automataACM Journal of Experimental Algorithmics, 2000
- Combinatorial Pattern Matching1998
- Fast string searchingSoftware: Practice and Experience, 1991
- Nomenclature for incompletely specified bases in nucleic acid sequences: rcommendations 1984Nucleic Acids Research, 1985