Melhoramento do resultado final do alinhamento múltiplo de sequências por meio de métodos de rearranjo de árvores e do princípio da evolução mínima - Oliveira, José Augusto Sabino [UNESP] (Universidade Estadual Paulista (Unesp), 2019)
Os recentes avanços cientíﬁcos e tecnológicos proporcionaram um grande aumento dos dados biológicos disponíveis para análise e técnicas manuais são inviáveis para executar a análise desses dados e, assim, a Bioinformática surgiu devido a necessidade de analisar-se esse volume de dados com ferramentas computacionais e possibilitar inferências relevantes. Neste contexto, técnicas de alinhamento de sequências são ferramentas imprescindíveis. No entanto, alinhar sequências tem alto custo computacional e neste cenário, adota-se o Alinhamento Múltiplo de Sequências no qual diversas heurísticas são adotadas para amenizar o problema do custo computacional. Uma destas é o Alinhamento Progressivo que funciona basicamente em três fases: alinhamento par a par, construção da árvore guia e o alinhamento de perﬁs. Diversos estudos destacam a importância da árvore guia e de reﬁná-la para manter as sequências mais similares em ramiﬁcações próximas e assim, produzir um resultado com melhor signiﬁcância biológica. Assim, no presente trabalho apresenta-se conceitos e técnicas essenciais da Bioinformática e de construção da árvore guia e, por ﬁm apresenta-se um método de reﬁnamento da árvore guia aplicado em ferramentas que usam o Alinhamento Progressivo e que trabalha entre as etapas de construção da árvore guia e do proﬁle ﬁnal. O método recebe como entrada uma árvore guia e sua matriz de distâncias produzida pelo Alinhamento Progressivo, promove mudanças em suas ramiﬁcações internas e avalia se a probabilidade da árvore produzida é mais próxima da árvore verdadeira. Se probabilidade da árvore produzida é maior que a da árvore guia inicial, a nova árvore é devolvida como a árvore guia para a ferramenta de alinhamento construir o proﬁle ﬁnal, o que proporciona resultados com melhor signiﬁcado biológico.

Recent scientiﬁc and technological advances have provided a large increase in the biological data available for analysis and manual techniques are unfeasible to perform the analysis of this data and thus Bioinformatics arose due to the need to analyze this data volume with computational tools and enable relevant inferences. In this context, sequence alignment techniques are essential tools. However, aligning sequences has a high computational cost and in this scenario, Multiple Sequence Alignment is adopted in which several heuristics are adopted to alleviate the computational cost problem. One of these is Progressive Alignment which works basically in three phases: pairwise alignment, guide tree construction and proﬁle alignment. Several studies highlight the importance of the guide tree and reﬁning it to maintain the most similar sequences in close branches and thus produce a result with better biological signiﬁcance. Thus, in the present work we discuss essential concepts and techniques of Bioinformatics and the construction of the guide tree and, ﬁnally, we present a method of reﬁnement of the guide tree applied in tools that use Progressive Alignment and that works between he guide tree build step and the ﬁnal proﬁle build step. The method receives as input a guide tree and its distance matrix produced by Progressive Alignment, makes changes in its internal branches and evaluates if the probability of the produced tree is closer to the true tree. If the produced tree’s probability is greater than that of the initial guide tree, the new tree is returned as the guide tree for the alignment tool to build the ﬁnal proﬁle, which gives better biological signiﬁcance results.
Improvement of the end result of multiple sequence alignment by tree rearrangement methods and the principle of minimum evolution
Keywords: Bioinformática; Alinhamento múltiplo de sequências; Alinhamento progressivo; Rearranjo de árvores; Reﬁnamento da árvore guia; Bioinformatics; Multiple sequence alignment; Progressive alignment; Tree rearrangement; Guide tree reﬁnement