Title :
Accelerating Phylogeny-Aware Short DNA Read Alignment with FPGAs
Author :
Alachiotis, Nikolaos ; Berger, Simon A. ; Stamatakis, Alexandros
Author_Institution :
Exelixis Lab., Heidelberg Inst. for Theor. Studies, Heidelberg, Germany
Abstract :
Recent advances in molecular sequencing technology have given rise to novel algorithms for simultaneously aligning short sequence reads to reference sequence alignments and corresponding evolutionary reference trees. We present a complete hardware/software implementation for the acceleration of a program called PaPaRa, a newly introduced dynamic programming algorithm for this purpose. We verify the correctness of the proposed architecture on a real FPGA and introduce a straight-forward communication protocol(using gigabit ethernet) for seamless integration with the encapsulating steering software that is executed on a PC processor. The hardware description and the software implementation are freely available for download. When mapped to a Virtex 6 FPGA, our reconfigurable architecture can compute 133.4 billion cell updates per second for the novel, tree-based alignment kernel of PaPaRa. Compared to PaPaRa, running on a 3.2GHz Intel Core i5 CPU, we obtain speedups for the alignment kernel, that range between 170 and 471. For the entire application, that is, the alignment kernel and the trace-back step, we obtain speedups between 74 and 118.
Keywords :
DNA; biology computing; dynamic programming; field programmable gate arrays; genetic engineering; hardware-software codesign; reconfigurable architectures; PC processor; PaPaRa program; Virtex 6 FPGA; communication protocol; dynamic programming algorithm; evolutionary reference trees; gigabit ethernet; hardware-software implementation; molecular sequencing technology; phylogeny-aware short DNA read alignment; reconfigurable architecture; reference sequence alignments; tree-based alignment kernel; Acceleration; Computer architecture; Dynamic programming; Field programmable gate arrays; Kernel; Microprocessors; Phylogeny; FPGA; dynamic programming; multiple alignment; phylogenetic inference;
Conference_Titel :
Field-Programmable Custom Computing Machines (FCCM), 2011 IEEE 19th Annual International Symposium on
Conference_Location :
Salt Lake City, UT
Print_ISBN :
978-1-61284-277-6
Electronic_ISBN :
978-0-7695-4301-7
DOI :
10.1109/FCCM.2011.13