5 ms·

Does this beat burrows wheeler?

pjscott 15y ago
The Burrows-Wheeler transform is something completely unrelated. http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform 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!
- epistasis 15y ago
  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.
  - tocomment 15y ago
    So can any of here other string search algos be used for DNA mapping?
  - ahelwer 15y ago
    You are probably thinking of Smith-Waterman: http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm 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.
    - epistasis 15y ago
      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 http://bio-bwa.sourceforge.net/bwa.shtml
  - pjscott 15y ago
    Sequence alignment and string search are different enough problems that we really should distinguish between them.
    - epistasis 15y ago
      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 http://people.unipmn.it/manzini/papers/focs00draft.pdf
rcthompson 15y ago
Asymptotically, string search based on the BWT is worst-case O(m+n).

The Burrows-Wheeler transform is something completely unrelated. http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform 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!

epistasis 15y ago
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.
- tocomment 15y ago
  So can any of here other string search algos be used for DNA mapping?
- ahelwer 15y ago
  You are probably thinking of Smith-Waterman: http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm 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.
  - epistasis 15y ago
    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 http://bio-bwa.sourceforge.net/bwa.shtml
- pjscott 15y ago
  Sequence alignment and string search are different enough problems that we really should distinguish between them.
  - epistasis 15y ago
    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 http://people.unipmn.it/manzini/papers/focs00draft.pdf

rcthompson 15y ago

Asymptotically, string search based on the BWT is worst-case O(m+n).