Abstract
Global sequence alignment is an essential process in bio-informatics for determining the degree of similarity between two DNA sequences.It is performed using the Dynamic Programming (DP) approach, in which the problem is broken down into smaller ones, and these sub-problems are solved individually.There are various dynamic programming-based approaches to performing global sequence alignments, e.g.,Needleman-Wunsch (NW), Longest Common Subsequences (LCS).It is computationally difficult and complex to perform a global sequence alignment operation when the given DNA sequences are very large because programs based on dynamic programming are generally written to run sequentially.On the other hand, A well-written parallelized code executes many times faster than its equivalent serial code.This paper first explains the NW and LCS methods.Then the parallelization of these methods for shared memory and distributed memory architecture using OpenMP and MPI parallel paradigms is discussed in detail and compares the sequential and parallelized version of the Needleman-Wunsch and longest common subsequences.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 the case of OpenMP-based parallelization and the number of processes in the case of MPI-based parallelization.The obtained experimental results helped to perform a comparative performance evaluation based on the execution time of the sequential and parallel implementation of the methods.The speedup analysis of results showed that the parallelized implementations are many times faster than the equivalent sequential implementation, and MPI-based parallel implementation is approximately three times faster than the OpenMP-based parallel implementation.