Performance evaluation of fast smith-waterman algorithm for sequence database searches using CUDA GPU-based parallel computing

Alhadi B., Giannina Ardaneswari, Hengki Tasman, Dian Lestari

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

In bioinformatics, one of the gold-standard algorithms to compute the optimal similarity score between sequences in a sequence database searches is Smith-Waterman algorithm that uses dynamic programming. This algorithm has a quadratic time complexity which requires a long computation time for large-sized data. In this issue, parallel computing is essential for sequence database searches in order to reduce the running time and to increase the performance. In this paper, we discuss the parallel implementation performance of Smith-Waterman algorithm in GPU using CUDA C programming language with NVCC compiler on Linux environment. Furthermore, we assess the performance analysis using three parallelization models, including Inter-task Parallelization, Intratask Parallelization, and a combination of both models. Based on the simulation results, a combination of both models has better performance than the others. In addition the parallelization using combination of both models achieves an average speed-up of 313× and an average efficiency with a factor of 0.93.

Original languageEnglish
Pages (from-to)38-46
Number of pages9
JournalJournal of Next Generation Information Technology
Volume5
Issue number2
Publication statusPublished - 1 Jan 2014

Keywords

  • CUDA GPU computing
  • Protein database searches
  • Smith-waterman sequence alignment

Fingerprint Dive into the research topics of 'Performance evaluation of fast smith-waterman algorithm for sequence database searches using CUDA GPU-based parallel computing'. Together they form a unique fingerprint.

Cite this