Prague Stringology Conference 2026
Hamed Hasibi, Mhaskar Neerja and Tieyun Zhang
Faster Indeterminate Pattern Matching Algorithm with Practical Implementations
| Abstract: |
|
In computational biology, sequence analysis is complicated by genetic mutations, polymorphisms, and sequencing ambiguities, making exact string
matching insufficient. Consequently, indeterminate pattern matching–where sequence positions may contain a set of possible characters– a
fundamental tool for identifying conserved biological motifs across degenerate sequences. In this paper, we present a simple and efficient
two-phase solution to the indeterminate pattern matching problem, where both the text t[1..n]$ and
the pattern p[1..m]
contain indeterminate letters. Our approach leverages pattern matching algorithms for partial words, containing holes that match any character,
yielding a solution that runs in O(n log m + |Occdiamondsuit|. min(m,D1+D2))-time, where |Occdiamondsuit|
denotes the number of occurrences of p in t when all indeterminate letters are treated as holes, and D1 and D2
are the numbers of indeterminate
letters in t and p, respectively. This algorithm removes the exponential dependence on alphabet size in the best-known algorithm
of Iliopoulos and Radoszewski 2016 for indeterminate pattern matching over a constant-sized alphabet.
To bridge the gap between our theoretical bounds and practical hardware performance, we expand our two-phase theoretical approach into
a highly efficient three-stage pipeline with the following stages: (I) heuristic candidate generation utilizing solid-letter anchors, (II) solid letter verification of the remaining solid positions, and (III) exact indeterminate letter resolution. We implement and compare three distinct heuristic wildcard matching strategies: a table-driven automaton (Modified SBNDM2), hardware-aware SIMD-accelerated scanning, and segment-based filtering. Through comprehensive experimental evaluation on DNA and protein datasets, we demonstrate that maximizing raw scanning throughput via the SIMD-accelerated approach fundamentally outperforms complex algorithmic filtering, yielding the best end-to-end performance. Finally, we verify the advantage of the heuristic implementations by comparing them with the FFT-based implementation, establishing that all three pipeline variants achieve a significant speedup over traditional convolution methods in biological scenarios. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |