%0 Journal Article
%T A Systolic Array-Based FPGA Parallel Architecture for the BLAST Algorithm
%A Xinyu Guo
%A Hong Wang
%A Vijay Devabhaktuni
%J ISRN Bioinformatics
%D 2012
%R 10.5402/2012/195658
%X 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. 1. Introduction In the bioinformatics and computational biology (BCB) domain, biological sequence alignment is a quite common task. It includes comparison of DNA (nucleotide), RNA (nucleotide), and protein (amino acid) sequences. In such comparison, a query sequence is aligned to subject sequences from a large database to find similarities [1]. Scientists are used to adopting sequence alignment to infer biological information of a newly discovered sequence from a set of previously known sequences. For instance, if a recently discovered sequence is similar to a known disease gene, then the biological information about the functionality of the new sequence can be inferred. This is extremely meaningful in early disease diagnosis and drug engineering [2]. In addition, biological sequence alignment plays an important role in the study of evolutionary development and the history of species [3]. Being one of the most important tools applied in finding biological sequence alignment, BLAST (Basic Local Alignment Search Tool) [4] has been widely implemented on commodity PC clusters. But with the exponential growth of the biosequence databases (see Figure 1 [1]), meeting the computational requirements using current platforms is becoming a difficult task. Figure 1: Exponential growth of biological sequence database on a yearly basis. Compared to general-purpose PC microprocessors, Field Programmable Gate Arrays (FPGAs) are able to provide a much higher degree of bit-level data parallelism which leads to higher computational speed. In addition, FPGAs are re-programmable [5]. Scientists have been investigating parallel architecture design for the BLAST algorithm on FPGAs to achieve higher computational efficiency. This paper proposes a design and implementation of a parallel architecture on FPGA for BLAST, namely,
%U http://www.hindawi.com/journals/isrn.bioinformatics/2012/195658/