Friday, 3 September 2010

SeqAlign, an FPGA-based accelerator for the two common DNA Sequence alignment algorithms: Smith-Waterman (for local alignments) and Needleman-Wunsch (for global alignments).

Using FPGA for seq align is  a new concept to me, making a board do alignment of reads!
Now most computers only have one processor, so we can’t really take advantage of this. Fortunately, wonderful little devices called Field-Programmable Gate Arrays exist (see my Non-Von1 for another fun example), that let you make your own computer circuitry. Imagine if we could build an array of processors, connected in a line, where each processor holds one “nucleotide” from the top sequence. We could then “feed” in the sequence from one side, and calculate the entire matrix just like in the picture above! This is called a “systolic array“, and is an awesome way to compute a matrix!

This is the dev kit which I found on amazon (? no idea amazon sold such stuff)

it does have some limitations in its current guise
The USB interface to this board does indeed suck. It takes less than 5 microseconds to compute the whole matrix, but initiating a driver call from windows to send a byte to the device takes a whopping 370 microseconds!! Oy! Fortunately, there are tricks you can play! Thanks to the use of FIFOs, buffering and the creative application of backpressuring, I was able to sustain about 1.8 GCUPS on this bad boy! 

Check out: The SeqAlign project


No comments:

Post a Comment

Datanami, Woe be me