Unfortunately, a lot of the existing software is not intended for the search we're trying to do, or does not perform well under these conditions. We did in fact experiment with some of them before building our own. Bowtie, for example, doesn't allow more than 3 mismatches, and is also intended for alignments where there are very few matches (close to 1).
Since we need to be able to support multiple genomes (see Josh's comment), the amount of RAM we need to run a particular set of alignments is relatively important. Things like BLAT (which seems also intended for > 25 bases) need to keep the entire genome index in memory. This means that we would need to spin up a lot more servers to handle parallel requests, especially with different genomes.
FWIW our search is only a couple hundred lines of C++, and does the search with very little memory requirements.
Maybe genomics doesn't have to be so memory hungry. 8)
Bingo. And they use on the order of the genome size in RAM to do so.
The FM-index is a helluva sequence search machine.
Most software done by bio"informaticians" seems sub-par, both in implementation and in theoretical properties. I'd suspect this is caused by the fact that a lot of people actually don't come from CS, but biology or other fields.
https://en.wikipedia.org/wiki/Rabin–Karp_algorithm
Rabin karp with rolling hashes is actually (not exactly but almost) what tools like rsync, or bittorent use to find chunks and differences in files. So it scales really well.
The algorithms you cite come from a time when computers looked rather different in their architectures.
Linearly scanning the entire genome from ram for example, could be significantly better than performing multiple index lookups from disk.
Many problems of bioinformatics (the text processing) aren't that hard or special anymore, a genome is tiny compared to the amount of data we have lying around elsewhere.
BLAT[0] is the most obvious and preferred solution designed for alignment against a reference sequence- a 20 BP search against the human genome should essentially be instantaneous. BLAST [1] is more versatile and a bit slower than BLAT, but would also align these sequence sizes against the human genome in ~1-2 seconds, and is a traditional solution to the alignment problem, and has no license restrictions. BWA [2] and Bowtie [3] default settings could also be modified for the task (they're optimized for performing this task with larger strings on the order of thousands of times per second).
More generally, it would not be difficult to re-implement any of the algorithms behind these software implementations if the authors really wanted to. It's weird, this is the second post I've seen recently when software folks who are now working in the bioinformatics space have seemed completely unaware of both the basic algorithms we use in computational biology and their common implementations, like Smith-Waterman and Burrows–Wheeler. These are complicated problems with 40+ years of research behind them, and the actual solutions are elegant and fast algorithms which solve the problem in a far superior way within reasonable computational time.
[0] http://genome.ucsc.edu/cgi-bin/hgBlat
[1] http://blast.ncbi.nlm.nih.gov/
[2] http://bio-bwa.sourceforge.net/
[3] http://bowtie-bio.sourceforge.net/index.shtml