The Smith-Waterman algorithm is used to determine the optimal local alignment between two nucleotide or protein sequences. The algorithm compares two sequences by computing the similarity score by means of dynamic programming.
CUDASW++
CUDASW++ is a bioinformatics software for Smith-Waterman protein database searches that takes advantage of the massively parallel CUDA architecture of NVIDIA Tesla GPUs to perform sequence searches 10x-50x faster than NCBI BLAST. In this algorithm, we deeply explore the SIMT (Single Instruction, Multiple Thread) and virtualized SIMD (Single Instruction, Multiple Data) abstractions to achieve fast speed. This algorithm has been fully tested on Tesla C1060, Tesla C2050, GeForce GTX 280 and GTX 295 graphics cards, and has been incorporated to NVIDIA Tesla Bio Workbench.
Download: Sourceforge; NVIDIA
Publications:
- Yongchao Liu, Douglas L. Maskell, Bertil Schmidt: "CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units". BMC Research Notes, 2009, 2:73
- Yongchao Liu, Bertil Schmidt, Douglas L. Maskell: "CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions". BMC Research Notes, 2010, 3:93
- Yongchao Liu, Adrianto Wirawan and Bertil Schmidt: "CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions". BMC Bioinformatics, 2013, 14:117
CBESW
CBESW demonstrates how the PlayStation® 3, powered by the Cell Broadband Engine, can be used as a computational platform to accelerate the Smith-Waterman algorithm. It also demonstrates that the PlayStation® 3 console can be used as an efficient low cost computational platform for high performance sequence alignment applications.For large datasets, our implementation on the PlayStation® 3 provides a significant improvement in running time compared to other implementations such as SSEARCH, Striped Smith-Waterman and CUDA. CBESW achieves a peak performance of up to 3.646 GCUPS. This performance is about 30x faster than the straightforward C-implementation in SSEARCH. It is also 1.64x faster than the highly optimized striped SW implementation on an Intel processor and 3x times faster than a CUDA implementation on an Nvidia GeForce 8800GTX.
Download: Sourceforge
Publications:
- Adrianto Wirawan, Chee Keong Kwoh, Tri Hieu Nim, Bertil Schmidt: "CBESW: Sequence Alignment on the Playstation 3". BMC Bioinformatics, 2008, 9:377