6533b7d4fe1ef96bd1262693

RESEARCH PRODUCT

Accelerating short read mapping on an FPGA (abstract only)

subject

description

The explosive growth of short read datasets produced by high throughput DNA sequencing technologies poses a challenge to the mapping of short reads to a reference genome in terms of sensitivity and execution speed. Existing methods often use a restrictive error model for computing the alignments to improve speed, whereas more flexible error models are generally too slow for large-scale applications. Although a number of short read mapping software tools have been proposed, designs based on hardware are relatively rare. In this paper, we present a hybrid system for short read mapping utilizing both software and field programmable gate array (FPGA)-based hardware. The compute intensive semi-global alignment operation is accelerated on the FPGA. The proposed FPGA aligner is implemented with a parallel block structure to gain computational efficiency. We also propose a block-wise alignment algorithm to approximate the score of the conventional dynamic programming algorithm. Our performance comparison shows that the FPGA achieves an average speedup of 38 for the alignment operation on a Xilinx Virtex5 FPGA compared to the GASSST software implementation. For the overall execution time, our hybrid system achieves an average speedup of 2.4 compared to GASSST at comparable sensitivity and an average speedup of 1.8 compared to the popular BWA software at a significantly better sensitivity.