(College of Computer Studies, De La Salle University, Philippines)(2) Yu Sin Kim
(College of Computer Studies, De La Salle University, Philippines)(3) Roger Luis Uy
(College of Computer Studies, De La Salle University, Philippines)*corresponding author
AbstractNeedleman-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.
KeywordsBioinformatics; Global alignment; Needleman-wunsch; GPU; CUDA
|
DOIhttps://doi.org/10.26555/ijain.v6i1.361 |
Article metricsAbstract views : 4931 | PDF views : 334 |
Cite |
Full Text Download
|
References
[1] S. El-Metwally, O. M. Ouda, and M. Helmy, Next Generation Sequencing Technologies and Challenges in Sequence Assembly, 2014, vol. 7, doi: 10.1007/978-1-4939-0715-1.
[2] S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Mol. Biol., vol. 48, no. 3, pp. 443–453, Mar. 1970, doi: 10.1016/0022-2836(70)90057-4.
[3] V. O. Polyanovsky, M. A. Roytberg, and V. G. Tumanyan, “Comparative analysis of the quality of a global algorithm and a local algorithm for alignment of two sequences,” Algorithms Mol. Biol., vol. 6, no. 1, p. 25, 2011, doi: 10.1186/1748-7188-6-25.
[4] X. Xia, “Sequence Alignment,” 2018, pp. 33–75, doi: 10.1007/978-3-319-90684-3_2.
[5] H. Khaled, R. El Gohary, N. L. Badr, and H. M. Faheem, “Accelerating pairwise DNA Sequence Alignment using the CUDA compatible GPU,” Int. J. Comput. Appl., vol. 84, no. 1, pp. 25–31, Dec. 2013, doi: 10.5120/14542-2619.
[6] T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” J. Mol. Biol., vol. 147, no. 1, pp. 195–197, Mar. 1981, doi: 10.1016/0022-2836(81)90087-5.
[7] T. R. P. Siriwardena and D. N. Ranasinghe, “Accelerating global sequence alignment using CUDA compatible multi-core GPU,” in 2010 Fifth International Conference on Information and Automation for Sustainability, 2010, pp. 201–206, doi: 10.1109/ICIAFS.2010.5715660.
[8] Y. Jararweh, M. Al-Ayyoub, M. Fakirah, L. Alawneh, and B. B. Gupta, “Improving the performance of the needleman-wunsch algorithm using parallelization and vectorization techniques,” Multimed. Tools Appl., vol. 78, no. 4, pp. 3961–3977, Feb. 2019, doi: 10.1007/s11042-017-5092-0.
[9] W. R. Pearson, “Searching protein sequence libraries: Comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms,” Genomics, vol. 11, no. 3, pp. 635–650, Nov. 1991, doi: 10.1016/0888-7543(91)90071-L.
[10] S. D. Eric, T. K. D. D. Nicholas, and K. A. Theophilus, “Bioinformatics with basic local alignment search tool (BLAST) and fast alignment (FASTA),” J. Bioinforma. Seq. Anal., 2014, doi: 10.5897/ijbc2013.0086.
[11] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, “Basic local alignment search tool,” J. Mol. Biol., vol. 215, no. 3, pp. 403–410, Oct. 1990, doi: 10.1016/S0022-2836(05)80360-2.
[12] M. A. Rahman and R. C. Muniyandi, “Review of GPU implementation to process of RNA sequence on cancer,” Informatics Med. Unlocked, vol. 10, pp. 17–26, 2018, doi: 10.1016/j.imu.2017.10.008.
[13] M. Garland et al., “Parallel Computing Experiences with CUDA,” IEEE Micro, vol. 28, no. 4, pp. 13–27, Jul. 2008, doi: 10.1109/MM.2008.57.
[14] S. Warris et al., “pyPaSWAS: Python-based multi-core CPU and GPU sequence alignment,” PLoS One, vol. 13, no. 1, p. e0190279, Jan. 2018, doi: 10.1371/journal.pone.0190279.
[15] N. Ahmed, J. Lévy, S. Ren, H. Mushtaq, K. Bertels, and Z. Al-Ars, “Correction to: GASAL2: a GPU accelerated sequence alignment library for high-throughput NGS data,” BMC Bioinformatics, vol. 20, no. 1, p. 597, Dec. 2019, doi: 10.1186/s12859-019-3185-7.
[16] C.-L. Hung, Y.-S. Lin, C.-Y. Lin, Y.-C. Chung, and Y.-F. Chung, “CUDA ClustalW: An efficient parallel algorithm for progressive multiple sequence alignment on Multi-GPUs,” Comput. Biol. Chem., vol. 58, pp. 62–68, Oct. 2015, doi: 10.1016/j.compbiolchem.2015.05.004.
[17] C. Gregg and K. Hazelwood, “Where is the data? Why you cannot debate CPU vs. GPU performance without the answer,” in (IEEE ISPASS) IEEE International Symposium on Performance Analysis of Systems and Software, 2011, pp. 134–144, doi: 10.1109/ISPASS.2011.5762730.
[18] V. W. Lee et al., “Debunking the 100X GPU vs. CPU myth,” in Proceedings of the 37th annual international symposium on Computer architecture - ISCA ’10, 2010, p. 451, doi: 10.1145/1815961.1816021.
[19] J. S. Vetter and S. Mittal, “Opportunities for Nonvolatile Memory Systems in Extreme-Scale High-Performance Computing,” Comput. Sci. Eng., vol. 17, no. 2, pp. 73–82, Mar. 2015, doi: 10.1109/MCSE.2015.4.
[20] S. Mittal and J. S. Vetter, “A Survey of CPU-GPU Heterogeneous Computing Techniques,” ACM Comput. Surv., vol. 47, no. 4, pp. 1–35, Jul. 2015, doi: 10.1145/2788396.
[21] S. Wang, A. Prakash, and T. Mitra, “Software Support for Heterogeneous Computing,” in 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2018, pp. 756–762, doi: 10.1109/ISVLSI.2018.00142.
[22] J. E. Stone, D. Gohara, and G. Shi, “OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems,” Comput. Sci. Eng., vol. 12, no. 3, pp. 66–73, May 2010, doi: 10.1109/MCSE.2010.69.
[23] Khoirudin and J. Shun-Liang, “GPU Application in Cuda Memory,” Adv. Comput. An Int. J., vol. 6, no. 2, pp. 01–10, Mar. 2015, doi: 10.5121/acij.2015.6201.
[24] NVIDIA CUDA C Programming Guide (Version 4.2). 2012, available at: https://developer.download.
nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf.
[25] J. Cheng, M. Grossman, and T. McKercher, Professional CUDA c programming. John Wiley & Sons, 2014, available at: Google Scholar.
[26] C. Ling, K. Benkrid, and T. Hamada, “A parameterisable and scalable Smith-Waterman algorithm implementation on CUDA-compatible GPUs,” in 2009 IEEE 7th Symposium on Application Specific Processors, 2009, pp. 94–100, doi: 10.1109/SASP.2009.5226343.
[27] B. Chen, Y. Xu, J. Yang, and H. Jiang, “A New Parallel Method of Smith-Waterman Algorithm on a Heterogeneous Platform,” 2010, pp. 79–90, doi: 10.1007/978-3-642-13119-6_7.
[28] S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, and K. Skadron, “A performance study of general-purpose applications on graphics processors using CUDA,” J. Parallel Distrib. Comput., vol. 68, no. 10, pp. 1370–1380, Oct. 2008, doi: 10.1016/j.jpdc.2008.05.014.
[29] S. A. Manavski and G. Valle, “CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment,” BMC Bioinformatics, vol. 9, no. S2, p. S10, Mar. 2008, doi: 10.1186/1471-2105-9-S2-S10.
[30] M. Fakirah, M. A. Shehab, Y. Jararweh, and M. Al-Ayyoub, “Accelerating Needleman-Wunsch global alignment algorithm with GPUs,” in 2015 IEEE/ACS 12th International Conference of Computer Systems and Applications (AICCSA), 2015, pp. 1–5, doi: 10.1109/AICCSA.2015.7507113.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0