Reconfigurable architectures for bio-sequence database scanning on FPGAs

• Published in: IEEE transactions on circuits and systems. 2, Analog and digital signal processing Analog and digital signal processing, 2005-12, Vol.52 (12), p.851-855
• Main Authors: Oliver, T.F., Schmidt, B., Maskell, D.L.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Biomedical computing; Costs; database searching; Field programmable gate arrays; Hardware; Heuristic algorithms; Parallel processing; Performance gain; Proteins; Reconfigurable architectures; Studies
• ISSN: 1549-7747; 1057-7130; 1558-3791
• DOI: 10.1109/TCSII.2005.853340

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 the rapid growth in the size of these databases. In this paper, we present a new approach to bio-sequence database scanning using re-configurable field-programmable gate array (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 toward the parameters of a query have been designed. We use customization opportunities available at run time to dynamically reconfigure the PEs to make better use of available resources. Our FPGA implementation achieves a speedup of approximately 170 for linear gap penalties and 125 for affine gap penalties compared to a standard desktop computing platform. We show how run-time reconfiguration can be used to further improve performance.