An Eﬃcient Algorithm for Finding Similar Short
Substrings from Large Scale String Data
Takeaki Uno
uno@nii.jp, National Institute of Informatics
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan

Abstract. Finding similar substrings/substructures is a central task inanalyzing huge amounts of string data such as genome sequences, web
documents, log data, etc. In the sense of complexity theory, the existenceof polynomial time algorithms for such problems is usually trivial since
the number of substrings is bounded by the square of their lengths. However, straightforward algorithms do not work for practical huge databases
because of their computation time of high degree order. This paper addresses the problems of ﬁnding pairs of strings with small Hamming
distances from huge databases composed of short strings. By solving the
problem for all the substrings of ﬁxed length, we can eﬃciently ﬁnd candidates of similar non-short substrings. We focus on the practical eﬃciencyof algorithms, and propose an algorithm running in almost linear time ofthe database size. We prove that the computation time of its variant isbounded by linear of the database size when the length of short strings
to be found is constant. Slight modiﬁcations of the algorithm adapt tothe edit distance and mismatch tolerance computation. Computational
experiments for genome sequences show the eﬃciency of the algorithm.
An implementation is available at the author’s homepage1

1

Introduction

These days we have many huge string data such as genome sequences, web documents, log data, etc. Since the size of data is so huge that human cannot grasp
them intuitively, they must be computationally analyzed. Finding similar substrings or similar substructures is an important way of analyzing the data. The
similarity and distribution of substrings makes it possible to grasp the global or
local structures. The number of substrings in a string is at most the square of
the string length. Thus, if the distance between two substrings can be computedin polynomial time, similar substrings can be found in polynomial time by comparing all substrings one by one. However, polynomial time algorithms of highdegree do not work for huge data, therefore practical fast algorithms are needed.
In the area of algorithms and computation, the problem of ﬁnding similar
strings has been widely studied. The problem is usually formulated that for two
given strings Q and S, ﬁnd all substrings of S similar to Q. This formulation canbe considered as a generalization of string matching problems. When Hamming1

http://research.nii.ac.jp/˜uno/index.html

