{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T10:18:46Z","timestamp":1769854726267,"version":"3.49.0"},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>This design of FPGA accelerated hardware offers a new promising direction to seeking computation improvement of genomic database searching.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-8-185","type":"journal-article","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T18:14:02Z","timestamp":1181240042000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":98,"title":["160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA)"],"prefix":"10.1186","volume":"8","author":[{"given":"Isaac TS","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Warren","family":"Shum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Truong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,7]]},"reference":[{"issue":"1","key":"1557_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS: Identification of common molecular subsequences. J Mol Biol 1981, 147(1):195\u2013197.","journal-title":"J Mol Biol"},{"issue":"9","key":"1557_CR2","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1093\/bioinformatics\/14.9.819","volume":"14","author":"RD Page","year":"1998","unstructured":"Page RD: GeneTree: comparing gene and species phylogenies using reconciled trees. Bioinformatics 1998, 14(9):819\u2013820.","journal-title":"Bioinformatics"},{"issue":"4693","key":"1557_CR3","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1126\/science.2983426","volume":"227","author":"DJ Lipman","year":"1985","unstructured":"Lipman DJ, Pearson WR: Rapid and sensitive protein similarity searches. Science 1985, 227(4693):1435\u20131441.","journal-title":"Science"},{"issue":"3","key":"1557_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic local alignment search tool. J Mol Biol 1990, 215(3):403\u2013410.","journal-title":"J Mol Biol"},{"issue":"6","key":"1557_CR5","first-page":"473","volume":"12","author":"R Hughey","year":"1996","unstructured":"Hughey R: Parallel hardware for sequence comparison and alignment. Comput Appl Biosci 1996, 12(6):473\u2013479.","journal-title":"Comput Appl Biosci"},{"key":"1557_CR6","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1145\/109025.109081","volume-title":"Proceedings of the 5th international conference on Supercomputing","author":"ET Chow","year":"1991","unstructured":"Chow ET, Peterson JC, Waterman MS, Hunkapiller T, Zimmermann BA: A systolic array processor for biological information signal processing. Proceedings of the 5th international conference on Supercomputing 1991, 216\u2013223."},{"key":"1557_CR7","first-page":"336","volume-title":"Proceedings of Application Specific Array Processors","author":"M Borah","year":"1994","unstructured":"Borah M, Bajwa RS, Hannenhalli S, Irwin MJ: A SIMD solution to the sequence comparison problem on the MGAP. Proceedings of Application Specific Array Processors 1994, 336\u2013345."},{"issue":"8","key":"1557_CR8","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1093\/bioinformatics\/16.8.699","volume":"16","author":"T Rognes","year":"2000","unstructured":"Rognes T, Seeberg E: Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics 2000, 16(8):699\u2013706.","journal-title":"Bioinformatics"},{"issue":"8","key":"1557_CR9","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1093\/bioinformatics\/16.8.665","volume":"16","author":"R Giegerich","year":"2000","unstructured":"Giegerich R: A systematic approach to dynamic programming in bioinformatics. Bioinformatics 2000, 16(8):665\u2013677.","journal-title":"Bioinformatics"},{"issue":"2","key":"1557_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","volume":"23","author":"M Farrar","year":"2007","unstructured":"Farrar M: Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics 2007, 23(2):156\u2013161.","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-185.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T07:47:37Z","timestamp":1683877657000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-185"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,7]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1557"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-185","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,7]]},"assertion":[{"value":"19 February 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"185"}}