Efficient Bit-Parallel Algorithms for (δ,α)-Matching

Abstract

We consider the following string matching problem. Pattern p ₀ p ₁ p ₂ ... p _{m − − 1} (δ,α)-matches the text substring $t_{i_0} t_{i_1} t_{i_2} \ldots t_{i_{m-1}}$, if $|p_j-t_{i_j}|\leq\delta$ for j ∈ {0,..., m–1}, where 0 < i _j + 1 – i _j ≤ α + 1. The task is then to find all text positions i _{m − − 1} that (δ,α)-match the pattern. For a text of length n, the best previously known algorithms for this string matching problem run in time O(nm) and in time O(n⌈mα/w⌉), where the former is based on dynamic programming, and the latter on bit-parallelism with w bits in computer word (32 or 64 typically). We improve these to take O(nδ + ⌈n/w⌉m) and O(n ⌈m log(α)/w⌉), respectively, worst case time using bit-parallelism. On average the algorithms run in O(⌈n/w⌉⌈αδ/σ⌉ + n)and O(n) time. Our experimental results show that the algorithms work extremely well in practice. Our algorithms handle general gaps as well, having important applications in computational biology.