Accelerated Guide Trees Construction for Multiple Sequence Alignment

Guide trees construction is an essential step in progressive Multiple Sequence Alignment (MSA). The most widely used MSA methods apply Neighbour Joining (NJ) algorithm.NJ requires intensive computationsand exhausts huge storage space proportional to number of sequences. The growing of biological sequences forms a significant barrier and necessitates fast and optimized computation method. Some algorithms that reduce time and space requirements were produced, but at the expense of alignment accuracy. This paper introduces a new massively parallel optimized algorithm based on converting used matrices in NJ into vectors and eliminating redundant computations, while preserving the accuracy. Complexity analysis indicates significant reductions in both time and space. Proposed algorithm have been implemented on a 2.0 GHz core i7 Intel CPU in C++ and tested on various real protein sequences. Results show how the proposed vectorization approach greatly improves the performance and achieves more than 2.5-fold speedup when aligning 8000 sequences compared to ClustalW- MPI.