Approximate Multiple String Searching by Clustering
Fei Shi, Peter Widmayer · 2010
We are given a nite set S of text strings and a pattern P over some xed alphabet 6. The topic of this paper is the design of a data structure D(S) which supports approximate multiple string searching queries e ciently. Thereby, for a given upper bound k 2 Z + on the allowable distance, P = p 1 111pm is said to appear approximately in a text T = t 1 111tn, m; n 2 Z +, if there exist positions u; v in T such that the edit distance between P and tu 111tv is at most k. Let N denote the sum of the lengths of all strings in S. Wepresent an algorithm that constructs the data structure D(S) in O(N) time and space. Afterwards, an approximate multiple string search query can be answered in O(N) expected-time if the allowable distance k is bounded above by O( m). The method can be used tosearch large log m nucleotide and amino acid sequence databases for similar sequences. 1