  Optimal multiple sequence alignment by dynamic programming, like many highly
dimensional scientific computing problems, has failed to benefit from the
improvements in computing performance brought about by multi-processor systems,
due to the lack of suitable scheme to manage partitioning and dependencies. A
scheme for parallel implementation of the dynamic programming multiple sequence
alignment is presented, based on a peer to peer design and a multidimensional
array indexing method. This design results in up to 5-fold improvement compared
to a previously described master/slave design, and scales favourably with the
number of processors used. This study demonstrates an approach for
parallelising multi-dimensional dynamic programming and similar algorithms
utilizing multi-processor architectures.

Distributed, Parallel, and Cluster Computing