Przyśpieszenie algorytmu Smitha-Watermana z użyciem procesora graficznego

• Autorzy: Pawłowski R. , Mrozek D.

Warianty tytułu

EN

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

• Języki publikacji: PL

Abstrakty

PL

Wraz z wprowadzeniem przez firmę NVIDIA technologii CUDA wykorzystanie potencjału kart graficznych stało się łatwiejsze. W artykule przedstawiono metodę istotnego przyśpieszenia wykonania algorytmu Smitha-Watermana, znajdującego optymalne, lokalne dopasowanie dwóch sekwencji, takich jak sekwencje aminokwasów lub nukleotydów. Uzyskane wyniki sugerują, że możliwe jest dokładne przeszukiwanie bioinformatycznych baz danych w rozsądnym czasie.

EN

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.

Słowa kluczowe

PL

bioinformatyka; architektura CUDA; algorytm Smitha-Watermana; CUDA

EN

bioinformatics; CUDA architecture; Smith-Waterman algorithm; CUDA

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2011
• Tom: Vol. 32, nr 2A
• Strony: 181--198
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Pawłowski R.

autor

Mrozek D.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice,

Bibliografia

• 1. 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.
• 2. 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
• 3. Farrar M.: Striped Smith–Waterman speeds database searches six times over other SIMD implementations. Bioinformatics, Vol. 23, No. 2, 2007, s. 156‚161.
• 4. GenomeNet. http://www.genome.jp/en/db_growth.html.
• 5. 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.
• 6. 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.
• 7. 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.
• 8. 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.
• 9. Mount D. W.: Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, 2001.
• 10. NVIDIA CUDA programming guide 2.3. http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf.
• 11. NVIDIA. http://www.nvidia.pl/object/cuda_home_new_pl.html.
• 12. 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.
• 13. Smith T. F., Waterman M. S.: Identification of common molecular subsequences. Journal of Molecular Biology, Vol. 147, 1981, s. 195‚197.
• 14. 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.