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,
References
[1]
R. Durbin, S. Eddy, A. Krogh, and G. Mitchison, Biological Sequence Analysis: Probabilistic Models for Proteins and Nucleic Acids, Cambridge University Press, Cambridge UK, 1998.
[2]
J. Hein, “A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given,” Molecular Biology and Evolution, vol. 6, no. 6, pp. 649–668, 1989.
[3]
W. Bains, “MULTAN: a program to align multiple DNA sequences,” Nucleic Acids Research, vol. 14, no. 1, pp. 159–177, 1986.
[4]
S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, “Basic local alignment search tool,” Journal of Molecular Biology, vol. 215, no. 3, pp. 403–410, 1990.
[5]
M. Gokhale, B. Holmes, and K. Iobst, “Processing in memory: the terasys massively parallel PIM array,” Computer, vol. 28, no. 4, pp. 23–31, 1995.
[6]
S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” Journal of Molecular Biology, vol. 48, no. 3, pp. 443–453, 1970.
[7]
T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” Journal of Molecular Biology, vol. 147, no. 1, pp. 195–197, 1981.
[8]
S. F. Altschul, T. L. Madden, A. A. Sch？ffer et al., “Gapped BLAST and PSI-BLAST: a new generation of protein database search programs,” Nucleic Acids Research, vol. 25, no. 17, pp. 3389–3402, 1997.
[9]
M. C. Herbordt, J. Model, G. Yongfeng, B. Sukhwani, and T. VanCourt, “Single pass, BLAST-like, approximate string matching on FPGAs,” in Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06), pp. 217–226, April 2006.
[10]
S. Kasap, K. Benkrid, and Y. Liu, “Design and Implementation of an FPGA-based Core for Gapped BLAST Sequence Alignment with the Two-Hit Method,” Engineering Letters, vol. 16, no. 3, pp. 443–452, 2008.
[11]
T. Oliver, B. Schmidt, and D. Maskell, “Hyper customized processors for bio-sequence database scanning on FPGAs,” in Proceedings of the ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays (FPGA '05), pp. 229–237, February 2005.
[12]
J. D. Buhler and J. M. Lancaster, “Mercury BLASTN: faster DNA sequence comparison using a streaming hardware architecture,” in Proceedings of the 3rd Annual Reconfigurable Systems Summer Institute, 2007.
[13]
R. D. Chamberlain, R. K. Cytron, A. M. Franklin, and S. R. Indeck, “The Mercury system: exploiting truly fast hardware for data search,” in Proceedings of the International Workshop on Storage Network Architecture and Parallel I/Os, pp. 65–72, September 2003.
[14]
J. M. Lancaster and A. C. Jacob, “Mercury BLASTN,” in Proceedings of the 44th Design Automation Conference, 2007.
[15]
B. Harris, A. C. Jacob, J. M. Lancaster, J. Buhler, and R. D. Chamberlain, “A banded smith-waterman FPGA accelerator for mercury BLASTP,” in Proceedings of the 2007 International Conference on Field Programmable Logic and Applications (FPL'07), pp. 765–769, August 2007.
[16]
S. Datta, P. Beeraka, and R. Sass, “RC-BLASTn: implementation and evaluation of the BLASTn Scan function,” in Proceedings of the IEEE Symposium on Field Programmable Custom Computing Machines (FCCM '09), pp. 88–95, April 2009.
[17]
D. Lavenier, G. Georges, and X. Liu, “A reconfigurable index FLASH memory tailored to seed-based genomic sequence comparison algorithms,” Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, vol. 48, no. 3, pp. 255–269, 2007.
[18]
E. Sotiriades and A. Dollas, “Design space exploration for the BLAST algorithm implementation,” in Proceedings of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '07), pp. 323–325, April 2007.
[19]
E. Sotiriades and A. Dollas, “A general reconfigurable architecture for the BLAST algorithm,” Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, vol. 48, no. 3, pp. 189–208, 2007.
[20]
C. Chang, BLAST Implementation on BEE2, Electrical Engineering and Computer Science University of California, Berkeley, Calif, USA, 2005.
[21]
Mitrion. Inc, “NCBI BLAST Accelerator,” 2007.
[22]
D. Lavenier, X. Liu, and G. Georges, “Seed-based genomic sequence comparison using a FPGA/FLASH accelerator,” in Proceedings of the IEEE International Conference on Field Programmable Technology (FPT '06), pp. 41–48, December 2006.
[23]
Server at http://www.ece.neu.edu/ Port 80, http://www.ece.neu.edu/groups/rcl/projects/.
[24]
M. C. Herbordt, J. Model, B. Sukhwani, Y. Gu, and T. VanCourt, “Single pass streaming BLAST on FPGAs,” Parallel Computing, vol. 33, no. 10-11, pp. 741–756, 2007.
[25]
H. Abelsson, C. Sandberg, and S. Moh, “Accelerating on NCBI BLAST,” in Proceedings of the CUG Conference, Seattle, Wash, USA, May 2007.
[26]
A. Rao and A. Visakhapatanam, “A tool for pair-wise alignment algorithm,” Management Review, vol. 2, no. 1, pp. 28–40, 2007.
[27]
S. Che, J. Li, J. W. Sheaffer, K. Skadron, and J. Lach, “Accelerating compute-intensive applications with GPUs and FPGAs,” in Proceedings of the Symposium on Application Specific Processors (SASP '08), pp. 101–107, June 2008.
[28]
F. Xia, Y. Dou, and J. Xu, “Families of FPGA-based accelerators for BLAST algorithm with multi-seeds detection and parallel extension,” in Bioinformatics Research and Development, vol. 13 of Communications in Computer and Information Science, part 1-2, pp. 43–57, 2008.
