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

BMC Res Notes 2019 Apr 11;12(1):220. Epub 2019 Apr 11.

Department of Biochemistry and Medical Genetics and The George and Fay Yee Centre for Healthcare Innovation, University of Manitoba, Room 308-Basic Medical Sciences Building, 745 Bannatyne Avenue, Winnipeg, MB, R3E 0J9, Canada.

Objective: Finding the longest common subsequence (LCS) among sequences is NP-hard. This is an important problem in bioinformatics for DNA sequence alignment and pattern discovery. In this research, we propose new CPU-based parallel implementations that can provide significant advantages in terms of execution times, monetary cost, and pervasiveness in finding LCS of DNA sequences in an environment where Graphics Processing Units are not available. For general purpose use, we also make the OpenMP-based tool publicly available to end users.

Result: In this study, we develop three novel parallel versions of the LCS algorithm on: (i) distributed memory machine using message passing interface (MPI); (ii) shared memory machine using OpenMP, and (iii) hybrid platform that utilizes both distributed and shared memory using MPI-OpenMP. The experimental results with both simulated and real DNA sequence data show that the shared memory OpenMP implementation provides at least two-times absolute speedup than the best sequential version of the algorithm and a relative speedup of almost 7. We provide a detailed comparison of the execution times among the implementations on different platforms with different versions of the algorithm. We also show that removing branch conditions negatively affects the performance of the CPU-based parallel algorithm on OpenMP platform.

Download full-text PDF

Source
http://dx.doi.org/10.1186/s13104-019-4256-6DOI Listing
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6458724PMC

Still can't find the full text of the article?

We can help you send a request to the authors directly.
April 2019

Publication Analysis

Top Keywords

shared memory
12
dna sequence
8
execution times
8
memory machine
8
longest common
8
cpu-based parallel
8
common subsequence
8
finding longest
8
openmp-based tool
8
data shared
4
purpose openmp-based
4
general purpose
4
usersresult study
4
tool publicly
4
real dna
4
memory openmp
4
simulated real
4
publicly usersresult
4
sequence data
4
graphics processing
4

Similar Publications