distance is chosen as a similarity measure, a straightforward algorithm solves the
problem in O(|S||Q|) time, thus a research goal is to reduce this time complexity.
Here the length of S and Q is denoted by |S| and |Q|.
For the problem of ﬁnding substrings of S with the shortest Hamming distance to Q, Abrahamson[1] proposed an algorithm running in O(|S|(|Q| log |Q|)1/2 )time. If the maximum Hamming distance is k, the computation time can be reduced to O(|S|(k log k)1/2 )[4]. Some approximation approaches have been also
developed. The Hamming distance of two strings of length l within (1−ϵ) and (1+ϵ) approximation ratio with probability δ can be computed in O(log l log(1/δ)/ϵ)time [6]. For edit distance, which allows insertions and deletions, algorithms proposed by Muthukrishnan and Sahinalp[8, 9] approximate the minimum distancesubstring. Using these algorithms, the problem can be solved in shorter time but
may fail with some solutions. These algorithms take more than O(|S|2 ) time toﬁnd similar substrings even for ﬁxed length strings, Thus direct application ofthese algorithms does not work in practice.
On the other hand, there are several studies for eﬃcient data structures toﬁnd similar substrings. The problem is formulated such that, for a given string
S, construct a data structure of not a large size such that for any query stringQ, substrings of S similar to Q can be found in short time. For the problem
of ﬁnding substring of S equal to Q, there are many eﬃcient data structures
such as suﬃx array which make it possible to ﬁnd all such substrings in almost
O(|Q|) time. However, allowing the errors makes the problem diﬃcult. Existingalgorithms basically need θ(|S|) time in the worst case. This diﬃculty can beobserved in many other similarity search problems, such as inner product ofvectors, points in Euclidean space, texts and documents. Motivated by practicaluse, there have been many studies on approximation and heuristic approaches.
Yamada and Morishita [12] proposed an algorithm for computing a lower
bound of the shortest Hamming distance from Q to a substring in S. The algorithm constructs a data structure in O(|S| log |S|) time, then answers a lower
bound in O(|Q|L) time for any Q, where L is a constant no greater than |Q|.
They also proposed an eﬃcient exact algorithm for strings with small alphabet
such as genome sequences[13].
In bioinformatics area, the problem of ﬁnding substrings of two strings which
are similar to each other is called homology search, and has been widely studied. Because of the huge size of genome sequences, developing exact algorithms
running in short time is diﬃcult thus many heuristic algorithms have been proposed. BLAST and FASTA[2, 3, 10] are widely used among these algorithms.
The idea of BLAST is to ﬁnd short substrings of S and Q that are equal andcheck whether there are similar substrings including them. This idea is based on
the observation that two similar substrings may have common short substrings.
Actually, if the Hamming distance between two strings is no more than 9% of
their length, they always have common string of 10 letters. The disadvantage ofthis method is that when the strings are long, huge number of substrings are thesame, thus a lot of comparisons must be made. Such frequently appearing strings
can be considered as a kind of noise in practice, thus heuristic methods ignorethese strings in the interest of practical eﬃciency. Another method of solving
the problem is to partition Q and S into many blocks[11]. Some statistics of theblocks are computed, for example the number of each letter in the blocks, which
for pruning blocks will never be similar. Then a dynamic programming connects
the blocks and produces candidates of long similar substrings. The idea is thatlong similar substrings are expected to be not so many.
In this paper, we focus on Hamming distance. For given a set S of strings ofthe same length l, our problem is to enumerate all pairs of similar strings in S. We
consider the case in which the length l is small, and propose a practically eﬃcientalgorithm. The idea of the algorithm is to classify the strings in several ways sothat any two similar strings are in the same group for at least one classiﬁcation.
Only strings in the same group have to be compared, which reduces the cost of
the comparison. Each string is partitioned into k blocks, then any two strings
with Hamming distance at most d share at least k − d blocks. Thus they arein the same group at least one classiﬁcation based on combinations of k − d ofthese blocks. By setting k to l, the Hamming distance of any two strings in thesame
is at most d. Using this fact, the time complexity is bounded by∑groupd
O(( i=0 l Ci ) × (|S| + dN )) = O(2l (|S| + dN )), where N is the number of pairs
to be output. Computational experiments show its practical eﬃciency.
Using the algorithm makes it possible to approach the problem of ﬁnding
similar non-short substrings. We can observe that two non-short similar strings
may have several short substrings with short Hamming distance. Thus, pairs of
substrings including several such strings are candidates for similar substrings.
This approach has a certain accuracy. For example, any two strings of 3,000
letters with Hamming distance of at most 290 includes at least three substringsof 30 letters with Hamming distance of at most two. Similar observation can bemade for edit distance. We propose an algorithm for ﬁnding representative pairsof non-short substrings including certain similar short substrings. We compared
the human genome and mouse genome by our algorithm. The computation isdone in quite short time and we could see the homology structure ﬁgured out
by the comparison.

2

Preliminary

Let Σ be an alphabet of letters, and a string be a sequence of letters. The lengthof a string S is the number of letters in S and is denoted by |S|. A sequence
composed of no letter is also a string and is called an empty string. The lengthof an empty string is 0. The ith letter of a string S is written S[i], and i is called
the position of S[i]. The substring of S starting from the ith letter and ending at
the jth letter is denoted by S[i, j]. For example, when string S is ABCDEF G,
S[3] = C, and S[4, 6] = DEF . When j < i, we deﬁne S[i, j] by the empty string.
For two strings S1 and S2 , the concatenation of S2 to S1 is a string S given
by concatenating S2 to S1 , i.e., |S| = |S1 | + |S2 |, S[i] = S1 [i] if i ≤ |S1 |, andS2 [i − |S1 |] otherwise. The concatenation of S2 to S1 is denoted by S1 · S2 .

