Comparative Analysis of DNA Sequence Alignment Algorithms in SARS-CoV-2
DOI:
10.33395/sinkron.v9i4.15323Keywords:
Sequence alignment; Needleman-Wunsch; Smith-Waterman; SARS-CoV-2; BioinformaticsAbstract
Sequence alignment is fundamental in bioinformatics, with Smith-Waterman (local) and Needleman-Wunsch (global) algorithms widely applied. However, comparative analyses on highly similar viral genomes such as SARS-CoV-2 remain scarce. This study systematically evaluated both algorithms using the first 5,000 nucleotides of two SARS-CoV-2 genomes (29,903 and 29,684 nt) under four parameter configurations: standard, low gap penalty, high gap penalty, and high match reward. Performance was assessed through alignment score, sequence identity, gap distribution, execution time, and parameter sensitivity. Both algorithms produced identical sequence identity (97.80%), with 4,943 matches out of 5,054 positions. Smith-Waterman consistently yielded higher alignment scores (12.6-112 points advantage), while Needleman-Wunsch was substantially faster (0.7752 vs 3.9014 s), showing 5.03 times greater computational efficiency. These findings indicate that both methods are reliable for highly similar viral sequences, with a trade-off between scoring precision and computational speed. This study provides the first parameter-sensitive comparison for full SARS-CoV02 genomes, emphasizing how parameter tuning can influence performance outcomes. A key limitation is that the analysis was restricted to the first 5,000 nucleotides, which may not capture variability across the complete genome.
Downloads
References
Banjarnahor, E., Bustamam, A., Siswantining, T., & Tampubolon, P. (2022). Analyzing kinship in severe acute respiratory syndrome coronavirus 2 DNA sequences based on hierarchical and k-means clustering methods using multiple encoding vector. International Journal on Advanced Science, Engineering and Information Technology, 12(6), 2237–2247.
Cho, H., Kalinin, M., Lim, S., Zegzhda, D., Belenko, V., & Nuralieva, E. (2020). Application and improvement of sequence alignment algorithms for intrusion detection in the Internet of Things. In 2020 IEEE Conference on Industrial Cyberphysical Systems (ICPS). https://doi.org/10.1109/ICPS48405.2020.9274752
Darsi, D., Rajesh, S., Sushma, & Krishna, P. J. S. (2023). Pairwise sequence alignment in biological sequences using machine learning. In 2023 Second International Conference on Advances in Computational Intelligence and Communication (ICACIC). IEEE. https://doi.org/10.1109/ICACIC59454.2023.10435046
Dhar, A., Bamzai, A., Chauhan, I., Yadav, T., & Azad, H. K. (2024). Parallelization of the Smith-Waterman algorithm to accelerate DNA sequence alignment. In 2024 3rd IEEE International Conference on Artificial Intelligence for Internet of Things (AIIoT). IEEE. https://doi.org/10.1109/AIIoT58432.2024.10574609
Heng, J. W., Juwono, F. H., & Reine, R. (2021). Using optimal sequencing algorithms for COVID-19 case study. In 2021 International Conference on Green Energy, Computing and Sustainable Technology (GECOST). https://doi.org/10.1109/GECOST52368.2021.9538762
Kalemati, M., Nayeri, A. D., & Koohi, S. (2024). Pip-SW: Pipeline architectures for accelerating Smith-Waterman algorithm on FPGA platforms. IEEE Transactions on Emerging Topics in Computing, 1–12. https://doi.org/10.1109/TETC.2024.3472649
Khodja, M., Melouki, A., Nabil, B., & Dehimat, A. (2024). Genomic analysis of SARS-COV2 using Biopython and Simplot comparison. Journal of Bioscience and Applied Research, 10(6), 42–53. https://doi.org/10.21608/jbaar.2024.332656.1098
Kim, J., Ji, M., & Yi, G. (2020). A review on sequence alignment algorithms for short reads based on next-generation sequencing. IEEE Access, 8, 189811–189822. https://doi.org/10.1109/ACCESS.2020.3031159
Kyal, C., Kumar, R., & Zamal, A. (2020). Performance-based analogising of Needleman Wunsch algorithm to align DNA sequences using GPU and FPGA. In 2020 IEEE 17th India Council International Conference (INDICON) (pp. 1–5). IEEE. https://doi.org/10.1109/INDICON49873.2020.9342078
Lall, A., & Tallur, S. (2023). Deep reinforcement learning-based pairwise DNA sequence alignment method compatible with embedded edge devices. Scientific Reports, 13, 2773. https://doi.org/10.1038/s41598-023-29277-6
Lee, Y. S., Kim, Y. S., & Uy, R. L. (2020). Serial and parallel implementation of Needleman-Wunsch algorithm. International Journal of Advances in Intelligent Informatics, 6(1), 97–108. https://doi.org/10.26555/ijain.v6i1.361
Naghibzadeh, M., Babaei, S., Behkmal, B., & Hatami, M. (2021). Divide and conquer approach to long genomic sequence alignment. Paper presented at the 11th International Conference on Computer and Knowledge Engineering (ICCKE 2021), Mashhad, Iran.
Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443–453. https://doi.org/10.1016/0022-2836(70)90057-4
Parvez, M. R., Hu, W., & Chen, T. (2020). Comparison of the Smith-Waterman and Needleman-Wunsch algorithms for online similarity analysis of industrial alarm floods. In 2020 IEEE Electric Power and Energy Conference (EPEC). IEEE. https://doi.org/10.1109/EPEC48502.2020.9320080
Peñaloza, R. M., Salgado, G. R., & Salazar, A. M. (2021). Optimization of a classical algorithm for the alignment of genomic sequences with artificial bee colony. In 2021 International Conference on Computational Science and Computational Intelligence (CSCI). https://doi.org/10.1109/CSCI54926.2021.00131
Rashed, A. E. E. D., Abdelfatah, H., El-Seddek, M., & Moustafa, H. E. D. (2021). Sequence alignment using machine learning-based Needleman–Wunsch algorithm. IEEE Access, 9, 109522–109535. https://doi.org/10.1109/ACCESS.2021.3100408
Saada, B., Zhang, T., Siga, E., Zhang, J., & Muniz, M. M. M. (2024). Whole-genome alignment: Methods, challenges, and future directions. Applied Sciences, 14(11), 4837. https://doi.org/10.3390/app14114837
Saloom, R. H., & Khafaji, H. K. (2023). Developing new pairwise sequence alignment method based on Needleman-Wunsch algorithm. International Journal of Intelligent Engineering and Systems, 16(2), 580–590. https://doi.org/10.22266/ijies2023.0430.48
Smith, T. F., & Waterman, M. S. (1981). Identification of common molecular subsequences. Journal of Molecular Biology, 147(1), 195–197. https://doi.org/10.1016/0022-2836(81)90087-5
Xu, X., Chan, Y., Xu, K., Zhang, J., Wang, X., Yin, Z., & Liu, W. (2020). SLPal: Accelerating long sequence alignment on many-core and multi-core architectures. In 2020 IEEE International Conference on Bioinformatics and Biomedicine (BIBM) (pp. 2242–2249). IEEE. https://doi.org/10.1109/BIBM49941.2020.9313261
Downloads
|
How to Cite
Issue
Section
License
Copyright (c) 2025 Edi, Robet, Nurhayati Harahap
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Google Scholar 
Moraref
PKP Index
Garuda Kemdikbud
Indonesia OneSearch
OCLC Worldcat
Dimensions
Index Copernicus
Scilit
Muhammad Khoiruddin harahap
