Optimizing the Needleman–Wunsch Algorithm Using Dual-GPU Tiling for Enhanced Computational Performance

Abstract

Global sequence alignment is a fundamental task in bioinformatics, yet its computational demands pose significant challenges for large-scale biological datasets, particularly with the rapid growth of high-throughput sequencing data. This study addresses the scalability limitation of the Needleman-Wunsch (NW) algorithm by introducing a dual-GPU computational model that integrates a tiling strategy with semi-parallel kernel scheduling. The dynamic programming matrix is partitioned into submatrices processed in anti-diagonal order, with inter-tile dependency management ensuring correctness. Performance was evaluated using breast cancer biomarker sequences and Saccharomyces cerevisiae reference sequences from the NCBI database, covering alignment tasks of diverse lengths. Results demonstrate that the proposed model effectively scales across matrix dimensions from 36 cells to over 400 million cells, achieving up to 68.38× speedup compared to CPU execution. Furthermore, execution cost per million cells is reduced from 157.75 ms on the CPU to 1.4 ms on the GPU. These findings establish dual-GPU tiling as a practical and scalable solution for accelerating global sequence alignment, and provide a foundation for future heterogeneous and multi-GPU implementations. In addition, the approach highlights the importance of resource-aware scheduling, which allows large problems to be executed efficiently even when hardware resources are limited. By demonstrating consistent performance improvements across different sequence sizes, the work also provides valuable insights into computational strategies for handling next-generation sequencing data. Overall, the proposed model contributes both methodological and practical advances that can benefit large-scale bioinformatics research and related applications.