Parallel Implementation of Centre Star Method in SMP Cluster for Multiple Sequence Alignment

Date Added: Nov 2009
Format: PDF

Multiple Sequence Alignment is one of the most fundamental problems in computational molecular biology. The running time of the best known scheme for finding an optimal alignment, based on dynamic programming, increases exponentially with large number of input sequences. Hence, many approximation algorithms are suggested for the problem. Most of the bounded error approximation multiple sequence alignment algorithms developed for different objective functions uses center star method which takes most of the overall running time in the above algorithms. Hence, there is a need to develop efficient parallel algorithm to speed up the solution of this time consuming problem.