Serial and parallel implementation of Needleman-Wunsch algorithm

International Journal of Advances in Intelligent Informatics

View Publication Info
 
 
Field Value
 
Title Serial and parallel implementation of Needleman-Wunsch algorithm
 
Creator Lee, Yun Sup
Kim, Yu Sin
Uy, Roger Luis
 
Subject Bioinformatics; Global alignment; Needleman-wunsch; GPU; CUDA
 
Description Needleman-Wunsch dynamic programming algorithm measures the similarity of the pairwise sequence and finds the optimal pair given the number of sequences. The task becomes nontrivial as the number of sequences to compare or the length of sequences increases. This research aims to parallelize the computation involved in the algorithm to speed up the performance using CUDA. However, there is a data dependency issue due to the property of a dynamic programming algorithm. As a solution, this research introduces the heterogeneous anti-diagonal approach, which benefits from the interaction between the serial implementation on CPU and the parallel implementation on GPU. We then measure and compare the computation time between the proposed approach and a straightforward serial approach that uses CPU only. Measurements of computation times are performed under the same experimental setup and using various pairwise sequences at different lengths. The experiment showed that the proposed approach outperforms the serial method in terms of computation time by approximately three times. Moreover, the computation time of the proposed heterogeneous anti-diagonal approach increases gradually despite the big increments in sequence length, whereas the computation time of the serial approach grows rapidly.
 
Publisher Universitas Ahmad Dahlan
 
Contributor
 
Date 2020-03-31
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion

 
Format application/pdf
 
Identifier http://ijain.org/index.php/IJAIN/article/view/361
10.26555/ijain.v6i1.361
 
Source International Journal of Advances in Intelligent Informatics; Vol 6, No 1 (2020): March 2020; 97-108
2548-3161
2442-6571
 
Language eng
 
Relation http://ijain.org/index.php/IJAIN/article/view/361/ijain_v6i1_p97-108
 
Rights https://creativecommons.org/licenses/by-sa/4.0
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library