Optimization of the Bitap Algorithm for High-Performance Pattern Matching in DNA Sequences

Deoxyribonucleic acid (DNA) is the molecule that holds genetic information needed for the growth, development and functioning of an organism. The four types of nitrogenous bases found in nucleotides that make up each strand of DNA are: adenine (A), cytosine (C), guanine (G), or thymine (T). Efficient analysis of DNA sequencing is required since mutations in a DNA sequence can lead to genetic disorders or diseases. Bitap is an approximate string-matching algorithm that provides an effective solution for identifying such mutations in large genomic datasets. However, with an increase in data size, the performance of the sequential Bitap algorithm also declines. This paper presents a parallelized approach to improve the efficiency of the Bitap algorithm by using the Message Passing Interface (MPI) for distributed memory systems and Compute Unified Device Architecture (CUDA) for parallel computation on Graphics Processing Units (GPUs). This study focuses on comparison of execution times of three implementations of the Bitap algorithm for mutation detection: the sequential implementation, the MPI-based parallelization, and the CUDA-based GPU implementation. Experimental results indicate that the parallel approaches achieve significant performance improvements as compared to the sequential implementation, thereby enabling faster processing and better scalability for large DNA datasets.