For two strings S1 and S2 of the same length, the Hamming distance of S1and S2 is deﬁned by the number of positions i satisfying that S1 [i] ̸= S2 [i]. The
Hamming distance is denoted by HamDist(S1 , S2 ). Such letters are called themismatch of S1 and S2 , and the positions of mismatches are called mismatch
positions of S1 and S2 . For string S and integers i and k, i ≤ k, we denote thesubstring of S starting from (⌈|S|(i − 1)/k⌉ + 1)th letter to (⌈|S|i/k⌉)th letter,i.e., S[⌈|S|(i − 1)/k⌉ + 1, ⌈|S|i/k⌉], by B(S, k, i). B(S, k, i) is called the ith block.
For a string S, the deletion of the position i is a string given by S[1, i −1] · S[i + 1, |S|]. The insertion of letter a to S at position i is a string given
by S[1, i − 1] · A · S[i, |S|] where A is the string composed of one letter a. Thechange of position i of S to a is a string given by S[1, i − 1] · A · S[i + 1, |S|]. For
two strings S1 and S2 , the edit distance of S1 and S2 is the smallest number of
combinations of insertion, deletion and change needed to transform S1 to S2 .
The problem we address in this paper is formulated as follows. Let S be amulti set of strings of the same length. S is allowed to include more than one
same string, and every string has an ID to be distinguished from the others. The
problem is formulated as follows.
Short Hamming Distance String Pair Enumeration Problem
Input: A multi set S of strings of ﬁxed length l, threshold value d
Output: All pairs of strings S1 and S2 such that HamDist(S1 , S2 ) ≤ d.
Hereafter we ﬁx the input set S of strings of length l and a threshold value d.

3

Multi-Classiﬁcation Algorithm

