doi: 10.7873/DATE.2015.0983


FPGA Accelerated DNA Error Correction


Anand Ramachandran1,a, Yun Heo1,b, Wen-Mei Hwu1,c, Jian Ma2,3 and Deming Chen1,d

1Department of Electrical and Computer Engineering, University of Illinois at Urbana Champaign, Urbana, USA.

aaramach4@illinois.edu
byunheo1@illinois.edu
cw-hwu@illinois.edu
ddchen@illinois.edu

2Department of Bioengineering, University of Illinois at Urbana Champaign, Urbana, USA

3Institute for Genomic Biology, University of Illinois at Urbana Champaign, Urbana, USA.

jianma@illinois.edu

ABSTRACT

Correcting errors in DNA sequencing data is an important process that can improve the quality of downstream analysis using the data. Even though many error-correction methods have been proposed for Illumina reads, their throughput is not high enough to process data from large genomes. The current paper describes the first FPGA-based error-correction tool, called FPGA Accelerated DNA Error Correction (FADE), which targets to improve the throughput of DNA error correction for Illumina reads. The base algorithm of FADE is BLESS that is highly accurate but slow. A Bloom filter that is the main data structure of BLESS and BLESS' error correction subroutines for different types of errors have been implemented on a FPGA. We compared our design with the software version of BLESS using DNA sequencing data generated from four genomes and we could achieve up to 43 times speedup for the best case, and 36 times speedup on the average.

Keywords: FPGA, Bloom filter, DNA, Error correction.



Full Text (PDF)