A Systolic Array-Based FPGA Parallel Architecture for the BLAST Algorithm

Xinyu Guo; Hong Wang; Vijay Devabhaktuni

doi:10.5402/2012/195658

A Systolic Array-Based FPGA Parallel Architecture for the BLAST Algorithm

ISRN Bioinform. 2012 Sep 4:2012:195658. doi: 10.5402/2012/195658. eCollection 2012.

Authors

Xinyu Guo¹, Hong Wang², Vijay Devabhaktuni¹

Affiliations

¹ Electrical Engineering and Computer Science Department, The University of Toledo, MS.308, 2801 W. Bancroft Street, Toledo, OH 43607, USA.
² Department of Engineering Technology, The University of Toledo, MS.402, 2801 W. Bancroft Street, Toledo, OH 43606, USA.

Abstract

A design of systolic array-based Field Programmable Gate Array (FPGA) parallel architecture for Basic Local Alignment Search Tool (BLAST) Algorithm is proposed. BLAST is a heuristic biological sequence alignment algorithm which has been used by bioinformatics experts. In contrast to other designs that detect at most one hit in one-clock-cycle, our design applies a Multiple Hits Detection Module which is a pipelining systolic array to search multiple hits in a single-clock-cycle. Further, we designed a Hits Combination Block which combines overlapping hits from systolic array into one hit. These implementations completed the first and second step of BLAST architecture and achieved significant speedup comparing with previously published architectures.