From Serial to Parallel: Enhancing Needleman-Wunsch Performance through GPU-Based Computing

Authors

  • Yustina Sri Suharini IPB University
  • Wisnu Ananta Kusuma IPB University
  • Sri Nurdiati IPB University
  • Irmanida Batubara IPB University

DOI:

https://doi.org/10.29207/resti.v9i5.6620

Keywords:

global sequence alignment, GPU computing, Needleman-Wunsch algorithm

Abstract

The increasing demand for faster bioinformatics analysis calls for more efficient approaches for sequence alignment. In this study, we demonstrate that a GPU-based implementation of the Needleman-Wunsch algorithm can achieve up to 14.8× speedup compared to its traditional CPU-based serial counterpart, without compromising alignment accuracy. By leveraging the parallel processing capabilities and shared memory of an NVIDIA GeForce RTX 3060 Laptop GPU, we significantly accelerated global sequence alignment tasks. Using clinically relevant genes such as NRAS, BRCA1, BRCA2, and Saccharomyces cerevisiae from NCBI ensures realistic alignment challenges and biological significance. Performance evaluation across a wide range of sequence lengths demonstrates the scalability and efficiency of the parallel approach. More importantly, this study provides a unique contribution by showing that a commodity GPU, such as the NVIDIA GeForce RTX 3060 Laptop, can serve as a practical alternative when high-performance computing clusters are unavailable or prohibitively expensive, thereby offering an accessible and cost-effective pathway to high-throughput bioinformatics workflows.

Downloads

Download data is not yet available.

Author Biographies

  • Wisnu Ananta Kusuma, IPB University
    • Department of Computer Science, School of Data Science, Mathematics and Informatics, IPB University, Bogor, Indonesia
    • Bioinformatics Study Program, Faculty of Mathematics and Natural Sciences, IPB University, Bogor, Indonesia
    • Tropical Biopharmaca Research Center, IPB University, Bogor, Indonesia
  • Sri Nurdiati, IPB University
    • Department of Mathematics, School of Data Science, Mathematics and Informatics, IPB University, Bogor, Indonesia
  • Irmanida Batubara, IPB University
    • Department of Chemistry, Faculty of Mathematics and Natural Sciences, IPB University, Bogor, Indonesia
    • Tropical Biopharmaca Research Center, IPB University, Bogor, Indonesia

References

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, 1970. https://doi.org/10.1016/0022-2836(70)90057-4

D. Stathis et al., “eBrainII: a 3 kW Realtime Custom 3D DRAM Integrated ASIC Implementation of a Biologically Plausible Model of a Human Scale Cortex,” J Signal Process Syst, vol. 92, no. 11, pp. 1323–1343, 2020. https://doi.org/10.1007/s11265-020-01562-x

S. Ullah, S. Rehman, M. Shafique, and A. Kumar, “High-Performance Accurate and Approximate Multipliers for FPGA-based Hardware Accelerators,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021. https://doi.org/10.1109/TCAD.2021.3056337

M. Alser, T. Shahroodi, J. Gómez-Luna, C. Alkan, and O. Mutlu, “SneakySnake: A fast and accurate universal genome pre-alignment filter for CPUs, GPUs and FPGAs,” Bioinformatics, vol. 36, no. 22–23, pp. 5282–5290, 2020. https://doi.org/10.1093/bioinformatics/btaa1015

S. Salamat and T. Rosing, “FPGA Acceleration of Sequence Alignment: A Survey,” 2020. http://arxiv.org/abs/2002.02394

A. E. E. D. Rashed, “Accelerating DNA pairwise sequence alignment using FPGA and a customized convolutional neural network,” Computers and Electrical Engineering, vol. 92, 2021. https://doi.org/10.1016/j.compeleceng.2021.107112

W. Chen, C. Yao, Y. Guo, Y. Wang, and Z. Xue, “pmTM-align: scalable pairwise and multiple structure alignment with Apache Spark and OpenMP.,” BMC Bioinformatics, vol. 21, no. 1, p. 426, Sep. 2020. https://doi.org/10.1186/s12859-020-03757-2

M. Malik, S. Malhotra, and N. Prasanth, “Time Improvement of Smith-Waterman Algorithm Using OpenMP and SIMD,” 2020. https://doi.org/10.1007/978-981-15-4451-4_54

A. R. Akbar, H. Sukoco, and W. A. Kusuma, “Comparison of data partitioning schema of parallel pairwise alignment on shared memory system,” Telkomnika (Telecommunication Computing Electronics and Control), vol. 13, no. 2, pp. 694–702, 2015. https://doi.org/10.12928/TELKOMNIKA.v13i2.1415

Q. Aguado-Puig et al., “WFA-GPU: Gap-affine pairwise alignment using GPUs,” bioRxiv, 2022. https://www.embase.com/search/results?subaction=viewrecord&id=L2018217170&from=export%0Ahttp://dx.doi.org/10.1101/2022.04.18.488374

