SeqAlign: Hardware Acceleration of DNA Sequence Alignment • Hacker News Board

Re: SeqAlign: Hardware Acceleration of DNA Sequence Alignment

#11

Post by tensor » Sun, Oct 06, 2013, 9:33 AM UTC

epistasis wrote: post #7

tensor wrote: post #4

Earlier quoted context omitted.

As far as I know, people generally use more sophisticated algorithms that run on commodity hardware. I remember hearing about this many years ago, but never actually saw it in the wild.

Smith-Waterman is the "gold-standard," but for speedy heuristic DNA alignment these days, BWA and Bowtie are probably the two most common mappers, and they're both based on the ideas of the FM-index [1]. BLAST and BLAT were previously the two most commonly used, both hash-based aligners, and they're still used today for one-off database searches, as they are more accurate, particularly for long sequences. [1] http://…

If you are interested in high accuracy for highly diverged DNA, take a look at:

http://www.ncbi.nlm.nih.gov/pubmed/20733242 https://github.com/akhudek/feast

Sadly, I haven't seen this research be applied anywhere. I'm not sure if it's a lack of advertising, or that there is nothing interesting at extreme divergences.

Re: SeqAlign: Hardware Acceleration of DNA Sequence Alignment

#12

Post by hyperbovine » Sun, Oct 06, 2013, 2:05 PM UTC

epistasis wrote: post #7

tensor wrote: post #4

Earlier quoted context omitted.

As far as I know, people generally use more sophisticated algorithms that run on commodity hardware. I remember hearing about this many years ago, but never actually saw it in the wild.

Smith-Waterman is the "gold-standard," but for speedy heuristic DNA alignment these days, BWA and Bowtie are probably the two most common mappers, and they're both based on the ideas of the FM-index [1]. BLAST and BLAT were previously the two most commonly used, both hash-based aligners, and they're still used today for one-off database searches, as they are more accurate, particularly for long sequences. [1] http://…

But see: http://snap.cs.berkeley.edu. BWT-based aligners hark back to a time when it was not cheap to own enough RAM to store an entire (human) genome seed lookup table in memory. That is no longer the case (you need about 64gb). Also, hash aligners perform better as the read length increases.

Re: SeqAlign: Hardware Acceleration of DNA Sequence Alignment

#13

Post by epistasis » Sun, Oct 06, 2013, 3:15 PM UTC

hyperbovine wrote: post #12

epistasis wrote: post #7

Earlier quoted context omitted.

Smith-Waterman is the "gold-standard," but for speedy heuristic DNA alignment these days, BWA and Bowtie are probably the two most common mappers, and they're both based on the ideas of the FM-index [1]. BLAST and BLAT were previously the two most commonly used, both hash-based aligners, and they're still used today for one-off database searches, as they are more accurate, particularly for long sequences. [1] http://…

But see: http://snap.cs.berkeley.edu . BWT-based aligners hark back to a time when it was not cheap to own enough RAM to store an entire (human) genome seed lookup table in memory. That is no longer the case (you need about 64gb). Also, hash aligners perform better as the read length increases.

Well, BLAT for example also stores the entire seed table in memory, it just has to use fewer, shorter, and more frequently-occurring seeds. BWT requires something like two random RAM accesses per base pair, which is incredibly slow. With a large enough seed table, hash-based can get down to just a few random accesses per 100 base pair read.

Has SNAP been published? I had heard about it but not seen it used in practice anywhere.

Re: SeqAlign: Hardware Acceleration of DNA Sequence Alignment

#14

Post by epistasis » Sun, Oct 06, 2013, 7:14 PM UTC

hyperbovine wrote: post #12

epistasis wrote: post #7

Earlier quoted context omitted.

Smith-Waterman is the "gold-standard," but for speedy heuristic DNA alignment these days, BWA and Bowtie are probably the two most common mappers, and they're both based on the ideas of the FM-index [1]. BLAST and BLAT were previously the two most commonly used, both hash-based aligners, and they're still used today for one-off database searches, as they are more accurate, particularly for long sequences. [1] http://…

But see: http://snap.cs.berkeley.edu . BWT-based aligners hark back to a time when it was not cheap to own enough RAM to store an entire (human) genome seed lookup table in memory. That is no longer the case (you need about 64gb). Also, hash aligners perform better as the read length increases.

BTW, thank you for the pointer to the repository! I hadn't realized that it was publicly available at all. There's a few niceties that would be good, such as reading gzip directly (named pipes are a hassle). But also very cool that they're using HugeTLB, I'm always glad when good systems people apply themselves to bioinformatics, they can really squeeze the most out of recent machines!