@article {2725, title = {A sublinear algorithm for approximate keyword matching.}, journal = {Algorithmica}, volume = {12}, year = {1994}, month = {1994 Nov}, pages = {345-74}, abstract = {

Given a relatively short query stringW of lengthP, a long subject stringA of lengthN, and a thresholdD, theapproximate keyword search problem is to find all substrings ofA that align withW with not more than D insertions, deletions, and mismatches. In typical applications, such as searching a DNA sequence database, the size of the {\textquotedblleft}database{\textquotedblright}A is much larger than that of the queryW, e.g.,N is on the order of millions or billions andP is a hundred to a thousand. In this paper we present an algorithm that given a precomputedindex of the databaseA, finds rare matches in time that issublinear inN, i.e.,N c for somec\<1. The sequenceA must be overa. finite alphabet σ. More precisely, our algorithm requires 0(DN pow(ɛ)\  logN) expected-time where ɛ=D/P is the maximum number of differences as a percentage of query length, and pow(ɛ) is an increasing and concave function that is 0 when ɛ=0. Thus the algorithm is superior to current O(DN) algorithms when ɛ is small enough to guarantee that pow(ɛ) \< 1. As seen in the paper, this is true for a wide range of ɛ, e.g., ɛ. up to 33\% for DNA sequences ({\textbrokenbar}⌆{\textbrokenbar}=4) and 56\% for proteins sequences ({\textbrokenbar}⌆{\textbrokenbar}=20). In preliminary practical experiments, the approach gives a 50-to 500-fold improvement over previous algorithms for prolems of interest in molecular biology.

}, author = {Myers, Eugene} }