Performance Analysis of Parallel Implementations of Global Sequence Alignment Methods for DNA Sequencing

Abstract

Sequence alignment is an important operation in bio-informatics that aims to find the similarity between the given DNA sequences. Many dynamic programming based methods exist to perform DNA sequence alignment. But due to the data dependency, for a program that is written to run in a sequential manner to do sequence alignment, this operation becomes computationally hard and complex to perform when the character length of the given DNA sequences is very large. Today mostly every device is a multicore architecture device. These devices can use parallel programming paradigms, like OpenMP and MPI, for the parallelization of codes. A parallelized code executes many times faster than its equivalent, well-written serial code. This paper aims to compare the sequential and parallelized version of the dynamic programming-based methods(Needleman-Wunsch and longest common subsequences) for the global sequential alignment of DNA sequences. The paper first describes the Needleman-Wunsch and longest common subsequence method, and then the parallelization of these methods is discussed in detail for shared memory and distributed memory architecture. The detailed experiments for sequential and parallelized implementation of both methods were carried out by varying the DNA sequence length and number of threads in case of OpenMP based parallelization and the number of processes in case of MPI based parallelization. The obtained experimental results helped to perform a comparative performance evaluation of the sequential and parallel implementation of the methods. The results showed that the parallelized implementations are many times faster than the equivalent sequential implementation. The results also show that the MPI based parallel implementation is approximately three times faster than the OpenMP based parallel implementation.