A faster way to compute edit distance does not exist | Hacker News Reader

A faster way to compute edit distance does not exist

bostonglobe.com

150 pointsdnt404-154 comments

The title of the Boston Globe article and of the HN submission is misleading.

The article does not prove that subquadratic edit distance algorithms do not exist. It only proves it conditional to another unproven complexity hypothesis (SETH). In other words, it shows that if such algorithms exist, then faster algorithms exist for another problem (SAT for CNF formulae with certain size bounds), where we haven't been able to find them yet. See the original article http://arxiv.org/abs/1412.0348 whose title is more accurate.

This is important work, of course, and provides more evidence that faster edit distance computation is not possible, but it is not proven yet.

The wording in the article also makes it sound like the existence of a faster algorithm for edit distance would imply P=NP ("Most if not nearly all computer scientists believe the P equal to NP problem is false", although later a variant of the problem is mentioned), but that's not the conclusion of the theorem.

A more accurate wording would be that the existence of a fast algorithm for edit distance implies that P is "close" to NP, because there would exist a sub-exponential algorithm for SAT (but not necessarily a polynomial algorithm).

I don't get it - how does the author of the piece not know this? He seems to reflect an excellent understanding, and it's bizarre that he would would miss this.

Often times authors of articles are not the same people who write their titles ... it may even be changed without their knowledge (until the paper is actually printed).

The title isn't misleading. The title is a reasonable summary of what the article aims to say, in actuality. What article is attempting to say may be wrong but that's a different issue.

There are really two notions of proof here [and hence truths and facts]. The article uses proof in a scientific sense, where P!=NP is accepted as empirical fact by the community of computer scientists in the same manner that biologists take natural selection as empirical fact.

To put it another way, representing the world as if P!=NP is no less reasonable than representing the world as if Newtonian physics are applicable.

Theoretical CS is usually not thought of as an experimental or empirical field. When a paper in that field claims "X does not exist", this has to mean that the inexistence of X was proven, not that a body of empirical knowledge against the existence of X has been collected. By contrast, such things are called "plausibility arguments", "heuristics", etc.

There is such a thing as experimental truth, but it applies to experimental fields, and theoretical CS is usually not thought as one of them. I still think it is misleading to claim that the inexistence of something has been proven if it is conditional to another hypothesis.

Computer scientists behave as if P!=NP, and Donald Knuth will send a check to anyone who comes up with a polynomial time general solution to 3-sat.

Or to put it another way, P!=NP is a de facto if not de jure axiom of theoretical computer science. And the burden of justification is on anyone whose conclusions are not premised on P!=NP just as it is a biologist who takes issue with evolution by saying "it's only a theory."

>The article uses proof in a scientific sense

Science does not deal in proofs, for example, the wiki page on scientific method does not use the word except in the mathematical sense [0].

Science deals in hypotheses, evidence, and models.

[0] https://en.wikipedia.org/wiki/Scientific_method

