4 ms·

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

• dekhn 11y ago
  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/ http://bcb.io/2014/10/07/joint-calling/