L. N. J. Gavarraju, K. K. Pavan, A. D. P. Swaroop, and H. C. Narne, “Gpu based parallel tlbo and parallel jaya for multiple sequence alignment using mapreduce (Gpu-ptlbo & Gpu-Pjaya),” International Journal of Innovative Technology and Exploring Engineering, vol. 8, no. 7, pp. 250–259, 2019, [Online]. https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85067857896&origin=inward

S. B. Iryanto, W. A. Kusuma, R. Sadikin, and I. W. A. Swardiana, “GPU-accelerated protein sequence alignment for Jamu prediction,” 2017. https://doi.org/10.1109/IC3INA.2017.8251754

V. Gancheva and I. Georgiev, “Multithreaded parallel sequence alignment based on needleman-wunsch Algorithm,” in Proceedings - 2019 IEEE 19th International Conference on Bioinformatics and Bioengineering, BIBE 2019, IEEE, Oct. 2019, pp. 165–169. https://doi.org/10.1109/BIBE.2019.00037

S. Bhattacharya, R. Roche, B. Moussad, and D. Bhattacharya, “DisCovER: distance- and orientation-based covariational threading for weakly homologous proteins,” Proteins: Structure, Function and Bioinformatics, vol. 90, no. 2, pp. 579–588, 2022. https://doi.org/10.1002/prot.26254

S. R. Perumalla, “Needleman–wunsch algorithm using multi-threading approach,” 2020. https://doi.org/10.1007/978-981-15-1480-7_25

B. Kieu-Do-Nguyen, C. Pham-Quoc, and C.-K. Pham, “Heterogeneous Hardware-assisted Parallel Processing for BWA-MEM DNA Alignment,” in 2020 RIVF International Conference on Computing and Communication Technologies (RIVF), IEEE, Oct. 2020, pp. 1–7. https://doi.org/10.1109/RIVF48685.2020.9140768

L. Alawneh, M. A. Shehab, M. Al-Ayyoub, Y. Jararweh, and Z. A. Al-Sharif, “A scalable multiple pairwise protein sequence alignment acceleration using hybrid CPU–GPU approach,” Cluster Comput, vol. 23, no. 4, pp. 2677–2688, Dec. 2020. https://doi.org/10.1007/s10586-019-03035-8

X. Gao et al., “CBEx: A Hybrid Approach for Cancer Biomarker Extraction,” in 2020 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), IEEE, Dec. 2020, pp. 2958–2958. https://doi.org/10.1109/BIBM49941.2020.9313403

D. Elettronica, A. Zeni, S. Onken, D. Elettronica, and M. Domenico, “Leveraging Difference Recurrence Relations for High-Performance GPU Genome Alignment”. https://doi.org/10.1145/3656019.3676894

A. Zeni et al., “LOGAN: High-Performance GPU-Based X-Drop Long-Read Alignment,” Proceedings - 2020 IEEE 34th International Parallel and Distributed Processing Symposium, IPDPS 2020, pp. 462–471, 2020. https://doi.org/10.1109/IPDPS47924.2020.00055

T. Benefits and U. Gpus, “CUDA C ++ Programming Guide Changes from Version 12.4”. https://docs.nvidia.com/cuda/cuda-c-programming-guide/

“National Center for Biotechnology Information (NCBI),” National Center for Biotechnology Information (NCBI). https://www.ncbi.nlm.nih.gov/

B. Schmidt, F. Kallenborn, A. Chacon, and C. Hundt, “CUDASW++4.0: Ultra-fast GPU-based Smith-Waterman Protein Sequence Database Search,” bioRxiv, vol. 25, no. 1, p. 2023.10.09.561526, Nov. 2023. https://doi.org/10.1186/s12859-024-05965-6

C. Zhong and H. Sun, “Parallel algorithm for sensitive sequence recognition from long-read genome data with high error rate,” Tongxin Xuebao/Journal on Communications, vol. 44, no. 2, pp. 160–171, 2023. https://doi.org/10.11959/j.issn.1000-436x.2023009

D. AnySeq, “High-speed alignment on GPUs (AnySeq/GPU),” Comp Methods, 2022. https://doi.org/10.48550/arXiv.2205.07610

Downloads

Published

2025-10-25

Issue

Section

Artificial Intelligence

How to Cite

Suharini, Y. S., Kusuma, W. A., Nurdiati, S., & Batubara, I. . (2025). From Serial to Parallel: Enhancing Needleman-Wunsch Performance through GPU-Based Computing. Jurnal RESTI (Rekayasa Sistem Dan Teknologi Informasi), 9(5), 1183-1192. https://doi.org/10.29207/resti.v9i5.6620