Multiple sequence alignment is computationally difficult and classified as a NP-Hard problem; so approximate algorithm(s) are generally required for most multiple alignment tasks. The Molecular Biologist may require the alignment of thousands of sequences that each can be of many hundreds or even several thousands of nucleotides or amino acids. Even this approximation algorithm requires a long processing period of time to compute near optimal alignment. Thus, one step to reduce the processing time is to parallelize the algorithm. In this paper we propose a new approach to parallelise one such popularly used approximate algorithm called CLUSTAL W multiple sequence algorithm. In order to have solution over parallelism method we can either use multiprocessor programming or cluster programming. Multiprocessor systems are specialized expensive hardware and are not commonly available. An alternate cheapest way is to use a computer cluster. A cluster is a set of computers that are interconnected through fast local area networks to perform as one computer system. High performance computing is just one of the things that a cluster can do. The benefit of using Message Passing Interface(MPI)/Parallel Virtual Machine(PVM) cluster is that if we are running a single application, which needs a huge number crunching capability on a PVM cluster, then the application will take care of thread management and job migration between the nodes. have designed an optimal size of parallel tasks in such a way that it can minimize the communication cost and time complexity. We have implemented parallel algorithm on computer cluster using C and MPI. Experimental results are showing enhanced speedup.
Parallel Implementation, Multiple Sequence Alignment, DNA Sequence, Computer Cluster
