Alinhamento múltiplo de sequências com A-Star paralelo em cluster MPI

Abstract

O alinhamento múltiplo de sequências visa ressaltar as similaridades e diferenças em um conjunto de sequências biológicas. O alinhamento múltiplo com a soma de pares é um problema NP-Difícil e métodos heurísticos são usados para solucioná-lo, porém esses métodos não garantem que o resultado ótimo será produzido. Algumas das técnicas exatas que produzem o resultado ótimo são baseadas no algoritmo de busca A-Star, sendo uma delas o A-Star Paralelo (PA-Star). O PA-Star divide o espaço de busca entre múltiplas threads, acelerando a obtenção de resultados, contudo tem sua execução limitada a uma única máquina. O objetivo deste trabalho de graduação é propor, implementar e avaliar o MPI-PAStar, uma estratégia que permita reduzir o tempo de busca ao executar o PA-Star em diversas máquinas, utilizando o ambiente MPI para trocar mensagens, distribuindo carga de trabalho entre as máquinas. O MPI-PAStar adiciona ao PA-Star um pool de threads de processamento de mensagens e duas threads responsáveis pelo envio e recebimento de mensagens. Diversas estratégias são utilizadas para reduzir o tráfego de dados e a latência de rede, como a serialização de blocos de carga de trabalho e compactação destes antes do envio, reduzindo efeitos colaterais negativos da rede sobre a computação do alinhamento. Os resultados do MPI-PAStar apresentaram ganhos de até 36.8% no tempo de busca do alinhamento ótimo e de até 29,7% no tempo total de execução do programa, quando comparado ao PA-Star, a depender do número e similaridade das sequências sendo alinhadas, além do comprimento da maior sequência.