Defesa de Tese de Doutorado de Mario João Junior – 11/03/2025, 14h, por videoconferência
Link para defesa: https://meet.google.com/mbe-zzvp-tem
MSA-XFlow: Aplicando Reengenharia Genética nas Ferramentas de Alinhamento Múltiplo de Sequências
Resumo:
O Alinhamento Múltiplo de Sequencias (MSA) e um passo fundamental para a resolução de uma variedade de problemas em Biologia Computacional. Dada a sua complexidade computacional, tipicamente uma das inúmeras estratégias baseadas em heurísticas, propostas e revisadas nas últimas duas ou mais décadas, e adotada para produzir uma solução, porém, sem garantia de ser ótima. Tradicionalmente, as heurísticas são implementadas em ferramentas seguindo um conjunto de etapas pré-definido, com os cientistas geralmente escolhendo a ferramenta com que possuem mais afinidade ou que acreditam ser a melhor. Isso pode significar, no entanto, que algumas heurísticas estão sendo ignoradas porque não fazem parte da ferramenta escolhida. Este trabalho desfragmenta algumas das ferramentas existentes, consideradas padrão-ouro, e recombina (crossover) suas técnicas para criar, efetivamente, heurísticas aprimoradas. A viabilidade dessa ideia e endossada por uma análise estatística detalhada e pela comparação de novas estratégias, que incorporaram o uso da consistência a heurísticas que não a usam. Por exemplo, os resultados usando o benchmark Bali Base mostram que o uso de consistência tem um enorme impacto na acurácia, especialmente para sequencias com baixa porcentagem de identidade. Mais importante, as novas estratégias, geradas pela recombinação de técnicas existentes, produzem alinhamentos com melhor acurácia do que as ferramentas baseadas em consistência mais usadas para alinhamento múltiplo. Baseado nessas recombinações de técnicas, foi criado o MSA-XFlow, um gerador de múltiplos alinhamentos múltiplos que faz uso de um workflow para a geração eficiente dos alinhamentos, possibilitando aos cientistas a escolha entre diversos alinhamentos gerados. Por meio da reutilização de dados gerados em etapas anteriores, combinados com a paralelização intra e entre etapas, foi possível atingir um ganho de até 395,68 vezes em relação ao que seria realizado tradicionalmente, o que mostra o grande desempenho da ferramenta.
Abstract:
The Multiple Sequence Alignment (MSA) is a fundamental step in solving a variety of problems in Computational Biology. Due to its computational complexity, one of the numerous heuristic-based strategies proposed and revised over the past two or more decades is adopted to produce a solution, albeit without guaranteeing optimality. Traditionally, heuristics are implemented in tools following a predefined set of steps, with scientists generally choosing the tool they are most familiar with or believe to be the best. However, this may mean that some heuristics are being overlooked because they are not part of the chosen tool. This work fragments some of the existing tools, considered the gold standard, and recombines (crossovers) their techniques to effectively create improved heuristics. The feasibility of this idea is supported by a detailed statistical analysis and the comparison of new strategies that incorporate consistency into heuristics that do not use it. For example, results using the BAliBASE benchmark show that consistency has a significant impact on accuracy, especially for sequences with a low identity percentage. More importantly, the new strategies, generated by recombining existing techniques, produce alignments with better accuracy than the most commonly used consistency-based tools for multiple sequence alignment. Based on these technique recombinations, MSA-XFlow was developed, a generator of multiple MSAs that utilizes a workflow for the efficient MSA generation, allowing scientists to choose among various generated solutions. By reusing data from previous steps, combined with intra- and inter-step parallelization, it was possible to achieve a speedup of up to 395.68 times compared to traditional methods, demonstrating the tools high performance.
Banca examinadora:
Prof. Eugene Francis Vinod Rebello, UFF – Presidente
Prof. Daniel Cardoso Moraes de Oliveira, UFF
Prof. Luis Antonio Brasil Kowada, UFF
Prof. Alexandre da Costa Sena, UERJ
Profa. Alba Cristina Magalhães Alves de Melo, UnB
Prof. Marcio Bastos Castro, UFSC
Profa. Aletéia Patricia Favacho de Araújo, UnB