Título:	Estratégias de otimização para alinhamento múltiplo paralelo exato de sequências biológicas
Autor(es):	Ribeiro, Vinícius Manoel Têixeira
Orientador(es):	Melo, Alba Cristina Magalhães Alves de
Assunto:	Algoritmo Computação paralela Bioinformática
Data de publicação:	25-Jun-2026
Data de defesa:	5-Mar-2026
Referência:	RIBEIRO, Vinícius Manoel Têixeira. Estratégias de otimização para alinhamento múltiplo paralelo exato de sequências biológicas. 2026. 68 f., il. Dissertação (Mestrado em Informática) — Universidade de Brasília, Brasília, 2026.
Abstract:	Multiple Sequence Alignment (MSA) is a method used in Bioinformatics for analyzing evolutionary and functional relationships between biological sequences. However, finding the mathematically optimal alignment is an NP-Complete problem, making exact algo rithms infeasible for most practical datasets. The PA-Star tool, a parallel implementation of the A* search algorithm, represents an advance by guaranteeing solution optimality. However, among other factors, its efficiency in reducing the search space is limited by the heuristic function h2,all (based on sequence pairs), resulting in less aggressive pruning. This Master’s Dissertation proposes optimizations for PA-Star, focusing on replacing the h2,all heuristic with a more robust function, h3,all (based on sequence trios), and on par allelizing its computation stage. The central hypothesis is that h3,all, despite the higher computational cost compared to h2,all, will provide a more precise lower bound, resulting in more effective pruning of the search space and, consequently, a reduction in total ex ecution time. The results obtained on two multithreaded platforms (local environment and AWS cloud) show that, although the computation time of the h3,all heuristic is much higher than that of h2,all, the average total execution time gain of the PA-Star tool with h3,all is about 34.20% in the AWS cloud environment with the arp.fasta protein dataset from the BAliBASE benchmark. In addition, we show that the solution presents good acceleration (speedup) for up to 64 cores.
Unidade Acadêmica:	Instituto de Ciências Exatas (IE) Departamento de Ciência da Computação (IE CIC)
Informações adicionais:	Dissertação (mestrado) — Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graduação em Informática, 2026.
Programa de pós-graduação:	Programa de Pós-Graduação em Informática
Licença:	A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.unb.br, www.ibict.br, www.ndltd.org sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra supracitada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
Aparece nas coleções:	Teses, dissertações e produtos pós-doutorado

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.