SeqAlign: Hardware Acceleration of DNA Sequence Alignment

http://www.chrisfenton.com/seqalign/

by luu • 13 years ago

35 13 13 years ago

dalke• 13 years ago

Did anything ever become of that work? Based on the project link to http://opencores.org/websvn,listing,seqalign , I see that that the last modification time is 2009-08-17 18:21:06 GMT, so it's been 4 years.

BTW, there are more details at http://chrisfenton.com/wp-content/uploads/2009/08/final_repo... , which has a date one day before the above "last modified" time.

tensor2• 13 years ago

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.

epistasis4• 13 years ago

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://en.wikipedia.org/wiki/FM-index

oakwhiz• 13 years ago

I wonder if it would somehow be possible to use this with the protein folding game Foldit. http://fold.it/portal/

Some puzzles start off with a sequence alignment phase.

epistasis4• 13 years ago

These particular algorithms are commonly used with proteins' amino acid sequences for general database searches. But since the database of protein sequences is far far smaller than typical DNA search problems, there are more sophisticated and computationally expensive algorithms such as Pair HMMs [1] or Profile HMMs [2] can be used, and for fine tuning of 3D model threading they would be a much better option, since the problem is so small.

[1] http://ai.stanford.edu/~serafim/CS262_2008/notes/lecture8.pd...

[2] http://www.biology.wustl.edu/gcg/hmmanalysis.html

kevinwuhoo• 13 years ago

Structural alignment algorithms are (generally) much different and is a much more difficult problem. The "most popular" (at least in my experience) methods are combinatorial extension [1] and DALI [2]. But I'm sure it could be done, no doubt about it. However, most people, probably besides ones at the PDB, usually don't do massive structural alignment tasks. The effort to develop and maintain such a device probably isn't feasible.

[1] http://peds.oxfordjournals.org/content/11/9/739

[2] http://www.sciencemag.org/content/273/5275/595

TheLegace• 13 years ago

I'm curious what people would think if they had this in their computers, laptops, game systems. So they could actively choose to help large scale computation for DNA sequencing or any other big scientific problem they could lend computation to.

gren• 13 years ago

Yeah! like some hidden script in popular websites doing some computation with WebCL

usamec• 13 years ago

It is much better to speed to aligment using heuristics (e.g. use hashing for find matching kmers and do dynamic programming only on small portion of data) than by using faster hardware. Look here: http://bowtie-bio.sourceforge.net/index.shtml or here: http://mummer.sourceforge.net/

SeqAlign: Hardware Acceleration of DNA Sequence Alignment

Related Stories