Maybe you were thinking of something like Aho-Corasick or Knuth-Morris-Pratt or Boyer-Moore? We really need better names for these algorithms. For example, by the authority vested in me by my own hubris, I hereby rename Rabin-Karp to "rolling hash search". Aho-Corasick is now "substring-trie search". Much easier to remember!
There is a string search based on the BWT which is used for most DNA read mapping these days due to its favorable performance compared to existing hash based algorithms.
Company I work at (in HPC) was in negotiations to implement it for one of those big plant biotech firms long before I was around, or so I have been told.
General alignment definitely is quite different, however The vast majority of sequence data that's produced these days are short reads. Read-mapping is a much lower-bar and more similar to string search than proper sequence alignment. The BWT-based search [1] is a bit more practical with the small alphabet size of DNA compared to most human texts, however.
Comments
Does this beat burrows wheeler?
The Burrows-Wheeler transform is something completely unrelated.
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo...
Maybe you were thinking of something like Aho-Corasick or Knuth-Morris-Pratt or Boyer-Moore? We really need better names for these algorithms. For example, by the authority vested in me by my own hubris, I hereby rename Rabin-Karp to "rolling hash search". Aho-Corasick is now "substring-trie search". Much easier to remember!
There is a string search based on the BWT which is used for most DNA read mapping these days due to its favorable performance compared to existing hash based algorithms.
You are probably thinking of Smith-Waterman:
http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorith...
Company I work at (in HPC) was in negotiations to implement it for one of those big plant biotech firms long before I was around, or so I have been told.
Smith-Waterman is the gold standard, but it's too slow for most applications so many heuristics have been developed.
BWA is the most popular tool these days for short-read mapping, and has a Smith-Waterman based approach for long reads as well:
http://bio-bwa.sourceforge.net/bwa.shtml
Sequence alignment and string search are different enough problems that we really should distinguish between them.
General alignment definitely is quite different, however The vast majority of sequence data that's produced these days are short reads. Read-mapping is a much lower-bar and more similar to string search than proper sequence alignment. The BWT-based search [1] is a bit more practical with the small alphabet size of DNA compared to most human texts, however.
http://people.unipmn.it/manzini/papers/focs00draft.pdf
So can any of here other string search algos be used for DNA mapping?
Asymptotically, string search based on the BWT is worst-case O(m+n).