Treffer: An Efficient Parallel Processing Approach For Multiple Biological Sequence Alignment.

Multiple biological sequence alignment is a challenging task due to its high demands for computational power, memory capacity and bandwidth and a number of novel algorithms have been developed for this. In this paper, an MPI based parallel multiple sequence alignment (MSA) algorithm is implemented with the Divide-and-Conquer approach. With this approach, the sequences are first cut down into smaller subsequences to minimize the computational space. Then these subsequences are run in parallel on different available processors using MPI. Each of those processors first builds an individual guide tree and then aligns the subsequences by Needleman-Wunsch algorithm for biological sequence comparison. After aligning, the results are then sent to the main processor where they concatenate to produce the final alignment. Because of the creation of multiple guide trees, this approach achieves a significantly better speed up than a simple MPI based parallel MSA algorithm. But some quality of the alignment is compromised for the introduction of gaps at the start or end of subsequence alignments. Therefore, some heuristic methods for fixing the cut points were suggested for future improvement. [ABSTRACT FROM AUTHOR]