7
$\begingroup$

I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can be assumed that one of the strings is fixed, i.e., we are comparing one fixed string to a billion other strings.

I know that the dynamic programming implementation of the levenshtein distance is $\mathcal{O}(m n)$, would like to know if there are any room for improvement. I found these two algorithms:

  • $\mathcal{O}(n + d^2)$ algorithm, in which $d$ is the edit distance by Berghel et al. However I can't make the assumption that $d$ is small so it might not give any advantage
  • $log(n)^{\mathcal{O}(1/\epsilon)}$ approximation in $n^{1+\epsilon}$ time by Andoni et al. But I have two concerns regarding this:
    • Is this algorithm also fast in practice?
    • Does $log(n)^{\mathcal{O}(1/\epsilon)}$ mean the computed edit distance in worst case is $log(n)^{\mathcal{O}(1/\epsilon)}$ times the actual one? In that case it's too much.

Do you know of any other algorithm/idea/approach that might be applicable?

$\endgroup$
  • 2
    $\begingroup$ Have you looked at Levenshtein automata? $\endgroup$ – adrianN Jul 26 '17 at 10:15
  • $\begingroup$ Does it have to be exactly the Levenshtein distance, or is any relatively consistent edit distance good enough? $\endgroup$ – Pål GD Jul 26 '17 at 15:30
  • $\begingroup$ Are you only interested in the edit distance if the edit distance is below some threshold (e.g., if the edit distance is $> 20$, you don't care what the exact edit distance is; just know that it is $> 20$ suffices)? $\endgroup$ – D.W. Jul 26 '17 at 15:32
  • $\begingroup$ Is DNA really Levenshtein similar. 11 versus 00 is 2 for Levenshtein but 10 versus 01 is only 1. I would be really surprised with DNA a match or not is all that matters. $\endgroup$ – paparazzo Jul 26 '17 at 17:00
  • $\begingroup$ @PålGD a good approximation of the Levenshtein distance could also be good. $\endgroup$ – Ameer Jewdaki Jul 26 '17 at 18:49
3
$\begingroup$

One approach is to build a Levenshtein automaton for the fixed string (see, e.g., here). Given a string $x$ and a distance $D$, you can build a DFA that recognizes all strings that are at distance $\le D$ from $x$. Thus, you can test whether a string is close to $x$ in $O(n)$ time, where $n$ is the length of the string. I'm not sure what the space requirements are to store the DFA (they are linear in $m,n$, but might be exponential in $D$).

Alternatively, you could use an "early-out" algorithm for computing the edit distance. You mentioned that you are only interested in the edit distance if it is less than some threshold $D$. There is an "early-out" algorithm for computing the edit distance whose running time is $O(\max(n,m) \times D)$, which computes the edit distance if it is $\le D$ or else outputs "too big" if it is $>D$. Basically, you do the standard dynamic programming algorithm for the edit distance, but only compute the elements of the matrix that are $\le D$ away from the diagonal. In your case this might or might not be better than the other alternatives.

$\endgroup$
-2
$\begingroup$

If I had to do billions and it was only 4 characters I would represent the characters as
1000
0100
0010
0001
It is then a 35 byte integer

Dot a bit-wise and and count the 1's

Not perfect but billions is a lot unless you throw a lot of CPU at it.

$\endgroup$
  • 1
    $\begingroup$ It's actually some trillions of distance calls in total, but I have access to a computing cluster. The problem is that if two strings are 100 in length and there are several insertions or deletions the dot product will deviate from the actual distance. $\endgroup$ – Ameer Jewdaki Jul 26 '17 at 18:58
  • $\begingroup$ OK you said 70 in Length. I am surprised an algorithm based on words applies to DNA. The are scientific DNA matching equations - I am surprised you are not using one of those. $\endgroup$ – paparazzo Jul 26 '17 at 19:05
  • $\begingroup$ Not complaining but a DV does not help me be a better contributor here. $\endgroup$ – paparazzo Jul 26 '17 at 19:55
  • $\begingroup$ I didn't down vote the answer. In fact I think it's generally a good approach, but here it is too far off because of insertions/deletions. $\endgroup$ – Ameer Jewdaki Jul 26 '17 at 20:20
  • $\begingroup$ and yes there are probabilistic ways to define distance between two DNA sequences but none, I believe, is simpler to compute than edit distance. So here I'm just starting with the "simple" measure $\endgroup$ – Ameer Jewdaki Jul 26 '17 at 20:22

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.