Accelerating Smith-Waterman algorithm with the use of graphics processing unit

Robert Pawłowski, Dariusz Mrozek

Abstract


CUDA is a technology introduced by NVIDIA Corporation, which allows software developers to take advantage of GPU resources relatively easily. This paper presents an approach leading to significant acceleration of the execution of the Smith-Waterman algorithm. The algorithm finds the best local alignment of two sequences, such as amino acid or nucleotide sequences. The results show that it is possible to search bio-informatics databases accurately within a reasonable time.

Keywords


bioinformatics; CUDA architecture; Smith-Waterman algorithm; CUDA

Full Text:

PDF (Polski)

References


Altschul S. F., Gish W., Miller W., Myers E. W., Lipman D. J.: Basic Local Alignment Search Tool. Journal of Molecular Biology, Vol. 215, 1990, s. 403‚410.

Boyer M., Skadron K., Weimer W.: Automated Dynamic Analysis of CUDA Programs. University of Virginia, USA, 2008. http://www.nvidia.com/docs/IO/67190/stmcs08.pdf. Przyspieszenie algorytmu Smitha-Watermana z uGyciem procesora graficznego 197

Farrar M.: Striped Smith–Waterman speeds database searches six times over other SIMD implementations. Bioinformatics, Vol. 23, No. 2, 2007, s. 156‚161.

GenomeNet. http://www.genome.jp/en/db_growth.html.

Gough E. S., Kane M. D.: Evaluating Parallel Computing Systems in Bioinformatics. Proceedings of the Third International Conference on Information Technology: New Generations, Las Vegas, NV 2006, s. 233‚238.

Liu Y., Maskell D., Schmidt B.: CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Research Notes, Vol. 2:73, 2009, s. 1‚10.

Liu Y., Maskell D., Schmidt B.: CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC Research Notes, Vol. 3:93, 2010, s. 1‚12.

Manavski S. A., Valle G.: CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics, Vol. 9, 2008, s. 1‚9.

Mount D. W.: Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, 2001.

NVIDIA CUDA programming guide 2.3. http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf.

NVIDIA. http://www.nvidia.pl/object/cuda_home_new_pl.html.

Pearson W. R., Lipman D. J.: Improved tools for biological sequence analysis. Proceedings of the National Academy of Sciences, Vol. 85, 1988, s. 2444‚2448.

Smith T. F., Waterman M. S.: Identification of common molecular subsequences. Journal of Molecular Biology, Vol. 147, 1981, s. 195‚197.

Striemer G. M., Akoglu A.: Sequence Alignment with GPU: Performance and Design Challenges. IPDPS, IEEE International Symposium on Parallel & Distributed Processing, 2009, s. 1‚10.




DOI: http://dx.doi.org/10.21936/si2011_v32.n2A.259