10
$\begingroup$

I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P matches a substring of T with at most k mismatches. This is different from the k-differences problem (edit distance). A mismatch implies the substring and the pattern have a different letter in at most k positions. I really only require k=1 (at most 1 mismatch), so a fast algorithm for the specific case of k=1 will also suffice. The alphabet size is 26 (case-insensitive english text), so space requirement should not grow too fast with the size of the alphabet (eg., the FAAST algorithm, I believe, takes space exponential in the size of the alphabet, and so is suitable only for protein and gene sequences).

A dynamic programming based approach will tend to be O(mn) in the worst case, which will be too slow. I believe there are modifications of the Boyer-Moore algorithm for this, but I am not able to get my hands on such papers. I do not have subscription to access academic journals or publications, so any references will have to be in the public domain.

I would greatly appreciate any pointers, or references to freely available documents, or the algorithm itself for this problem.

$\endgroup$
  • 2
    $\begingroup$ If the pattern is fixed (but the text to match varies), you could potentially create a finite automaton and run the text through that. There are also algorithms using suffix trees (usually good if the text is constant and pattern varies, but also applicable if both vary), you might be able to find some references on the web. (Not adding an answer yet as I am not very sure of the suffix tree based algorithms, if some one knows please feel free to ignore this comment). $\endgroup$ – Aryabhata Sep 29 '12 at 21:34
  • $\begingroup$ @Aryabhata Thanks! Both the pattern and the text change. In that context, building a finite automaton would be too expensive, especially when including the scope for 1 mismatch. As for suffix trees/suffix arrays, I have never used them, and know little about them, but was under the impression that they are slow to build and efficient mainly for exact matching. But I will explore this option further. Any pointers in this direction, or in any other direction would be most useful! $\endgroup$ – Paresh Sep 29 '12 at 22:33
  • 1
    $\begingroup$ No, suffix trees can be used for approximate matches too. Atleast the wiki claims so: en.wikipedia.org/wiki/Suffix_tree $\endgroup$ – Aryabhata Sep 30 '12 at 1:43
5
$\begingroup$

Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA.

Once the suffix array has been constructed, we need to construct a Longest Common Prefix (LCP) array for the suffix array. The LCP array stores the length of the longest common prefix between two consecutive prefixes in the suffix array (lexicographic consecutive suffixes). Thus, LCP[i] contains the length of the longest common prefix between SA[i] and SA[i+1]. This array can also be constructed in linear time: see here, here and here for some good references.

Now, to compute the length of the longest prefix common to any two suffixes in the suffix tree (instead of consecutive suffixes), we need to use some RMQ data structure. It has been shown in the references above (and can be seen easily if the array is visualized as a suffix tree), that the length of the longest common prefix between two suffixes having positions $u$ and $v$ ($u < v$) in the suffix array, can be obtained as $min_{u<=k<=v-1}{LCP[k]}$. A good RMQ can pre-process the $LCP$ array in $O(n)$ or $O(n\log n)$ time and respond to queries of the form $LCP[u, v]$ in $O(1)$ time. See here for a succint RMQ algorithm, and here for a good tutorial on RMQ's, and the relationship (and reductions) between LCA and RMQs. This has another nice alternative approach.

With this information, we construct the suffix array and associated arrays (as described above) for the concatenation of the two strings with a delimiter in between (such as T#P, where '#' does not occur in either string). Then, we can perform k mismatch string matching using the "kangaroo" method. This and this explain the kangaroo method in the context of suffix trees, but can be directly applied to suffix arrays too. For every index $i$ of the text $T$, find the $LCP$ of the suffix of $T$ starting at $i$ and the suffix of $P$ starting at 0. This gives the location after which the first mismatch occurs when matching $P$ with $T[i]$. Let this length be $l_0$. Skip the mismatching character in both $T$ and $P$ and try to match the remaining strings. That is, again find the $LCP$ of $T[i + l_0 + 1]$ and $P[l_0 + 1]$. Repeat this till you obtain $k$ mismatches, or either string finishes. Each $LCP$ is $O(1)$. There are $O(k)$ $LCP$'s for each index $i$ of $T$, giving this a total complexity of $O(nk)$.

I used an easier to implement RMQ giving a total complexity of $O(nk + (n+m)\log(n+m))$, or $O(nk + n\log n)$ if $m = O(n)$, but it can be done in $O(nk)$ too as described above. There may be other direct methods for this problem, but this is a powerful and generic approach that can be applied to a lot of similar problems.

$\endgroup$
4
$\begingroup$

Below is an expected $\mathcal{O}(n + m )$ algorithm (which can be extended to other $k$, making it $\mathcal{O}(nk +m )$). (I haven't done the calculations to prove it is so, though).

The idea is similar to the Rabin-Karp rolling hash algorithm for exact substring matches.

The idea is to separate each string of length $m$ into $2k$ blocks of $m/2k$ size each and compute the rolling hash for each block (giving $2k$ hash values) and compare those $2k$ hash values against the one from the pattern.

We allow at most $k$ mismatches in those values.

If more than $k$ mismatches occur, we reject and move on. Otherwise we try and confirm an approximate match.

I expect (caveat: haven't tried it myself) this will probably be faster in practice, and perhaps easier to code/maintain, than using a suffix tree based approach.

$\endgroup$
  • $\begingroup$ Just need a clarification. By "..separate each string of length m into 2k blocks of m/2k size each...", you mean that separate each substring of length m in T (of length n) into 2k blocks. And this hash can be calculated in O(n) by the rolling hash method. Then, the pattern string will also be divided into 2k blocks, and the corresponding hashes will be compared, giving allowance for atmost k blocks to mismatch. If so, then we would be able to potentially discard all cases where the number of mismatches is more than k. Did I understand right? $\endgroup$ – Paresh Sep 30 '12 at 15:42
  • $\begingroup$ @Paresh: Yes, you got it right, except because there are $k$ hashes, it is $\Omega(nk)$, rather than $O(n)$. $\endgroup$ – Aryabhata Sep 30 '12 at 17:49
  • $\begingroup$ I like this approach! Yet, this approach is fast in general, but degrades to O(mnk) if the number of matches is high (O(n) matches). Keeping this in mind, I maintained two rolling hashes, under the assumption that both cannot have a collision for the same input (I did not do this mathematically since I wanted to see the speed). This way, we don't have to verify a match char-by-char if the two hashes agree. This is pretty fast in general, but this too is slow if the number of matches are large. With this and with the way you suggested, it was slow for large matches. $\endgroup$ – Paresh Oct 1 '12 at 14:10
  • $\begingroup$ This could be made faster in the worst case if we divide the text into $\sqrt{m}$ sized blocks instead of $m/2k$ blocks. The pattern will also be divided into $\sqrt{m}$ (+1 if not perfect square) blocks, and we compare each of the blocks. This will be slower than your approach if the number of mismatches are small, but I think it should only be $O(nk\sqrt{m})$ in the worst case (I haven't checked this properly though). I have not tried this, but I will first explore suffix trees/arrays as you suggested. They seem to offer good bounds. Thanks! $\endgroup$ – Paresh Oct 1 '12 at 14:20
  • $\begingroup$ @Paresh: You cannot see it (in the revision history), but I initially had the $\sqrt{m}$ approach, but changed it to the current one. I think using $m/2k$ is better. You are unnecessarily computing too many hash values. Of course, which is better depends on your data. Of course, instead of $2k$, you could also try $k+1$ or $k+c$ etc. btw, worst case is $\Omega(nm)$ for both $\sqrt{m}$ and $m/2k$ approaches... $\endgroup$ – Aryabhata Oct 1 '12 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.