Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1508128.1508169acmconferencesArticle/Chapter ViewAbstractPublication PagesfpgaConference Proceedingsconference-collections
short-paper

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

Published: 22 February 2009 Publication History

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]
Gokhale, M. et al. "Processing in memory: The Terasys massively parallel PIM array", Computer, 28 (4), pp. 23--31, April 1995.
[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.

Cited By

View all
  • (2013)FPGA-based hardware acceleration for local complexity analysis of massive genomic dataIntegration, the VLSI Journal10.1016/j.vlsi.2012.10.00346:3(230-239)Online publication date: 1-Jun-2013
  • (2012)Towards systolic hardware acceleration for local complexity analysis of massive genomic dataProceedings of the great lakes symposium on VLSI10.1145/2206781.2206864(339-344)Online publication date: 3-May-2012
  • (2011)Bridging the GPGPU-FPGA efficiency gapProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950439(119-122)Online publication date: 27-Feb-2011
  • Show More Cited By

Index Terms

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

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays
      February 2009
      302 pages
      ISBN:9781605584102
      DOI:10.1145/1508128
      • General Chair:
      • Paul Chow,
      • Program Chair:
      • Peter Cheung
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 22 February 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. blast
      2. fpga
      3. handel c
      4. psi-blast

      Qualifiers

      • Short-paper

      Conference

      FPGA '09
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 125 of 627 submissions, 20%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)7
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 25 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2013)FPGA-based hardware acceleration for local complexity analysis of massive genomic dataIntegration, the VLSI Journal10.1016/j.vlsi.2012.10.00346:3(230-239)Online publication date: 1-Jun-2013
      • (2012)Towards systolic hardware acceleration for local complexity analysis of massive genomic dataProceedings of the great lakes symposium on VLSI10.1145/2206781.2206864(339-344)Online publication date: 3-May-2012
      • (2011)Bridging the GPGPU-FPGA efficiency gapProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950439(119-122)Online publication date: 27-Feb-2011
      • (2011)Design of a FPGA-Based Parallel Architecture for BLAST Algorithm with Multi-hits DetectionProceedings of the 2011 Eighth International Conference on Information Technology: New Generations10.1109/ITNG.2011.122(689-694)Online publication date: 11-Apr-2011
      • (2011)Tile optimization for area in FPGA based hardware acceleration of peptide identification2011 6th International Conference on Industrial and Information Systems10.1109/ICIINFS.2011.6038056(140-145)Online publication date: Aug-2011
      • (2011)Massively parallel FPGA-based implementation of BLASTp with the two-hit methodProcedia Computer Science10.1016/j.procs.2011.04.2154(1967-1976)Online publication date: 2011

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media