A high performance fpga-based implementation of position specific iterated blast

ABSTRACT

We present in this paper the first reported FPGA implementation of the Position Specific Iterated BLAST (PSI-BLAST) algorithm. The latter is a heuristic biological sequence alignment algorithm that is widely used in the bioinformatics and computational biology world in order to detect weak homologs. The architecture of our FPGA implementation is parameterized in terms of sequence lengths, scoring matrix, gap penalties and cut-off and threshold values. It is composed of various blmocks each of which performs one step of the algorithm in parallel. This results in high performance implementations, which easily outperform equivalent software implementations by one order of magnitude or more. Furthermore, the core was captured in an FPGA-platform-independent language, namely the Handel-C language, to which no specific resource inference or placement constraints were applied. This makes our core portable across different FPGA families and architectures.

REFERENCES

• 1: Durbin, R., Eddy, S., Krogh, A., and Mitchison, G., "Biological Sequence Analysis: Probabilistic Models for Proteins and Nucleic Acids", Cambridge University Press, Cambridge UK, 1998.
• 2: Hein, J. "A New Methodology that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when a phylogeny is given". Journal of Molecular Biology, 6, pp.649--668, 1989.
• 3: Hoang, D.T. "Searching genetic databases on Splash 2", in Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines, pp. 185--191, 1993.
• 4: Maya Gokhale , Bill Holmes , Ken Iobst, Processing in Memory: The Terasys Massively Parallel PIM Array, Computer, v.28 n.4, p.23-31, April 1995 [doi>10.1109/2.375174]
• 5: TimeLogic Corporation, "Decypher Scalable, High Performance Biocomputing Solutions", http://www.timelogic.com.
• 6: Altschul, S. F., Gish, W., Miller, W., Myers, E.W. and Lipman, D.J. "Basic Local Alignment Search Tool", Journal of Molecular Biology,215, pp. 403--410, 1990.
• 7: Kasap, S., Benkrid, K., Liu, Y., "Design and Implementation of an FPGA-based Core for Gapped BLAST Sequence Alignment with the Two-Hit Method", Engineering Letters, Vol. 16, Issue: 3, pp. 443--452,2008.
• 8: Altschul, S. F., Madden, T. L., Schaffer, A. A., Zhang, J., Zhang, Z., Miller, W., and Lipman, D. J. "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs", Nucleic Acid Research, Oxford Journals, 25(17), pp. 3389--3402, 1997.
• 9: Yi-Kuo Yu, John C. Wootton, and Stephen F. Altschul, "The compositional adjustment of amino acid substitution matrices", PNAS, Vol. 100, no 26, pp. 15688--15693, December, 2003.
• 10: RCHTX FPGA Board Reference Manual, Celoxica Plc, http://www.celoxica.com.
• 11: Boeckmann, B., et al., "The SWISS-PROT protein knowledgebase and its supplement TrEMBL" in 2003 Nucleic Acids Research, Vol.31, pp. 365--370, 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.0 General

Additional Classification:
  B. Hardware
  B.0 GENERAL
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays; Combinational logic; Sequential circuits; Parallel circuits

General Terms:
Algorithms, Design

Keywords:
blast, fpga, handel c, psi-blast