Hyper customized processors for bio-sequence database scanning on FPGAs
Authors:
Open Access
- 20 February 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 229-237
Abstract
Protein sequences with unknown functionality are often compared to a set of known sequences to detect functional similarities. Efficient dynamic-programming algorithms exist for solving this problem, however current solutions still require significant scan times. These scan time requirements are likely to become even more severe due to exponential database growth. In this paper we present a new approach to bio-sequence database scanning using re-configurable FPGA-based hardware platforms to gain high performance at low cost. Efficient mappings of the Smith-Waterman algorithm using fine-grained parallel processing elements (PEs) that are tailored towards the parameters of a query have been designed. We use customization opportunities available at run-time to dynamically hyper customize the systolic array to make better use of available resource. Our FPGA implementation achieves a speedup of approximately 170 for linear gap penalties and 125 for affine gap penalties as compared to a standard desktop computing platform. We show how hyper-customization at run-time can be used to further improve the performance.Keywords
This publication has 10 references indexed in Scilit:
- A Smith-Waterman Systolic Cell2003
- Searching genetic databases on Splash 22002
- A SIMD solution to the sequence comparison problem on the MGAP2002
- Biological information signal processor2002
- Parallel Processing for Scanning Genomic Data-Bases1998
- Comparison of methods for searching protein sequence databasesProtein Science, 1995
- Processing in memory: the Terasys massively parallel PIM arrayComputer, 1995
- Basic local alignment search toolJournal of Molecular Biology, 1990
- P-NAC: A Systolic Array for Comparing Nucleic Acid SequencesComputer, 1987
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981