I guess it is a bad news for bioinformatics (comparing two very long pieces of DNA), but maybe there are sufficiently useful approximations. Or if one string is fixed and only the other string varies, maybe you can precompute some data to make the comparison faster.
I don’t think the Levensthtein distance between two chromosomes is useful.
If a gene changes location it’s still for practical purposes mostly the same gene but the Levensthtein distance is very different.
http://arxiv.org/abs/1412.0348
Calculating Levenshtein distance may be unoptimizable.
What are the consequences?
I guess it is a bad news for bioinformatics (comparing two very long pieces of DNA), but maybe there are sufficiently useful approximations. Or if one string is fixed and only the other string varies, maybe you can precompute some data to make the comparison faster.
I don’t think the Levensthtein distance between two chromosomes is useful. If a gene changes location it’s still for practical purposes mostly the same gene but the Levensthtein distance is very different.