3 ms·
>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 co
by im3w1l 11y ago
>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.
- new299 11y agoHuman 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.
- dekhn 11y agoThe 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/ http://bcb.io/2014/10/07/joint-calling/