Sublinear Expected Time Approximate String Matching and Biological Applications
Chang, William I.
Lawler, Eugene L.
Technical Report Identifier: CSD-91-654
Abstract: The k differences approximate string matching problem specifies a text string of length n, a pattern string of length m, the number k of differences (substitutions, insertions, deletions) allowed in a match, and asks for all locations in the text where a match occurs. We treat k not as a constant but as a fraction of m (not necessarily constant-fraction). Previous algorithms require at least O(kn) time (or else exponential space). We are interested in much faster algorithms for restricted cases of the problem, such as when the text string is random and the allowable error rate is not too high (log-fraction). We have devised an algorithm that is sublinear time O(n/m)k logb m) on the average, when k is bounded by the threshold m / (logb m + O(1)). In particular, when k = o(m / logb m) the expected running time is o(n). In the worst case, our algorithm is O(kn), but still an improvement in that it is practical and uses O(m) space compared to O(n) or O(msquared). We define three problems inspired by molecular biology and describe efficient algorithms based on our techniques: (1) approximate substring matching; (2) approximate-overlap detection; and (3) approximate codon transcription. Respectively, applications to genetics are local similarity search; sequence assembly; and DNA-protein matching.