High performance Intra-task parallelization of Multiple Sequence Alignments on CUDA-compatible GPUs

In a Multiple Sequence Alignment (MSA), homologous residues are aligned together among a set of biological sequence. It is an extension of single pair-wise alignment and usually used to infer evolutionary relationships in sets of species. Traditionally, high quality MSAs were produced by expert biologists, but this work is very tedious and trivial. Automatic MSA approaches have been proposed and some popular tools have been developed and used widely for phylogenetic analysis. However, the application of MSAs needs expensive computation as its computing requirements grow quadratically with the size and the number of the sequences to be aligned. This paper presents a GPU-based multi-threaded implementation of Multiple Sequence Alignments (MSAs). In particular, an improved strategy is specified for Intra-task parallelization approach. The proposed approach resulted in around 20× speedup on an NVidia GeForce 8800GTX GPU compared to a MSAs software program (ClustalW) running on Mac Pro machine with a single Intel Xeon 2.66 GHz CPU core.