One common form of scientific proof is that upon which your comment rests: pointing to something and proving that x obtains, e.g. showing me a unicorn would demonstrate that unicorns exist. G. E. Moore (the less famous of Wittgenstein's doctoral advisors) pointed out this out in Proof of an External World [1]. It's more popular form is Popper's falsifiability [2] which is the more commonly accepted formulation of scientific formalism.

[1]: http://www.thatmarcusfamily.org/philosophy/Course_Websites/R...

[2]: https://en.wikipedia.org/wiki/Falsifiability

Showing me a unicorn example is not proof that unicorns exist. It is evidence towards a hypothesis that they exist. After you present your unicorn, I may discover it is a modified horse.

Science can never prove truth or falsity of anything - it only provides evidence for or against hypotheses, but every single thing can be changed subject to future evidence. As such, there is no true/false in science, only degrees of evidence.

This article, which you claim uses proof "in the scientific sense," does not prove a hypothesis is false, only that is gets less and less likely and competing ones get more and more likely, which is what your examples are getting at. The article proves (in the mathematical sense) the non-existence of an item, only if a certain conjecture is true.

As pointed out above, this is math, not empirical.

The thing is the article implies the paper proves a link to p!=NP but the actual paper only claims "evidence" that there is a link, so there are multiple stages where the link is sketchy.

beat me to it

>The fact that edit distance is only computable in quadratic time has big implications for genomics. The human genome contains about 3 billion base pairs. To compute the edit distance between two human genomes takes 3 billion-squared operations (to appreciate how big that is, write a 9 followed by 18 zeroes). That’s a number of operations, explains Piotr Indyk of MIT, that is “computationally infeasible.” Which is to say that our best computers chugging away for a really long time still won’t generate an answer.

As was commented last time this was posted: Just because it's not possible to do better in the general case doesn't mean it isn't possible to do better in your case. For all we know, human genomes may not actually be 100% random strings, but may have some kind of structure that makes it possible to do it faster. Even when solving the problem exactly.

Human genomes are very much not random strings, and in any case if calculating the edit distance between two human genomes they are likely largely similar, and if memory serves there are suffix tree/array based algorithms for bounded edit-distance calculations.

Moreover, I'm not sure if it would ever actually be useful to compute the edit distance between two full genomes. Edit distances/local/global alignments are useful for short fragments (gene's/reads etc) but not the full sequence.

The challenge with comparing genomes is that you can't just do edit distance using a naive substitution table. It has to be probabilistic and contextual (for it to be scientifically useful), because genome sequences are actually sampled estimates of the true genome sequence. You have to tolerate errors, and when you do that, the exploration space gets huge.

Instead of aligning two genomes this way, people normally start with a very well calibrated and fairly accurate reference sequence, then align to that structure probabilistically, and "call the joint variants".

This is actually far more interesting that doing the raw hard problems that computer scientists love to talk about theoretically. One of the reasons it's so interesting is that different genomes differ by operations that are much more complex than simple edit distance- for example, large regions can be excised, and placed, in reverse order, in completely other parts of the genome. Trying to use a DP edit distance calculation to detecet those is futile.

http://bcb.io/2014/10/07/joint-calling/

The name "Wagner-Fischer" is new to me. I usually cite this as Levenshtein [1965]. Even the Wagner-Fischer wp page notes that Levenshtein was first by a long shot. https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...

Yeah this struck me as well. I've always heard it described as Levenshtein edit distance.

It's a nice theoretical result. In practice there are some quirks though:

- I assume this is worst case complexity. While this is useful, maybe the average time can be much lower for certain data (like the genome).

- I assume the theorem doesn't restrict the input strings in any way. If you put restrictions on the input then there could be a faster algorithm than the general one. I don't know if this can be applied to the genome though.

- People are interested in the constant factor too.

Also, a fast approximation with a good error bound might be good enough for many applications in biology.

Absolutely. This is surely more theoretical than practical. Solving a linear system of equations has cubic complexity but we still routinely solve systems with millions of equations. Billions are probably being done too. We just take advantages of special features that allow us to do things faster than the worst case - such as having a sparse matrix.

As a quadratic algoritm, assuming 13 million base pairs can be solved in 7 seconds on a GTX275 (according to a paper on edit distance computation), is it correct to assume that 3 billion base pairs can be solved in (3bil * 3bil / (13mil * 13mil/7)) in 373443 seconds, or about 103 hours. Isn't that fast enough for a quadratic algorithm that samples DNA to be useful?

I think the article is talking about the "full fledged" problem, while the computation you talk about could be using a set of optimizations aimed particularly at base-pair edit distance problem.

For example, I could assume that there no deletions and insertions, only changes and then the problem becomes embarrasingly paralell and extremely easy to express in assembly-like operations. So I could paralellize it on a GPU by splitting the string into fixed length substrings and get huge gains. Problem is, can it be safely assumed that there are no deletions and insertions?

Wikipedia has a list with some modifications that can also be used to speedup the calculation under certain constraints: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...

I wondered about that as well, 3 billion squared is a massive number but we have processors in the billions of operations per second per core and machines with hundreds of thousands of processors.

