4 ms·
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 al
by 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 agoSo can any of here other string search algos be used for DNA mapping?
- ahelwer 15y agoYou 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 agoSmith-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 agoSequence alignment and string search are different enough problems that we really should distinguish between them.
- epistasis 15y agoGeneral 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