4 ms·
Another area where fuzzy string search is really useful is computational biology. You often have a particular DNA or RNA sequence and you want to figure out wha
by jphackworth 15y ago
Another area where fuzzy string search is really useful is computational biology. You often have a particular DNA or RNA sequence and you want to figure out what it is. However, the version on file can be different by a few mutations. For this sort of search where the database can be quite large, there are specialized algorithms like BLAST that index by n-grams.
Just thought I'd mention it because if you find it interesting, computational biology is a real growth area right now - the cost of sequencing genomes has been dropping faster than Moore's law, and it's quite possible that within our lifetimes we will be using this sort of technology to genetically engineer people.
- dhruvbird 15y agoYes, its useful for alignment. However, I've noticed that such alignment techniques are quite slow (since many of them resort to brute force on O(n^2) on sufficiently large strings - a few thousand maybe). I've found that a better way to approach this problem is to use suffix arrays to generate the best overlaps (ranges) from the reference and then perform a "range compression" (not of the audible kind) to coalesce adjacent ranges that differ by very little and insert/delete the offending characters. I'm using a similar technique for genome compression against a reference and am able to get a 700x compression on 2 Korean genomes and 130x compression on hg18(build 36.1) and another build/assembly(number 36.3) of the human reference genome.