Utilize este link para identificar ou citar este item: https://bdm.unb.br/handle/10483/15790
Arquivos neste item:
Arquivo Descrição TamanhoFormato 
2016_GabrielDeCFerreira_tcc.pdf1,91 MBAdobe PDFver/abrir
Título: Alinhamento múltiplo de sequências com A-Star paralelo em cluster MPI
Autor(es): Ferreira, Gabriel de C.
Orientador(es): Melo, Alba Cristina Magalhães Alves de
Assunto: Alinhamento Múltiplo de Sequências (MSA)
Algoritmos de computador
Processamento paralelo (Computadores)
Data de apresentação: 8-Ago-2016
Data de publicação: 18-Jan-2017
Referência: FERREIRA, Gabriel de C. Alinhamento múltiplo de sequências com A-Star paralelo em cluster MPI. 2016. xi, 75 f., il. Trabalho de conclusão de curso (Bacharelado em Ciência da Computação)—Universidade de Brasília, Brasília, 2016.
Resumo: 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.
Abstract: The multiple sequence alignment purpose is to highlight similarities and differences between a set of biological sequences. The multiple alignment is an NP-Hard problem and heuristic methods are used to solve it, however those do not guarantee that an optimal result is produced. Some exact techniques that can produce an optimal result are based on the A-Star graph search algorithm, being one of them the Parallel A-Star (PA-Star). The PA-Star divides the search space to multiple threads, accelerating the search for the result, but its execution is limited to a single machine. The objective of this undergraduate work is to propose, implement and evaluate the MPI-PAStar, a strategy that allows the reduction of the search time by executing the PA-Star on multiple machines, using the MPI environment to exchange messages, distributing the workload across different machines. The MPI-PAStar adds to PA-Star a pool of message processing threads and two threads responsible for sending and receiving messages. Multiple strategies are used to reduce network traffic and latency, like serialized workload blocks and compressing them before sending them, reducing negative network effects over the alignment computation. Results obtained with the MPI-PAStar showed that it can yield up to 36.8% reduction in terms of alignment time and up to 29.7% in terms of total execution time, depending on the number of sequences being aligned, the length of longest sequence and the content of the sequences.
Informações adicionais: Trabalho de conclusão de curso (graduação)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2016.
Aparece na Coleção:Ciência da Computação



Este item está licenciado na Licença Creative Commons Creative Commons