CUDASW++: Optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units

被引：127

作者：

Liu Y. ^{[1
]}

Maskell D.L. ^{[1
]}

Schmidt B. ^{[1
]}

机构：

[1] School of Computer Engineering, Nanyang Technological University, Singapore

来源：

BMC Research Notes | / 2卷 / 1期

关键词：

Query Sequence; Global Memory; Thread Block; Constant Memory; Subject Sequence;

D O I：

10.1186/1756-0500-2-73

中图分类号：

学科分类号：

摘要：

Background. The Smith-Waterman algorithm is one of the most widely used tools for searching biological sequence databases due to its high sensitivity. Unfortunately, the Smith-Waterman algorithm is computationally demanding, which is further compounded by the exponential growth of sequence databases. The recent emergence of many-core architectures, and their associated programming interfaces, provides an opportunity to accelerate sequence database searches using commonly available and inexpensive hardware. Findings. Our CUDASW++ implementation (benchmarked on a single-GPU NVIDIA GeForce GTX 280 graphics card and a dual-GPU GeForce GTX 295 graphics card) provides a significant performance improvement compared to other publicly available implementations, such as SWPS3, CBESW, SW-CUDA, and NCBI-BLAST. CUDASW++ supports query sequences of length up to 59K and for query sequences ranging in length from 144 to 5,478 in Swiss-Prot release 56.6, the single-GPU version achieves an average performance of 9.509 GCUPS with a lowest performance of 9.039 GCUPS and a highest performance of 9.660 GCUPS, and the dual-GPU version achieves an average performance of 14.484 GCUPS with a lowest performance of 10.660 GCUPS and a highest performance of 16.087 GCUPS. Conclusion. CUDASW++ is publicly available open-source software. It provides a significant performance improvement for Smith-Waterman-based protein sequence database searches by fully exploiting the compute capability of commonly used CUDA-enabled low-cost GPUs. © 2009 Liu et al; licensee BioMed Central Ltd.

引用

共 19 条

[1]

Smith T., Waterman M., Identification of common molecular subsequences, J Molecular Biology, 147, pp. 195-197, (1981)

[2]

Gotoh O., An improved algorithm for matching biological sequences, J Mol Biol, 162, pp. 707-708, (1982)

[3]

Pearson W.R., Lipman D.J., Improved tools for biological sequence comparison, Proc Nat Acad Sci USA, 85, 8, pp. 2444-2448, (1988)

[4]

Altschul S.F., Gish W., Miller W., Myers E.W., Lipman D.J., Basical local alignment search tool, J Mol Biol, 215, 3, pp. 403-410, (1990)

[5]

Altschul S.F., Madden T.L., Schaffer A.A., Zhang J., Zhang Z., Miller W., Lipman D.J., Gapped BLAST and PSI-BLAST: A new generation of protein database search programs, Nucleic Acids Research, 25, 17, pp. 3389-3402, (1997)

[6]

Oliver T., Schmidt B., Nathan D., Clemens R., Maskell D., Using reconfigurable hardware to accelerate multiple sequence alignment with ClustalW, Bioinformatics, 21, 16, pp. 3431-3432, (2005)

[7]

Oliver T.F., Schmidt B., Maskell D.L., Reconfigurable architectures for bio-sequence database scanning on FPGAs, IEEE Transactions on Circuits and Systems II: Express Briefs, 52, 12, pp. 851-855, (2005)

[8]

Li T.I., Shum W., Truong K., 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA), BMC Bioinformatics, 8, (2007)

[9]

Farrar M., Striped Smith-Waterman speeds database searches six times over other SIMD implementations, Bioinformatics, 23, 2, pp. 156-161, (2007)

[10]

Szalkowski A., Ledergerber C., Krahenbuhl P., Dessimoz C., SWPS3 - Fast multi-threaded vectorized Smith-Waterman for IBM Cell/B.E. and x86/SSE2, BMC Research Notes, 1, (2008)

← 1 2 →