Use of parallelism on MSA tools

9th September 2011: Miquel Orobitg, PhD Student, HPC_Europe visitor

Abstract: Multiple Sequence Alignment (MSA) constitutes an extremely powerful tool for important
biological applications such as phylogenetic analysis, identification of conserved motifs and
domains and structure prediction. In spite of the improvement in speed and accuracy introduced by
MSA programs, the computational requirements for large-scale alignments requires high
performance computing and parallel applications. We present an improvement to a parallel
implementation of MSA tool. Our approximation resolves the bottleneck of the progressive
alignment stage on MSA. This is achieved by increasing the degree of parallelism by balancing the
guide tree that drives the progressive alignment process. The experimental results show
improvements in execution time while maintaining the biological accuracy. We also present a first
parallel prototype to improve the alignment accuracy of a progressive alignment MSA tool. This is
achieved by producing different guide trees in order to generate different alignments and finally
choose the better one using an evaluation score. The first experimental results show that our method
is able to produce better alignments than the original MSA tool.