Investigating the Performance of Serial and Parallel Smith-Waterman Algorithm Implementations for Genetic Sequence Alignment Using OpenMPI
##plugins.themes.bootstrap3.article.sidebar##
##plugins.themes.bootstrap3.article.main##
Abstract
Deoxyribonucleic acid (DNA) is composed of nucleotide chains containing nitrogenous bases, phosphate groups, and pentose sugars, with variations primarily occurring in the sequence of nitrogenous bases. The analysis of DNA sequences often employs the Smith-Waterman algorithm for sequence alignment, a fundamental technique in bioinformatics. This research evaluates the performance of the Smith-Waterman algorithm across varying sequence lengths (10, 102, 103, and 104) using both serial and parallel implementations with the OpenMPI library. The study focuses on measuring execution times and speedup on 4, 6, 10, 12, and 24 cores. Results indicate that while execution times increase with longer sequences, parallelization significantly reduces processing time for sequences longer than 102. However, smaller sequences exhibit higher overhead on shorter lengths. The findings underscore the importance of efficient parallel programming and task allocation strategies in optimizing computational performance for DNA sequence analysis.
##plugins.themes.bootstrap3.article.details##
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish articles in CoreID Journal agree to the following terms:
- Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
References
E. Ernawati, D. Puspitaningrum, and A. Pravitasari, “Implementasi Algoritma Smith–Waterman Pada Local Alignment Dalam Pencarian Kesamaan Pensejajaran Barisan DNA (Studi Kasus: DNA Tumor Wilms),” Jurnal Pseudocode, vol. 1, no. 2. 2014, [Online]. Available: https://media.neliti.com/media/publications/126696-ID-implementasi-algoritma-smithwaterman-pad.pdf.
M. I. Khan, M. S. Kamal, and L. Chowdhury, “MSuPDA: A Memory Efficient Algorithm for Sequence Alignment,” Interdiscip. Sci. – Comput. Life Sci., vol. 8, no. 1, pp. 84–94, 2016, doi: 10.1007/s12539-015-0275-8.
E. F. Kirkness et al., “The dog genome: Survey sequencing and comparative analysis,” Science (80-. )., vol. 301, no. 5641, pp. 1898–1903, 2003, doi: 10.1126/science.1086432.
M. Issa and M. A. Elaziz, “Analyzing COVID-19 virus based on enhanced fragmented biological Local Aligner using improved Ions Motion Optimization algorithm,” Appl. Soft Comput. J., vol. 96, p. 106683, 2020, doi: 10.1016/j.asoc.2020.106683.
T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” J. od Mol. Biol., no. 147, pp. 195–197, 1981.
A. Chaibou and O. Sie, “Comparative Study of the Parallelization of the Smith-Waterman Algorithm on OpenMP and Cuda C,” J. Comput. Commun., vol. 03, no. 06, pp. 107–117, 2015, doi: 10.4236/jcc.2015.36011.
F. N. Muhamad, R. B. Ahmad, S. M. Asi, and M. N. Murad, “Performance Analysis of Needleman-Wunsch Algorithm (Global) and Smith-Waterman Algorithm (Local) in Reducing Search Space and Time for Dna Sequence Alignment,” J. Phys. Conf. Ser., vol. 1019, no. 1, 2018, doi: 10.1088/1742-6596/1019/1/012085.
K. Song, R. Wei, L. Zhou, and Y. Zhang, "Smith-Waterman Algorithm with CUDAlign for Faster DNA Sequence Alignment," in Proc. IEEE Int. Conf. Bioinform. Biomed., Washington, DC, USA, 2011, pp. 348-351, doi: 10.1109/BIBM.2011.48.
G. J. Liao and X. Wang, "Parallelizing Smith-Waterman algorithm using hybrid CPU/GPU systems," in Proc. IEEE Int. Conf. Bioinform. Biomed., Shenzhen, China, 2019, pp. 290-294, doi: 10.1109/BIBM47256.2019.8983098.
. S. S. K. Pavan, K. Srinivas, and K. M. Anjaneyulu, "Accelerating DNA sequence alignment using parallel computing techniques," in Proc. IEEE Int. Conf. Adv. Comput., Bengaluru, India, 2017, pp. 203-208, doi: 10.1109/IACC.2017.0049.
. A. Striemer and A. Akoglu, "Sequence alignment with GPU: Performance and cost," in Proc. IEEE Int. Conf. Appl. Reconfig. Comput., Miami, FL, USA, 2009, pp. 131-138, doi: 10.1109/ARC.2009.14.
. H. Liu, Y. Liu, and G. Zhao, "A Parallel Smith-Waterman Algorithm based on Divide and Conquer for OpenCL Compatible Devices," in Proc. IEEE Int. Conf. Intell. Comput. Commun., Bali, Indonesia, 2019, pp. 405-409, doi: 10.1109/ICICC.2019.00086.
. W. Zhang, Z. Jiang, Y. Zhang, and C. Peng, "Parallelization and Optimization of Smith-Waterman Algorithm for Efficient Genomic Data Processing," in Proc. IEEE Int. Conf. Comput. Sci. Softw. Eng., Wuhan, China, 2017, pp. 173-177, doi: 10.1109/CSSE.2017.43.
. B. Liu and H. Luo, "Optimization of DNA Sequence Alignment Based on Smith-Waterman Algorithm Using Spark," in Proc. IEEE Int. Conf. Comput. Netw. Commun., Irvine, CA, USA, 2018, pp. 562-566, doi: 10.1109/ICCNC.2018.8390354.
. A. Wijaya, Y. Nurdiansyah, and T. K. Pratama, "Parallel Implementation of Smith-Waterman Algorithm for DNA Sequence Alignment Using Hadoop," in Proc. IEEE Int. Conf. Syst. Eng. Technol., Bandung, Indonesia, 2019,