I'm curious how fast we could do it on the raw 'string' in the worst case (assuming DNA is entirely random) but it's out of my scope, anyone hazard a guess?

Previously here: https://news.ycombinator.com/item?id=9698785

That was refreshing; a regular newspaper publishing an article about computer science. And it does a fairly good job, I wish I could see something related to CS rather than to web apps and startups in the Canadian newspapers.

An article on edit distance without mentioning the person who invented it - Levenshtein. https://en.wikipedia.org/wiki/Vladimir_Levenshtein

This is interesting, but it looks like this proves nothing according to the article since we don't know if P==NP. We are no closer to understanding whether or not a faster way to compute edit distance exists. All we know now is that it matches up to a class of problems that we _think_ are probably hard. It is still possible that we might find a faster solution to the problem.

I'd like to request a title change - "New proof that a faster way to compute edit distance might be tied up in the P vs. NP problem"

Hence the need and desire for approximation algorithms. Often, you can give up a tiny amount of precision in exchange for dramatically increased performance - if you can make an assumption.

For instance, computing cardinality of a value over a huge dataset (distributed or otherwise) that is assumed to be evenly distributed would take memory proportional to the size of the dataset for 100% precision. Implementing a cardinality approximation algorithm like HyperLogLog++ lets you get a pretty close to accurate result for this calculation but with far fewer resources. There are many others and I think it is important to consider this trade off when it is appropriate.

Of course, it makes an assumption that the data is distributed more or less evenly.

Now we can start looking for a more precisely defined problem, that can be solved faster than in quadratic time.

Or in other words, for certain classes of inputs, we can find a faster algorithm. We only need to find/define those classes.

Does a similar result hold, if we don't consider inserts, deletions and substitutions (definition of edit distance), but only inserts and deletions?

I don't know about the mathematical result (the conditional proof), but I do know that it's easy to expand or limit the edit operations, or change their costs, while keeping the dynamic program order the same (so not e.g. allowing 'move this whole phrase' type edits - that would probably be cubic or worse). If you're considering the generalized 'set any costs you like for the operations' problem then you could set the subst cost as 2 and the insert and delete as 1.

Again, I know that's not precisely what you asked. I can't think of a reduction from "insert+delete only" problems to "insert+delete+subst" (all operations cost 1) problems (where solving the latter gives you a solution to the former, and the size is no more than k times the original).

How do you define an edit distance (the number of operations required to transform one string to the other) if you don't allow substitutions?

Eg. what's the edit distance between these two strings?

AAAA BBBB

Traditionally, it would be 4, but it's unclear if you allow only inserts and deletions.

  > Eg. what's the edit distance between these two strings?
  > 
  > AAAA BBBB
  > 
  > Traditionally, it would be 4, but it's unclear if you
  > allow only inserts and deletions.

It is >= 8, since you surely have to remove 4 As and insert 4 Bs. Since these 8 transformations indeed transform AAAA into BBBB, it is exactly 8.

It is very easy to generalize the Wagner-Fisher algorithm (https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...) to this "simpler" variant of edit distance, but this algorithm will still have a (worst-case) runtime of O(m*n), where m, n are the lengths of the two strings.

Of course, the question remains: Is there a (worst-case) faster algorithm?

Don't know, but you still end up aligning common subsequences (advanced monotonically in both seqs) and you still have the same order-of-computing-cells allowed in the standard m*n dynamic program. Your restricted problem is basically asking for the standard unix line-diff.

It's not unclear, any substitution can be replicated by a deletion and insertion. I have no idea if that leads to a simpler case of the edit distance algorithm.

> Edit distance is useful, but also very time-consuming to calculate.

So I guess we will soon see a lot of crypto based on calculating edit distances?

No. Quadratic speed is way too fast for crypto - besides, asymmetric cryptography relies on problems that are difficult to solve but candidate solutions are easy to validate! This is what the complexity class NP is about. As far as I know there's no way to check a solution for edit distance any faster than it takes to compute it in the first place. Also, the new proof just shows that edit distance is quadratic if P!=NP.

