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.
We have submitted your request - we will update you on status within the next 48 hours.
Sign up for further access to Scientific Publications and Authors!
What are PubFacts Points?
PubFacts points are rewards to PubFacts members, which allow you to better promote your profile and articles throughout PubFacts.com
How do I earn PubFacts Points?
Each member is given 50 PubFacts points upon signing up. You can earn additional points by completing 100% of your profile, creating and participating in discussions, and sharing other members research.
What can I do with PubFacts Points?
Currently, you can use PubFacts Points to promote and increase readership of your articles.