The basic idea of the algorithm is to classify the strings in several ways sothat any two similar strings are in the same group at least once. Let C(k, j)
be the set of j distinct integers taken from 1, . . . , k. For example, C(4, 2) ={{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}. For a string S and a set C = {i1 , ..., ik−d },ij < ij+1 taken from C(k, k − d), we deﬁne Sig(S, C) = B(S, k, i1 ) · B(S, k, i2 ) ·. . . · B(S, k, ik−d ). We suppose that an integer k, d < k ≤ l is chosen, and have alook at the following property.
Lemma 1. If HamDist(S1 , S2 ) ≤ d, at least one C ∈ C(k, k − d) satisfies
Sig(S1 , C) = Sig(S2 , C).
Proof. The statement is obvious from the pigeonhole principle. Suppose that
HamDist(S1 , S2 ) ≤ d. Observe that if B(S1 , k, j) ̸= B(S2 , k, j) holds, it includes
at least one mismatch, i.e., S1 [i] ̸= S2 [i] holds for some i, ⌈|S|(i − 1)/k⌉ + 1 ≤ i ≤⌈|S|i/k⌉. Since S1 and S2 have at most d mismatches, at most d integers j satisfy
B(S1 , k, j) ̸= B(S2 , k, j), thereby at least k − d integers h satisfy B(S1 , k, h) =B(S2 , k, h). Setting C to the set of those integers h satisfying B(S1 , k, h) =B(S2 , k, h) shows that Sig(S1 , C) = Sig(S2 , C).
⊓⊔.

AB CD EF
CD AB EF
AB CC EF
FF CC EF
AB CD AA
FF CD EACC AB FFAB CD EAFF CD EF

AB CC EF
AB CD AAAB CD EAAB CD EFCC AB FF
CD AB EF
FF CC EF
FF CD EAFF CD EAAB CD AAAB CD EAAB CC EF
AB CD EFCC AB FF
CD AB EF
FF CC EF
FF CD EAFF CD EACC AB FF
CD AB EF
AB CC EF
FF CC EF
AB CD AAAB CD EAFF CD EAFF CD EAAB CD EFABCCEF & ABCDEFFFCDEA & FFCDEAABCDAA & ABCDEAABCDEA & ABCDEF
Fig. 1. Example of multi-classiﬁcation
withHamming distance of at
FFCDEA & FFCDEAfor ﬁnding strings
FFCDEA& FFCDEA

most one, by dividing strings in three blocks and classifying them by two blocks.

This lemma motivates us to restrict the comparison to those pairs of strings
satisfying the condition of the lemma. To eﬃciently ﬁnd these pairs, we focus on
the combinations of integers. For each C ∈ C(k, k − d), we classify the strings S
in S according to Sig(S, C) so that two strings S1 and S2 satisfy Sig(S1 , C) =Sig(S2 , C) if and only if they are in the same group. In Fig. 1, we show an
example of this method, which we call the multi-classification method. In theexample, there are nine strings and set d = 1 and k = 3. Each block is composedof two letters, and classiﬁcations by two blocks are done three times. For eachclassiﬁcation there are several groups represented by rectangles with more than
one strings, and some of them contain strings with Hamming distance of at mostone, written at the head of the arrows.
ALGORITHM MultiClassiﬁcation Basic (S:set of strings of length l, d)
1. choose k from d + 1, . . . , l
2. for each C ∈ C(k, k − d) do
3. classify all strings S ∈ S by Sig(S, C)
4. for each group K of the classiﬁcation
output all pairs S1 and S2 in K satisfying HamDist(S1 , S2 ) ≤ d
6. end for
The classiﬁcation for C is done by sorting Sig(S, C) in O(l(k − d)/k × |S|)
time by a radix sort. We compute the probability that two randomly chosen
letters from strings of S are the same, and choose k such that the expected sizeof each group in a classiﬁcation is less than 1. Then the comparisons for a groupis not so many, and the bulk of the computation time is for radix sort. Sincel(k − d)/k is expected to be relatively small when l is small, it can be expectedthat the practical performance of the algorithm will be high.
3.1

Reducing the Cost for Radix Sort

Here we present a way to reduce the total computation time for radix sort byunifying the sort of the preﬁx of Sig. Suppose that we repeatedly and recursively
add integers one by one to construct C ∈ C(k, k − d) like a backtrack algorithm.

Then, after choosing i in some iteration of the backtracking, B(S, k, i) is common
to all C generated in the recursive call, i.e., until i is removed. Thus, the radix
sort for B(S, k, i) can be done at the iteration and the result can be used in therecursive calls. As a result, the computation time for each radix sort is reducedto O(l/k × |S|). We describe the algorithm in the next subsection.
3.2

Avoiding Duplication without Memory

The multi-classiﬁcation described above may output duplicates, i.e., output one
pair of strings many times. For example, in Fig. 1, the pair FFCDEA andFFCDEA is output three times. A way to avoid such duplication is to store
all the pairs found in memory and check the duplication when a new pair isfound. Although this is simple, it requires a lot of memory. Here, we present a
method that does not store found pairs and thus requires no extra memory.
A pair of strings S1 and S2 is output more than once if B(S1 , k, i) = B(S2 , k, i)holds more than k − d integers i. Then, Sig(S1 , C) = Sig(S2 , C) holds formany C’s. For given S1 and S2 , let C ∗ (S1 , S2 ) be the lexicographically minimum one among {C ′ |C ′ ∈ C(k, k − d), Sig(S1 , C ′ ) = Sig(S2 , C ′ )}. Our idea
is to output an S1 and S2 pair only when the current operating C is equal toC ∗ (S1 , S2 ). Since, C ∗ (S1 , S2 ) is the collection of the k − d smallest i’s satisfying
B(S1 , k, i) = Sig(S2 , k, i), the computation is not a heavy task. The algorithm
is the following which requires an initial call with S, d and k, and set C = ∅.
ALGORITHM MultiClassiﬁcation (S:set of strings of length l, d, k, C)
1. if |C| = k − d then output all pairs S1 and S2 in K
satisfying HamDist(S1 , S2 ) ≤ d and C = C ∗ (S1 , S2 ) ; return
2. for each i in c + 1, . . . , (k − d) + (c − |C|) do (c = the maximum integer in C)
3. do a radix sort to classify all strings S ∈ S according to B(S, k, i)
4. for each group K of the classiﬁcation with |K| > 1
call MultiClassiﬁcation (K, d, k, C ∪ {i})5. end for
Theorem 1. The computation time of algorithm MultiClassification except forstep 1 is bounded by O(l/k × |S| ×l Cd ).
3.3

A Fixed Parameter Tractable Algorithm

The time complexity of the algorithm presented in the previous subsection isstill O(|S|2 ) since the bottle neck of the computation is actually step 1. For
example, if all strings in S are the same, HamDist(S1 , S2 ) must be computed
l Cd times for every S1 and S2 pair in S, thereby the total computation time isO(l|S|(|S| +l Cd )). Here we will save the computation time in step 1.
Let k = l. Then, for each i, B(S, k, i) is composed of one letter, thus Sig(S1 , C) =Sig(S2 , C) immediately means HamDist(S1 , S2 ) ≤ d. This implies that theHamming distance does not have to be computed for any pair in each group.
Another task in step 1 is avoiding duplications. We do this in another way.

Duplicate outputs occur when HamDist(S1 , S2 ) is strictly smaller than d.
If HamDist(S1 , S2 ) = d, exactly one C ∈ C(k, k − d) satisﬁes Sig(S1 , C) =Sig(S2 , C). This implies that without any check, we can output pairs with Hamming distance equal to d without duplications. Thus, we change d′ from 0 to
d and output only pairs with Hamming distance equal to d′ , we need no checkfor duplications. We call this algorithm the complete version. For the complete
version of our algorithm, we obtain the following theorem. Note that the computation of HamDist(S1 , S2 ) is done in O(d) time if Sig(S1 , C) = Sig(S2 , C).
Theorem 2. The short Hamming distance string pair enumeration problem
for∑dset S of strings of length l and distance threshold d can be solved in O(( i=0 l Ci )×(|S|+dN )) = O(2l (|S|+dN )) time where N is the number of output string pairs.

4

Approach to Long Substrings

In this section, we consider the problem of ﬁnding all pairs of substrings of agiven string S that are similar to each other in some sense. In the sense of timecomplexity, the existence of polynomial time algorithms for this kind of problem
is trivial since we have to compare only a polynomial number of pairs. However,in a practical sense, this problem is diﬃcult since even if if we restrict the pars
to be strings of the same length, O(|S|3 ) pairs of substrings must be compared.
For huge strings the computation time must be quasi linear time, thus O(|S|3 )time is far from practical eﬃciency.
Here we approach this problem with our algorithm. For a string S, distancethreshold value d and length l, a pair of positions (p, q), p ̸= q is an l-d seed if
HamDist(S[p, p+l −1], S[q, q +l −1]) ≤ d. We can ﬁnd all l-d seeds by giving all
the substrings of S of length l to our multi-classiﬁcation algorithm. One typicalapproach to capturing the similarity structures by using such seeds is as follows.
We partition S into non-short blocks, for example, partition a string of 1,000,000
letters into 1,000 strings of 1,000 letters. We deﬁne the similarity measure ofblocks S[k1 , h1 ] and S[k2 , h2 ] by the number of l-d seeds (p, q) satisfying k1 ≤p ≤ h1 and k2 ≤ q ≤ h2 . We can visualize the similarity structure of this measure
by a ﬁgure such that the intensity of the color of the pixel (x, y) is given by the
number of l-d seeds in xth block and yth block. The left of Figure 2 shows anexample of pictures obtained by this method. If the blocks are large, any two
blocks have a suﬃciently large number of seeds, thus all pixels will be the samecolor. For large scale data, we need more precise method of deleting such noise.
A pair of positions (p, q), p ̸= q is a normal l-d seed if (p, q) is an l-d seed
and p is a multiple of l. The normal l-d seeds can also be enumerated by ouralgorithm with shorter time than the usual l-d seeds. For a width thresholdw and count threshold c, we say the pair of substrings S[k1 , h1 ] and S[k2 , h2 ]is a normal (w, c, l, d) candidate if there are distinct c normal l-d seeds (p, q)satisfying k1 ≤ p ≤ h1 , k2 ≤ q ≤ h2 and |p − q| ≤ w. A pair of similar substrings
can be considered to be a normal (w, c, l, d) candidate for non-trivial w, c, l, andd. Especially if the Hamming distance of two substrings is short, they mustFig. 2. Matrix showing similarity of mouse 11 chromosomes (X-axis) and Human 17
chromosome (Y-axis), with black cells on similar parts; we can see similar substructures
as diagonal lines, but the ﬁgure is noisy because of the low resolution.

be a normal (w, c, l, d) candidate for a certain (w, c, l, d). For example, if theHamming distance of two substrings of length 3000 is at most 290, they have to
be a normal (0, 3, 30, 2) candidate. If the edit distance of two substrings of length
3000 is at most 190 and has at most 50 of insertions and deletions, then they
have to be a normal (50, 3, 30, 2) candidate. Thus, we are motivated to enumerate
all normal (w, c, l, d) candidates. However, for a set of c normal l-d seeds, there
would be many normal (w, c, l, d) candidates including these seeds. Thus, thenumber of enumerated candidates can be large. Recall that the aim here is toﬁnd candidates of similar substrings, or to capture the similarity structures. Not
many similar candidates are needed to represent one similar structure. Thus,
here we propose a simple algorithm to output a set of pairs of substrings suchthat any normal (w, c, l, d) candidate is obtained by a slight modiﬁcation of oneof the pair.
For an integer z, we consider a slit of width 2w. An l-d seed (p, q) is includedin the slit of z if z ≤ p − q ≤ z + 2w. For each multiple z of w, we ﬁnd all integers
i such that there are at least c l-d seeds (p, q) included in the slit of z such thati ≤ p + q < i + a where a is a given length, and one of them satisﬁes i = p + q.
For such integers i, the pair of substrings S[(i + z + w)/2, (i + z + w)/2 + a] andS[(i − z − w)/2, (i − z − w)/2 + a] is a desired pair. We output all such pairs. Thisrequires sorting of all l-d seeds, but remaining process is very light and simple.
We display a ﬁgure made by this approach in the right of Figure 2.

5

Applications and Extensions

In the practical applications there are many variants of similar string ﬁnding
problems. In the following subsections we present several problems to which we
can apply our multi classiﬁcation algorithm.
5.1

Computing Mismatch Tolerance

In real world applications, we often need to ﬁnd several unique short strings
which are similar to no other strings. Such unique strings can be used as characterizations, invariants of string databases, or markers of substructures. A typicalapplication is in microarray. A microarray is a tool for biological experiments thatcan detect the existence of short strings, say 25 letters, in the genome sequenceof a species or organizations. If a unique short substring in a gene sequence is
known, the existence of the substring indicates the existence of the gene. To
allow for experimental error, the substring has to have no similar substring.
When the Hamming distance is used, one of the uniqueness measure iscalled mismatch tolerance. The mismatch tolerance is the shortest Hamming
distance to the other string. More precisely, for a set S of strings of the samelength l, the mismatch tolerance of string S, denoted by mis(S, S) is deﬁned
by min{HamDist(S, S ′ ) | S ′ ∈ S \ {S}}. If mis(S, S) is large, S has no similar
string in S in the sense of Hamming distance, thus our aim is to ﬁnd the strings
having not so small mismatch tolerance. Here we deﬁne our problem.
All Mismatch Tolerance Computing Problem
Input: for a set S of strings of the same length l, distance threshold d
Output: all S ∈ S such that mis(S, S) ≤ dThis problem can be solved by solving the short Hamming distance string
pair enumeration problem. Actually, we do not have to output pairs, thus we do
not check the duplications. Moreover, in the complete version of our algorithm,
we have to execute the algorithm only for d′ = d, and omit the computation ofHamming distance. Thus we obtain the following theorem.
Theorem 3. The all mismatch tolerance computing problem for set S of stringsof length l and distance threshold d can be solved in O(l Cd |S|) = O(2l |S|) time.
5.2

General Edit DistanceIn many studies and real world applications, the distance between two strings,
genomes, and documents is evaluated by edit distance. The multi classiﬁcation
algorithm proposed above fails for edit distance since the position of the block
shifts by the preceding insertions and deletions. For example, the edit distance
between S1 =ABCDEFGH and S2 =ACDEFGHI is 2, obtained by deleting thesecond letter of S1 and the eighth letter of S2 . By setting k = 4, the strings are
partitioned into substrings of two letters. Although there are only two positionsedited, no substrings in the partitions of S1 and S2 are the same, since thesubstrings in the middle are shifted by the deletion of the second letter.
For adapting to edit distance, we consider Ĉ(k, d) instead of C(k, k−d) whereĈ(k, d) is the set of k − d signed or unsigned integers taken from 1 to d, i.e.,Ĉ(k, d) = {C | |C| = d, C ⊆ {1, 1+ , 1− , 2, 2+ , 2− , . . . , k, k+ , k − }}. i+ , i− and imeans an insertion, a deletion and a change at the ith block. For C ∈ Ĉ(k, d),let sft(C, i) = |{j + | j < i, j + ∈ C}| − |{j − | j < i, j − ∈ C}|, and Eq(C) ={i | i, i+ , i− ̸∈ C}. We denote S[⌈|S|(i − 1)/k⌉ + 1 + j, ⌈|S|i/k⌉ + j] by B̂(S, i, j).
ˆThen, for string S and C ∈ Ĉ(k, d), we deﬁne Sig(S,C) by B̂(S, i1 , sft(C, i1 )) ·B̂(S, i2 , sft(C, i2 ))·. . .·B̂(S, ik−d , sft(C, ik−d )) where Eq(C) = {i1 , . . . , ik−d }, ij <ij+1 . By using the terminology, we obtain the following lemma.

Fig. 3. Increase in computation time against the increase in database size with ﬁxed land d: the right-lower ﬁgure is for ﬁxed d/l inputting a string of 2.1 million letters

Lemma 2. If the edit distance between strings S1 and S2 is no more than d, atˆleast one C ∈ Ĉ(k, d) satisfies Sig(S1 , Eq(C)) = Sig(S2 , C).
The proof is omited by the page limit. Based on the lemma, we are motivatedˆ
to classify all strings by Sig(S, Eq(C)) and Sig(S,C) for all C ∈ Ĉ(k, d) to obtainall the pairs of strings satisfying the condition of the lemma. By checking theedit distance for all pairs in each group classiﬁed, we can ﬁnd all pairs of strings
with edit distance at most d.
Theorem 4. The computation time of algorithm MultiClassification modified toedit distance is bounded by O(3d l/k × |S| ×l Cd ), except for that for step 1.
Theorem 5. For set S of strings of length l and distance∑dthreshold d, we can findall pairs of strings with edit distance at most d in O(3d ( i=0 l Ci )×(|S|+l2 N )) =O(2l 3d (|S| + l2 N )) time where N is the number of string pairs to be output.

6Computational Experiments

This section shows the results of computational experiments of the basic versionof our algorithm. The code was written in C, and compiled with gcc. We used
a note PC with a Pentium M 1.2GHz processor with 768 MB of memory, withcygwin which is a Linux emulator on Windows. The implementation is available
at the author’s homepage; http://research.nii.ac.jp/˜uno/index.html.
The instance is the set of substrings of ﬁxed length taken from the Y chromosome of Homo sapiens. The length is set to 20, 50 and 300. Figure 3 shows
the results. Each line corresponds to one threshold value d. The X-axis is thenumber of input substrings, and Y -axis is the computation time. Both axes use

Fig. 4. number of radix sorts performed.

log scales. We can see that the computation time increases slightly higher thanlinear, but smaller than the square. Figure 4 shows the number of executed radix
sorts. The number increases drastically if the number of mismatches increases,
but does not increase much as the increase of input size.
We also show the increase in computation time against the increase of l withﬁxed d/l. The instance is ﬁxed to that with 2.1 million strings, and the resultis shown in the right-lower ﬁgure of Figure 3. From these results, at least for
genome sequences our algorithm is quite scalable for the increase of input string.

7

Conclusion

We proposed an eﬃcient algorithm for enumerating all pairs of strings with Hamming distance at most given d from string set S. We focused on the practicaleﬃciency of algorithms, and proposed an algorithm based on multiple classiﬁcations according to combinations of blocks of each string. We proved that thecomputation time of its variant is bounded by linear of the string length when
the length of strings in the string set is constant. A simple modiﬁcation of thealgorithm adapts the edit distance, and computation of mismatch tolerance.
We also proposed a method of ﬁnding similar non-short substrings from hugestrings. We modeled similar non-short strings by two non-short strings including
several short similar substrings. We presented an eﬃcient algorithm for ﬁnding
those strings from huge strings. By the computational experiments for genome
sequences, we demonstrated the practical eﬃciency of the algorithm. On thecomparison of genome sequences, we could ﬁnd similar long substrings fromhuman and mouse genomes in a practically short time.

Acknowledgments
We gratefully thank to Professor Asao Fujiyama of National Institute of Informatics of Japan, Professor Shinichi Morishita of Tokyo University Doctor
Takehiko Itoh of Mitsubishi Research Institute, and Professor Hidemi Watanabeof Hokkaido University, for their valuable comments. We would also like to thankto Professor Tsuyoshi Koide and Doctor Juzo Umemori of National Institute of
Genetics for their contribution to the evaluation of the algorithm on practicalgenome problems.

References
1. K. Abrahamson, Generalized String Matching, SIAM J. on Comp., 16(6), pp. 1039–
1051, 1987.
2. S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, Basic localalignment search tool, J. Mol. Biol. 215, pp. 403–10, 1990.
3. S. F. Altschul, T. L. Madden, A. A. Schaﬀer, J. Zhang, Z. Zhang Z, W. Miller, D.
J. Lipman, Gapped BLAST and PSI-BLAST: a new generation of protein databasesearch programs, Nucleic Acids Res., 25, pp. 3389–3402, 1997.
4. A. Amir, M. Lewenstein, and E. Porat, Faster Algorithms for String Matching withk Mismatches, In Symposium on Disc. Alg., pp. 794–803, 2000.
5. P. Brown and D. Botstein, Exploring the New World of the Genome with DNA
Microarrays, Nature Genetics, 21, pp. 33–37, 2000.
6. J. Feigenbaum, S. Kannan, M. Strauss, and M. Viswanathan, An Approximate l1diﬀerence Algorithm for Massive Data Streams, In Proc. FOCS99, 1999.
7. U. Manber and G. Myers, Suﬃx Arrays: A New Method for On-line String Searches,
SIAM J. on Comp., 22, pp. 935–948, 1993.
8. S. Muthukrishnan and S. C. Sahinalp, Approximate Nearest Neighbors and Sequence Comparison with Block Operations, In Proc. 32nd annual ACM symposiumon Theory of Computing, pp. 416–424, 2000.
9. S. Muthukrishnan and S. C. Sahinalp, Simple and Practical Sequence Nearest Neighbors under Block Edit Operations, In Proc. CPM2002, 2002.
10. W. R. Pearson, Flexible sequence similarity searching with the FASTA3 program
package, Methods in Molecular Biology 132, pp. 185–219, 2000.
11. S. Yamada, O. Gotoh, H. Yamana, Improvement in Accuracy of Multiple Sequence
Alignment Using Novel Group-to-group Sequence Alignment Algorithm with Piecewise Linear Gap Cost, BMC Bioinformatics 7, pp. 524, 2006.
12. T. Yamada and S. Morishita, Computing Highly Speciﬁc and Mismatch Tolerant
Oligomers Eﬃciently, Bioinformatics Conference 2003, 2003.
13. T. Yamada and S. Morishita, Accelerated Oﬀ-target Search Algorithm for siRNA,
Bioinformatics 21, pp. 1316–1324, 2005.