Re:Faster string searching and matching with Rabin-Karp algo...
by tocomment on Friday April 06, 2012 @10:20PM
(#3809745)
Does this beat burrows wheeler?
[ Parent
| on HN ]
Re:Faster string searching and matching with Rabin-Karp algo...
by pjscott on Saturday April 07, 2012 @12:16AM
(#3809950)
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!
Re:Faster string searching and matching with Rabin-Karp algo...
by epistasis on Saturday April 07, 2012 @01:12AM
(#3810040)
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.
Re:Faster string searching and matching with Rabin-Karp algo...
by ahelwer on Saturday April 07, 2012 @11:31AM
(#3811110)
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.
Re:Faster string searching and matching with Rabin-Karp algo...
by epistasis on Monday April 09, 2012 @06:32PM
(#3819612)
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:
Re:Faster string searching and matching with Rabin-Karp algo...
by pjscott on Sunday April 08, 2012 @02:47AM
(#3813290)
Sequence alignment and string search are different enough problems that we really should distinguish between them.
Re:Faster string searching and matching with Rabin-Karp algo...
by epistasis on Monday April 09, 2012 @06:36PM
(#3819635)
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.
Re:Faster string searching and matching with Rabin-Karp algo...
by tocomment on Saturday April 07, 2012 @09:08AM
(#3810764)
So can any of here other string search algos be used for DNA mapping?
Re:Faster string searching and matching with Rabin-Karp algo...
by rcthompson on Saturday April 07, 2012 @03:47AM
(#3810269)
Asymptotically, string search based on the BWT is worst-case O(m+n).