160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA)
Open Access
- 7 June 2007
- journal article
- Published by Springer Science and Business Media LLC in BMC Bioinformatics
- Vol. 8 (1), 185
- https://doi.org/10.1186/1471-2105-8-185
Abstract
Background: To infer homology and subsequently gene function, the Smith-Waterman (SW) algorithm is used to find the optimal local alignment between two sequences. When searching sequence databases that may contain hundreds of millions of sequences, this algorithm becomes computationally expensive.Results: In this paper, we focused on accelerating the Smith-Waterman algorithm by using FPGA-based hardware that implemented a module for computing the score of a single cell of the SW matrix. Then using a grid of this module, the entire SW matrix was computed at the speed of field propagation through the FPGA circuit. These modifications dramatically accelerated the algorithm's computation time by up to 160 folds compared to a pure software implementation running on the same FPGA with an Altera Nios II softprocessor.Conclusion: This design of FPGA accelerated hardware offers a new promising direction to seeking computation improvement of genomic database searching.Keywords
This publication has 9 references indexed in Scilit:
- Striped Smith–Waterman speeds database searches six times over other SIMD implementationsBioinformatics, 2006
- A systematic approach to dynamic programming in bioinformaticsBioinformatics, 2000
- Six-fold speed-up of Smith–Waterman sequence database searches using parallel processing on common microprocessorsBioinformatics, 2000
- GeneTree: comparing gene and species phylogenies using reconciled trees.Bioinformatics, 1998
- Parallel hardware for sequence comparison and alignmentBioinformatics, 1996
- A systolic array processor for biological information signal processingPublished by Association for Computing Machinery (ACM) ,1991
- Basic local alignment search toolJournal of Molecular Biology, 1990
- Rapid and Sensitive Protein Similarity SearchesScience, 1985
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981