# Efficient algorithm for edit distance for short sequences

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?

• Have you looked at Levenshtein automata? – adrianN Jul 26 '17 at 10:15
• Does it have to be exactly the Levenshtein distance, or is any relatively consistent edit distance good enough? – Pål GD Jul 26 '17 at 15:30
• 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)? – D.W. Jul 26 '17 at 15:32
• 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. – paparazzo Jul 26 '17 at 17:00
• @PålGD a good approximation of the Levenshtein distance could also be good. – Ameer Jewdaki Jul 26 '17 at 18:49

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.

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.

• 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. – Ameer Jewdaki Jul 26 '17 at 18:58
• 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. – paparazzo Jul 26 '17 at 19:05
• Not complaining but a DV does not help me be a better contributor here. – paparazzo Jul 26 '17 at 19:55
• 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. – Ameer Jewdaki Jul 26 '17 at 20:20
• 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 – Ameer Jewdaki Jul 26 '17 at 20:22