Alinhamento Global de Várias Sequências Biológicas utilizando Cluster de GPUs

Abstract

A multiple sequence alignment is an important tool for studying and representing similarities between a set of biological sequences – such as DNAs, RNAs and proteins. This study allows relevant information to be obtained from these sequences, i.e. their functional and evolutionary relations as well as their internal structures. Due to its importance, several methods have been proposed as a solution to this problem. Nonetheless, the problem’s inherent complexity, which is described as computationally NP-Hard, leads to prohibitive execution times in scenarios with large numbers of lengthy sequences. In this work, we present a complete implementation of the Progressive Alignment heuristic method, using hybrid parallelism for environments with multiple GPU devices. This approach allows the construction of global alignments between datasets of numerous lengthy sequences in reasonable time. Our implementation achieves expressive results, showing speedups of up to 380 when compared to the parallel ClustalW-MPI aligner for datasets obtained from NCBI’s sequence databases.