An OpenMP-based tool for finding longest common subsequence in bioinformatics.

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Design

Background:

• The longest common subsequence (LCS) problem is crucial for DNA sequence alignment and pattern discovery in bioinformatics.
• Finding the LCS is computationally intensive (NP-hard), necessitating efficient algorithms.
• Existing solutions often rely on Graphics Processing Units (GPUs), limiting accessibility.

Purpose of the Study:

• To develop novel CPU-based parallel implementations for the LCS problem, specifically for DNA sequences.
• To provide efficient alternatives in environments lacking GPU resources.
• To make a publicly available OpenMP-based tool for general use.

Main Methods:

• Developed three parallel versions of the LCS algorithm: Message Passing Interface (MPI) for distributed memory, OpenMP for shared memory, and a hybrid MPI-OpenMP approach.
• Evaluated implementations using both simulated and real DNA sequence data.
• Analyzed performance by comparing execution times across different platforms and algorithm versions.

Main Results:

• The OpenMP shared memory implementation achieved at least a two-times absolute speedup and a relative speedup of nearly seven compared to the best sequential version.
• Detailed comparisons of execution times were provided for various platforms and algorithm configurations.
• Performance analysis indicated that removing branch conditions can negatively impact the OpenMP parallel algorithm's efficiency.

Conclusions:

• CPU-based parallel LCS algorithms, particularly the OpenMP implementation, offer substantial performance improvements for DNA sequence analysis.
• These methods provide a viable and cost-effective solution for LCS computation, especially when GPUs are unavailable.
• The study highlights the importance of algorithm design choices, such as branch conditions, in optimizing parallel performance.