Novel Parallel MSA Algorithm Implementation Approach on a Computer Cluster

摘要

Multiple sequence alignment is computationally difficult and classified as aNP-Hard problem; so approximate algorithm(s) are generally required formost multiple alignment tasks. The Molecular Biologist may require thealignment of thousands of sequences that each can be of many hundreds oreven several thousands of nucleotides or amino acids. Even this approximationalgorithm requires a long processing period of time to compute near optimalalignment. Thus, one step to reduce the processing time is to parallelize thealgorithm. In this paper we propose a new approach to parallelise one suchpopularly used approximate algorithm called CLUSTAL W multiple sequencealgorithm. In order to have solution over parallelism method we can either usemultiprocessor programming or cluster programming. Multiprocessor systemsare specialized expensive hardware and are not commonly available. Analternate cheapest way is to use a computer cluster. A cluster is a set ofcomputers that are interconnected through fast local area networks to performas one computer system. High performance computing is just one of the thingsthat a cluster can do. The benefit of using Message PassingInterface(MPI)/Parallel Virtual Machine(PVM) cluster is that if we arerunning a single application, which needs a huge number crunching capabilityon a PVM cluster, then the application will take care of thread managementand job migration between the nodes. have designed an optimal size ofparallel tasks in such a way that it can minimize the communication cost andtime complexity. We have implemented parallel algorithm on computer clusterusing C and MPI. Experimental results are showing enhanced speedup.