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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • P. Apoorva Ananth,
  • V. Rachana Shanbhogue,
  • N. Gopalakrishna Kini,
  • K. Jyothi Upadhya

摘要

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.