Abstract

Manal Helal
Search Space Reduction Technique for Distributed Multiple Sequence Alignment.
Software modeling needs to take advantage of the several High Performance Computer (HPC) architectures through multi-threaded and distributed computing. This work extends the dynamic programming algorithm for Multiple Sequence Alignment (MSA) to be suitable for parallel simultaneous execution, and then reduces the search space using a novel definition of a hyper-diagonal through a tensor space. Experiments demonstrates that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are better than some of the heuristic methods and capable of aligning more divergent sequences.