Algoritmos paralelos para o alinhamento de sequências genômicas

Abstract

No estudo da evolução dos organismos, ou das funções biológicas das moléculas, é comum a comparação entre diferentes organismos, ou moléculas, onde, em geral, essas moléculas são DNA, RNA ou proteínas, que são facilmente representadas por sequências de caracteres. A análise dessas várias sequências é um problema que necessita de muito tempo para ser realizada. Visando diminuir esse tempo são desenvolvidos métodos utilizando programação paralela com granulosidade híbrida, sendo essa paralelização necessária para tratar várias sequências com mais de 1000 caracteres. Neste trabalho estudamos o alinhamento de várias sequências e implementamos um algoritmo paralelo para este problema e comparamos o desempenho com o algoritmo sequencial utilizado pelo ClustalW, obtendo speedups que variam entre 61 e 8200, e com o algoritmo paralelo utilizado pelo ClustalWMPI, obtendo speedups que variam entre 44 e 280, quando temos muitas sequências de tamanho pequeno e quando temos um número considerável de sequências de tamanho grande, respectivamente, em ambas as comparações.

ABSTRACT - In the study of evolution and biological functions of molecules is common to compare different organisms or molecules, where, in general, these molecules are DNA, RNA or proteins that are easily represented by sequences of characters. The analysis of these sequences, either in pairs or in multiple sequences, is a problem that needs much time to be performed. And, aiming to reduce that time, parallel programming methods are developed, using hybrid granularity, and this parallelization is required to treat sequences in pratical scales. We have studied the multiple sequence alignment and implemented a parallel algorithm for this problem and we have compared the performance with the sequential algorithm used by the ClustalW, obtaining speedups between 61 and 8200, and with the parallel algorithm ClustalW-MPI, obtaining speedups between 44 and 280, when we have many small sequences and when we have few sequences with big size.