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.