I get what you mean but 'easy to validate' in the context of NP means 'can be validated in polynomial time'. It seems to me that you imply that edit distance is harder to validate than problems in NP. Edit distance itself is in NP since P is in NP.

I mean that there needs to be a fundamental difference between the difficulty of finding a solution and validating one. There's none in case of edit distance.

  > I mean that there needs to be a fundamental difference between the 
  > difficulty of finding a solution and validating one. There's none in 
  > case of edit distance.

If you consider the decision problem "Is the edit distance <= d?", there is (according to this result) a fundamental difference - though only a polynomial one.

To see this, consider the following argument:

Clearly the edit distance between strings of length m, n is bounded by m+n (>= d). So if we found a way to transform the string s1 into s2 using d steps, we can construct a certificate of length O(m+n) (worst case) steps, which can be verified in linear time.

On the other hand (according to this result) you need Omega(m*n) (worst case) steps to find such a certificate.

The article says it's quadratic, which would put it in P as it's polynomial time.

P is in NP.

Yeah, don't know enough about it.

Hmmmm. That got me thinking about spam, and I went off on a tangent.

What if an email could be parsed in such a way as to generate seed data for an an NP problem which the sender must solve and supply the answer in the in the email header...

If the receiver can instantly dismiss any emails that provide an answer that can not be verified, then that could have a huge impact on the the spammers ability to send spam in the volumes they currently enjoy. A penalty of 5 seconds per email is unlikely to impact ordinary users, but would be a major pain for spammers.

Also, could this be used to throttle user input to mitigate brute force attacks?

You're not the first one to think of this: https://en.wikipedia.org/wiki/Challenge%E2%80%93response_spa...

You would quickly run out of instances of a given NP problem that can be solved under 5 seconds.

It's still polynomial though, I think it's not practical for crypto.

n^100 is perfectly good for crypto.

n^2 is insufficient, but 'polynomial' as a category is not necessarily bad.

P=NP is not the end of the world, by itself.

Which order of n it is has no influence on crypto. The crux is whether there is a large difference in computing an answer and validating an answer.

A technique which requires both n^100 for validation and computing is useless, a technique which requires n^2 for computation and log(log(n)) for validation would be fine (you just have to use sufficiently large n).

It's just that problems with an exponential computation and polynomial validation provide an almost unbeatable cost-to-benefit ratio in terms of n. A n^2/log(log(n)) algorithm might require 10MB encryption keys to be secure, while a n^a/n algorithm like the current prime-based cryptosystems require ~4KB.

Operations are not going to be sublinear. So that lower limit does make very small absolute orders matter.

And I think it's implied that validation has to actually be possible on computers, so given that constraint an enormous number for brute-forcing will almost always be a solid option.

So n^2/anything is going to suck. n^3/anything or n^4/anything may or may not suck. And n^100/n^small is great.

Also RSA operations aren't n^a/n. They're sub-exponential to brute force, and n^3 to encrypt and decrypt. Unless you mean a different system.

It's only quadratic, for asymmetric crypto you'd want something with a much higher complexity and preferably non-polynomial.

This is misleading twice over. First, as a3_nm notes, this proof depends on unproven conjectures, and so this isn't proven yet.

Secondly, it is possible to do better than the Wagner-Fischer algorithm in certain cases. I figured this out myself and was about to write a paper on it when I realized that other researchers had beat me to it by a couple of decades.

If the two strings are equal you can establish that the edit distance is 0 in linear time, obviously. If you consider how the algorithm fills out the square down the diagonal you'll see that if there's only a one-letter difference you only actually need to fill out small parts of the grid around that difference.

This is generalizable, so the complexity actually depends on the distance between the strings.

In practice, yes, the computation time required to compute edit distance will depend on the actual data. Similarly, 'sorting' a list that is already sorted can be done in linear time, and near-sorted lists can be sorted much faster than a randomly ordered list.

This is certainly useful in practice, but it doesn't affect whether the worst- or average-case complexity is quadratic. I'd like to see a quadratic (or exponential etc) time problem that couldn't be solved faster in many cases.

Reply on news.ycombinator.com