  Multiple Sequence Alignment (MSA) is one of the most computationally
intensive tasks in Computational Biology. Existing best known solutions for
multiple sequence alignment take several hours (in some cases days) of
computation time to align, for example, 2000 homologous sequences of average
length 300. Inspired by the Sample Sort approach in parallel processing, in
this paper we propose a highly scalable multiprocessor solution for the MSA
problem in phylogenetically diverse sequences. Our method employs an
intelligent scheme to partition the set of sequences into smaller subsets using
kmer count based similarity index, referred to as k-mer rank. Each subset is
then independently aligned in parallel using any sequential approach. Further
fine tuning of the local alignments is achieved using constraints derived from
a global ancestor of the entire set. The proposed Sample-Align-D Algorithm has
been implemented on a cluster of workstations using MPI message passing
library. The accuracy of the proposed solution has been tested on standard
benchmarks such as PREFAB. The accuracy of the alignment produced by our
methods is comparable to that of well known sequential MSA techniques. We were
able to align 2000 randomly selected sequences from the Methanosarcina
acetivorans genome in less than 10 minutes using Sample-Align-D on a 16 node
cluster, compared to over 23 hours on sequential MUSCLE system running on a
single cluster node.
