CUK-Band: A CUDA-Based Multiple Genomic Sequence Alignment on GPU

Multiple Sequence Alignment (MSA) is a fundamental process that involves aligning a set of sequences based on their identical form and structure through dynamic programming. MSA is a crucial tool for temporal analyses such as classification, aggregation, and speech recognition. The process uses a penalty score to assess the similarity among the sequences, with or without gaps. In bioinformatics, MSA is widely used to identify conserved regions and functional sites and to reveal similarities and differences between homologous biological sequences consisting of nucleic acid bases or protein amino acids. This provides a basis for genomics research and drug design. However, the large scale of biological sequences often results in high time complexity, making it difficult to achieve efficient processing. To address this issue, a new multi-sequence alignment algorithm called CUK-band has been proposed, which combines the improved central star alignment and the Compute Unified Device Architecture (CUDA) platform. Experimental results have demonstrated that CUK-band is significantly faster than previous methods. Compared to existing GPU approaches such as CMSA, CUK-band has achieved an accelerated running time of over 1.5X.