Search Space Reduction Technique for Distributed Multiple Sequence Alignment

To take advantage of the various high performance computer (HPC) architectures for multithreaded and distributed computing, this paper parallelizes the dynamic programming algorithm for multiple sequence alignment (MSA). A novel definition of a hyper-diagonal through a tensor space is used to reduce the search space. Experiments demonstrate that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are often better than other heuristic methods and are capable of aligning more divergent sequences.