Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance

We develop efficient dynamic programming algorithms for pattern matching with general gaps and character classes. We consider patterns of the form p ₀ g(a ₀,b ₀)p ₁ g(a ₁,b ₁)…p _m−1, where p _i ⊂ Σ, Σ is some finite alphabet, and g(a _i ,b _i ) denotes a gap of length a _i …b _i between symbols p _i and p _i+1. The text symbol t _j matches p _i iff t _j  ∈ p _i . Moreover, we require that if p _i matches t _j , then p _i+1 should match one of the text symbols \( t_{j+a_i+1} \ldots t_{j+b_i+1}.\) Either or both of a _i and b _i can be negative. We also consider transposition invariant matching, i.e., the matching condition becomes t _j  ∈ p _i + τ, for some constant τ determined by the algorithms. We give algorithms that have efficient average and worst case running times. The algorithms have important applications in music information retrieval and computational biology. We give experimental results showing that the algorithms work well in practice.