A Novel High-Throughput Acceleration Engine for Read Alignment

Author

Yu-Ting Chen ; Cong, Jason ; Jie Lei ; Peng Wei

Author_Institution

Comput. Sci. Dept., Univ. of California, Los Angeles, Los Angeles, CA, USA

fYear

2015

fDate

2-6 May 2015

Firstpage

199

Lastpage

202

Abstract

The Smith-Waterman (S-W) algorithm is widely adopted by the state-of-the-art DNA sequence aligners. Existing wave front-based methods ignored the fact that the S-W algorithm is fed with significantly varied-size inputs in modern aligners, in which the S-W algorithm is further optimized by exerting extensive pruning. In this paper, we propose an architecture, tailored for varied input sizes as well as harnessing software pruning strategies, to accelerate S-W. Our implementation demonstrates a 26.4x speedup over a 24-thread Intel Has well Xeon server, and outperforms wave front-based implementations by up to 6x with the same FPGA resource.

Keywords

DNA; biology computing; software engineering; 24-thread Intel Has well Xeon server; DNA sequence aligners; S-W algorithm; Smith-Waterman algorithm; high-throughput acceleration engine; read alignment; resource; software pruning strategy; varied-size inputs; wavefront-based methods; Algorithm design and analysis; Bioinformatics; Computer architecture; Field programmable gate arrays; Kernel; Parallel processing; FPGA; HLS; Smith-Waterman; multilevel scheduling; read alignment;

fLanguage

English

Publisher

ieee

Conference_Titel

Field-Programmable Custom Computing Machines (FCCM), 2015 IEEE 23rd Annual International Symposium on

Conference_Location

Vancouver, BC

Type

conf

DOI

10.1109/FCCM.2015.27

Filename

7160071