Parallel implementation and performance characterization of muscle

Multiple sequence alignment is a fundamental and very computationally intensive task in molecular biol-ogy. MUSCLE, a new algorithm for creating multi-ple alignments of protein sequences, achieves a high-est rank in accuracy and the fastest speed compared to ClustalW as well as T-Coffee, some widely used tools in multiple sequence alignment. To further accelerate the computations, we present the parallel implementation of MUSCLE in this paper. It is decomposed into several independent modules, which are parallelized with differ-ent OpenMP paradigms. We also conduct detailed per-formance characterization on symmetric multiple pro-cessor systems. The experiments show that MUSCLE scales well with the increase of processors, and achieves up to 15.x speedup on 16-way shared memory multiple processor system. 1