José Augusto Sabino de Oliveira 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 São José do Rio Preto 2019 José Augusto Sabino de Oliveira 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 Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação, junto ao Programa de Pós-Graduação em Ciência da Computação, do Instituto de Biociên- cias, Letras e Ciências Exatas da Universidade Esta- dual Paulista “Júlio de Mesquita Filho”, Campus de São José do Rio Preto. Orientador: Prof. Dr. Geraldo Francisco Donegá Za- falon São José do Rio Preto 2019 O48m Oliveira, José Augusto Sabino de 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 / José Augusto Sabino de Oliveira. -- São José do Rio Preto, 2019 95 f. : il., tabs. Dissertação (mestrado) - Universidade Estadual Paulista (Unesp), Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto Orientador: Geraldo Francisco Donegá Zafalon 1. Ciência da computação. 2. Bioinformática. 3. Alinhamento de sequências. 4. Rearranjo de Árvore. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca do Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. José Augusto Sabino de Oliveira 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 Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Ciência da Computação, junto ao Programa de Pós-Graduação em Ciência da Computação, do Instituto de Biociên- cias, Letras e Ciências Exatas da Universidade Esta- dual Paulista “Júlio de Mesquita Filho”, Campus de São José do Rio Preto. Comissão Examinadora Prof. Dr. Geraldo Francisco Donegá Zafalon UNESP – Câmpus de São José do Rio Preto Orientador Prof. Dr. Jorge Rady de Almeida Junior USP – Câmpus de São Paulo Prof. Dr. Leandro Alves Neves UNESP – Câmpus de São José do Rio Preto São José do Rio Preto 07 de agosto de 2019 Ao meu pai, que sempre me guiou pelo caminho correto, acreditou e me inspirou na busca pelo conhecimento. A minha esposa Maria, pela força e companheirismo ao longo dessa caminhada. Para Alexandre, Leonardo, Mirella e Arthur. Agradecimentos À Deus por ser a luz que me guia e não me deixa desanimar frente aos desafios; À toda minha família, por toda força e confiança; Em especial, meu pai que sempre me guia e inspira a fazer sempre o melhor; A minha esposa pelo companheirismo e pelo tempo abdicado; Aos meus filhos, por serem o motivo de toda minha luta; Ao meu orientador, por ter acredito e viabilizado a realização desse trabalho; A todos do Grupo de Computação Cientifica da Unesp de São José do Rio Preto; Aos colegas do Laboratório de Bioinformática da Unesp de São José do Rio Preto; A todos os meus professores. “Aquele que ousa perder uma hora de seu tempo não sabe o valor da vida.” (CHAPIN; CHAPIN, 1935) Resumo Os recentes avanços científicos 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 in- ferências relevantes. Neste contexto, técnicas de alinhamento de sequências são ferra- mentas 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 heu- rí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 perfis. Diversos estudos destacam a importância da árvore guia e de refiná-la para manter as sequências mais similares em ramificações próximas e assim, produzir um resultado com melhor significâ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 fim apresenta-se um método de refinamento da árvore guia aplicado em ferramentas que usam o Alinhamento Pro- gressivo e que trabalha entre as etapas de construção da árvore guia e do profile final. O método recebe como entrada uma árvore guia e sua matriz de distâncias produzida pelo Alinhamento Progressivo, promove mudanças em suas ramificaçõ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 profile final, o que proporciona resultados com melhor significado biológico. Palavras-chave: Bioinformática. Alinhamento Múltiplo de Sequências. Alinhamento Progressivo. Rearranjo de Árvores. Refinamento da Árvore Guia. Abstract Recent scientific 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 profile alignment. Several studies highlight the importance of the guide tree and refining it to maintain the most similar sequences in close branches and thus produce a result with better biological significance. Thus, in the present work we discuss essential concepts and techniques of Bioinformatics and the construction of the guide tree and, finally, we present a method of refinement of the guide tree applied in tools that use Progressive Alignment and that works between the guide tree build step and the final profile 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 final profile, which gives better biological significance results. Keywords: Bioinformatics. Multiple Sequence Alignment. Progressive Alignment. Tree Rearrangement. Guide Tree Refinement. Lista de Figuras 2.1 Exemplo de célula eucarionte animal. . . . . . . . . . . . . . . . . . 25 2.2 Exemplo de célula eucarionte vegetal. . . . . . . . . . . . . . . . . . 26 2.3 Exemplo de células procariontes. . . . . . . . . . . . . . . . . . . . . 26 2.4 Esquema do núcleo de uma célula eucarionte. . . . . . . . . . . . . . 27 2.5 Estrutura do DNA. . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6 Estrutura do DNA e do RNA. . . . . . . . . . . . . . . . . . . . . . . 29 2.7 O Dogma central da biologia molecular. . . . . . . . . . . . . . . . . 30 2.8 Alinhamento global e alinhamento local. . . . . . . . . . . . . . . . . 34 2.9 A matriz de pontuação gerada pelo algoritmo de Needleman-Wunsch. 36 2.10 A matriz de pontuação gerada pelo algoritmo de Smith-Waterman. . . 37 2.11 Exemplo de um Alinhamento Progressivo. . . . . . . . . . . . . . . . 43 2.12 As etapas do Alinhamento Progressivo. . . . . . . . . . . . . . . . . 45 2.13 Exemplo de árvore guia. . . . . . . . . . . . . . . . . . . . . . . . . 46 2.14 As duas possíveis operações NNI em uma ramificação interna da árvore. 51 2.15 As operações SPR em uma ramificação interna da árvore. . . . . . . . 52 2.16 As operações TBR em uma ramificação interna da árvore. . . . . . . . 54 2.17 As operações da TBR modificadas. . . . . . . . . . . . . . . . . . . . 56 2.18 Cálculo de diagonal no DIALIGN. . . . . . . . . . . . . . . . . . . . 59 2.19 Esquema do algoritmo implementado na SAGA. . . . . . . . . . . . . 62 2.20 Esquema de funcionamento do algoritmo MUSCLE. . . . . . . . . . 63 3.1 Fluxograma de execução do método. . . . . . . . . . . . . . . . . . . 68 3.2 A Estrutura de dados da árvore binária. . . . . . . . . . . . . . . . . . 69 3.3 Árvore T’ obtida pela mudança de aresta de T. . . . . . . . . . . . . . 72 3.4 Ponto de alteração da Muscle. . . . . . . . . . . . . . . . . . . . . . 74 3.5 Fases de Execução do Alinhamento Progressivo. . . . . . . . . . . . . 75 3.6 Conjunto de sequências do BAliBase. . . . . . . . . . . . . . . . . . 75 3.7 Estrutura da árvore guia da Muscle. . . . . . . . . . . . . . . . . . . 77 3.8 Árvore guia da Muscle. . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.9 Conjunto de sequências alinhadas. . . . . . . . . . . . . . . . . . . . 78 4.1 Comparação dos resultados obtidos. . . . . . . . . . . . . . . . . . . 83 4.2 Tempos de execução. . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Lista de Tabelas 2.1 Os vinte aminoácidos que são codificados. . . . . . . . . . . . . . . . 30 2.2 Conjuntos extras de aminoácidos. . . . . . . . . . . . . . . . . . . . 31 3.1 Estrutura da árvore guia da Muscle. . . . . . . . . . . . . . . . . . . 75 4.1 Parâmetros da MUSCLE usados. . . . . . . . . . . . . . . . . . . . . 80 4.2 Comparação dos resultados obtidos. . . . . . . . . . . . . . . . . . . 81 4.3 Tempos de execução. . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.4 Efetividade do TreeRMEP. . . . . . . . . . . . . . . . . . . . . . . . 84 Lista de Abreviações AMS Alinhamento Múltiplo de Sequências DNA Deoxyribonucleic Acid FFT Fast Fourier Transform GA Algoritmos Genéticos GPU Graphics Processing Unity GPU Graphics Processing Unit HMM Hidden Markov Model IDE Integrated Development Environment MAFFT Multiple Alignment using Fast Fourier Transform ME Minimum Evolution Principle ML Maximum-Likelihood MP Maximum-Parsimony MUSCLE Multiple Sequence Comparison by Log-Expectation NGS Next Generation Sequencing NJ Neighbor-Joining NNI Nearest Neighbor Interchange PCR DNA Polimerase PD Programação Dinâmica PHYML Phylogenetic Maximum Likelihood Q Q Score RAxML Randomized Axelerated Maximum Likelihood RNA Ribonucleic Acid SA Simulated Annealing SP Sum-of-Pairs SPR Subtree Pruning and Regrafting TBR Tree Bisection and Reconnection TBR Tree Bisection and Reconnection TC Total Column Score TRMLE Tree Rearrangement + Maximum Likelihood + Minimum Evolution UPGMA Unweighted Pair Group Method using Arithmetic averages WSP Weighted Sum-of-Pairs Sumário 1 Introdução 15 1.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Justificativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Motivação e Escopo . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Revisão Bibliográfica 23 2.1 Biologia Molecular . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.1 Organização Celular . . . . . . . . . . . . . . . . . . . . . . 24 2.1.2 DNA, RNA e Proteínas . . . . . . . . . . . . . . . . . . . . . 28 2.1.3 Filogenia e Padrões . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Alinhamento de Sequências . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.1 Algoritmo de Needleman-Wunsch . . . . . . . . . . . . . . . 34 2.2.2 Algoritmo de Smith-Waterman . . . . . . . . . . . . . . . . . 36 2.3 Alinhamento Múltiplo de Sequências . . . . . . . . . . . . . . . . . . 39 2.3.1 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . 40 2.3.2 Busca Tabu . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3.3 Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . 41 2.3.4 Colônia de Formigas . . . . . . . . . . . . . . . . . . . . . . 42 2.3.5 Alinhamento Progressivo . . . . . . . . . . . . . . . . . . . . 42 2.4 O Princípio da Evolução Mínima . . . . . . . . . . . . . . . . . . . . 46 2.5 Técnicas de Reconstrução e Rearranjo de Árvores . . . . . . . . . . . 47 2.5.1 Técnicas para Rearranjo de Árvores . . . . . . . . . . . . . . 49 2.5.2 Estratégias para Rearranjo de Árvores . . . . . . . . . . . . . 50 2.5.3 O Método TBR . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.6 Ferramentas de AMS . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.6.1 Clustal Omega . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.6.2 DIALIGN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.6.3 MAFFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.6.4 SAGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.6.5 MUSCLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.7 Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3 Desenvolvimento do Trabalho 66 3.1 O Método Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2 Desenvolvimento do Método . . . . . . . . . . . . . . . . . . . . . . 72 3.3 Análise da Muscle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.4 Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4 Testes e Resultados 79 4.1 Execução dos Testes . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.3 Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5 Conclusões 86 5.1 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 REFERÊNCIAS 88 Capítulo 1 Introdução 1.1 Contextualização São muitas as revoluções e descobertas que ocorreram em todas as áreas da ciên- cia no século XX e nesse princípio do século XXI. Entre todas ciências, a Biologia enquadra-se como uma das que mais se destacou, devido aos vários avanços que tem proporcionado (COHEN, 2004). Apesar de haver registros históricos de que os antigos chineses, gregos e egípcios estudavam alguns aspectos dos seres vivos e de estruturas das células em séculos anteriores, a Biologia só teve sua considerável revolução a par- tir da descoberta da estrutura 3D, em forma de hélice, do DNA, por Watson e Crick em 1953 (WATSON; CRICK et al., 1953). Por outro lado, a Ciência da Computação é uma área que se desenvolveu no século XX, com importantes contribuições do matemático britânico Alan Turing, que lançou as suas bases ao introduzir, em 1936, um modelo matemático simples, de uma má- quina hipotética, para o processo computacional e que atualmente é conhecida como Máquina de Turing (TURING, 1937). Além disso, houve também uma contribuição relevante do matemático húngaro John von Neumann, que trabalhou com seus colegas do Instituto de Estudos Avançados de Princeton, entre 1946 e 1952, para desenvol- ver um computador que executasse programas armazenados, que foi chamado de IAS 16 Computer e se tornou o protótipo de todos os computadores modernos (STALLINGS, 2003). No entanto, a Ciência da Computação não é um fim específico, mas um meio pelo qual as demais ciências podem obter melhores resultados para os seus trabalhos e pes- quisas. Dessa forma, solucionando problemas complexos de forma automática, mais rápido do que o trabalho e a mente humana são capazes de realizar. A aplicação das técnicas e ferramentas da Ciência da Computação na área das Ciências Biológicas deu origem a uma área de conhecimento multidisciplinar conhecida como Bioinformática (EDGAR; BATZOGLOU, 2006). Um dos principais fatores que contribuíram para a evolução da Bioinformática e que a torna cada vez mais importante, relaciona-se com os avanços na medicina. O progresso fundamental na medicina depende da elucidação de como ocorrem os vários processos biológicos, levando-se a uma necessidade crescente e constante de avanços tecnológicos (COHEN, 2004). O projeto Genoma Humano e seus desmembramen- tos podem ser citados como exemplos de impulsionadores desses avanços citados na Bioinformática (PROSDOCIMI et al., 2002). Além desses fatores de avanço relatados anteriormente, o surgimento dos sequenci- adores de nova geração NGS (Next Generation Sequencing) revolucionou ainda mais a pesquisa genômica, devido ao grande volume de dados que ele é capaz de gerar, quando comparado com a tecnologia anterior, a Sanger (LIU et al., 2012). Para se ter um efeito comparativo, o que um NGS produz em um dia, um Sanger produz em anos (BEHJATI; TARPEY, 2013). Esse fato tem aumentando de maneira considerável a quantidade de dados biológicos de sequências de DNA e de proteínas que precisam ser analisados e armazenados. Com esses avanços tecnológicos, tornou-se infactível a análise manual desses dados coletados pelos biólogos (ZAFALON et al., 2015), que têm a necessidade de interpretá-los. Dessa forma, estratégias computacionais para analisá-los tornaram-se essenciais, especialmente considerando-se que os dados obti- 17 das por meio do sequenciamento são expressados na forma de cadeia de caracteres, ou seja, sequências de símbolos (COHEN, 2004). No caso do DNA, que é base da hereditariedade, trata-se de um polímero composto por moléculas chamadas nucleotídeos, que podem ser mapeados por quatro bases ni- trogenadas: Adenina (A), Citosina (C), Guanina (G) e Timina (T). Uma sequência de DNA é, portanto, especificada completamente por uma sequência composta por um alfabeto de quatro letras A, C, G, T (LIEW; YAN; YANG, 2005). Essa mesma abs- tração aplica-se aos aminoácidos, no entanto, usa-se um alfabeto de vinte letras, cujas combinações formam as proteínas. A Bioinformática desempenha um importante papel na coleta e processamento dos dados genômicos obtidos pelos biólogos no estudo das funções proteicas, bem como a determinação das regiões conhecidas como pontos quentes (hotspots), que são rele- vantes para a indústria farmacêutica (COHEN, 2004). O conhecimento detalhado das estruturas das proteínas facilita o desenvolvimento de medicamentos capazes de atuar nessas regiões de interesse e atacar as causas das potenciais doenças. Desta forma, algumas das tarefas típicas realizadas na Bioinformática incluem indicar a forma e a função de uma proteína a partir de uma determinada sequência de aminoácidos, en- contrar todos os genes e proteínas em um dado genoma e determinar os locais na estrutura proteica onde moléculas de drogas podem ser anexadas (COHEN, 2004). Essa percepção apresenta-se como um fator de suma importância em diversos cená- rios, principalmente no auxílio à eventual cura de diferentes tipos de doenças (KHURI, 2008). Assim, biólogos têm a necessidade do poder computacional para a análise sa- tisfatória dos dados que, geralmente, são obtidos em sua forma bruta e que precisam ser processados para a realização de posteriores inferências (KHURI, 2008). 18 1.2 Justificativas Existem vários métodos que são usados em várias ferramentas computacionais para extrair informações genômicas das amostras biológicas sequenciadas e as que mais se destacam são as ferramentas de alinhamento de sequências (EDGAR; BATZOGLOU, 2006). Uma das principais estratégias utilizadas pelos métodos empregados para as análises de sequências biológicas é o Alinhamento Múltiplo de Sequências (AMS) (MORRISON; MORGAN; KELCHNER, 2015). O AMS é uma estratégia útil na previsão de estruturas de proteínas, análise filogenética, predição de função e no dese- nho dos iniciadores da reação em cadeia da DNA polimerase (PCR) (NOTREDAME; HOLM; HIGGINS, 1998). No entanto, AMS é uma técnica não-determinística e nem sempre garante o resul- tado exato, mas sim um alinhamento ótimo, ao contrário do que pode ser obtido por meio de técnicas determinísticas, como a Programação Dinâmica (PD). Dentre essas técnicas de PD, destacam-se os algoritmos de Needleman-Wunsch (NEEDLEMAN; WUNSCH, 1970) e de Smith-Waterman (SMITH; WATERMAN, 1981). Estas técni- cas são adequadas para tratarem pares de sequências (WANG; JIANG, 1994). Assim, a utilização de estratégias determinísticas para alinhamentos de múltiplas sequências torna-se uma tarefa com alto custo computacional, uma vez que os algoritmos de PD anteriormente citados enquadram-se como problemas da classe dos NP-completos, com complexidade de tempo e espaço O(LN), em que L é o comprimento da sequên- cia e N é o número de sequências de uma conjunto (WATERMAN; SMITH; BEYER, 1976; WANG; JIANG, 1994; EDGAR, 2004a; WANG et al., 2015), com 1 ≥ N ≤ ∞. Devido à complexidade computacional das técnicas determinísticas, houve uma concentração de trabalhos nas técnicas de AMS, que podem ser baseadas em diver- sas heurísticas (EDGAR; BATZOGLOU, 2006). Destas, destaca-se atualmente o Ali- nhamento Progressivo (FENG; DOOLITTLE, 1987), que é o mais implementado nas diversas ferramentas bem conhecidas, como as da família Clustal (THOMPSON; HIG- 19 GINS; GIBSON, 1994; SIEVERS; HIGGINS, 2014; SIEVERS; HIGGINS, 2018), a MUSCLE (EDGAR, 2004a), a MAFFT (KATOH; ROZEWICKI; YAMADA, 2017), a MULTAL (TAYLOR, 1988), entre outras. A característica que torna o Alinhamento Progressivo interessante deve-se ao fato de que as sequências mais semelhantes, ou menos distantes, são alinhadas primeiro por meio de uma árvore binária, que neste contexto recebe o nome de árvore guia. A árvore guia é construída com auxílio de uma matriz de distâncias, na qual são arma- zenadas as distâncias evolutivas computadas com o auxílio de uma função de medida, para todos os possíveis pares de sequências de um dado conjunto de sequências forne- cido como entrada para o algoritmo. Os pares de sequências menos distantes, ou mais semelhantes, são agrupados primeiro e assume-se que, no Alinhamento Progressivo, o melhor resultado é obtido em cada nó ao alinhar os dois perfis com menor número de diferenças, mesmo que não sejam vizinhos evolutivos (BOYCE; SIEVERS; HIG- GINS, 2015; EDGAR, 2004b). O Alinhamento Progressivo tem como vantagem a velocidade, a simplicidade e a sensibilidade. Porém, erros ocorridos no início do processo não são corrigidos nas fases posteriores, devido à característica gulosa da estratégia e podem conduzir a dis- torções no resultado final (NOTREDAME; HOLM; HIGGINS, 1998). Isto leva à ne- cessidade de esforços para melhorar a acurácia da árvore guia. O desenvolvimento de estratégias capazes de conciliar desempenho computacional e acurácia dos alinhamen- tos, dando um significado biológico relevante é um dos desafios na área da Bioinfor- mática (MORRISON; MORGAN; KELCHNER, 2015). Uma vez que o Alinhamento Progressivo é sensível aos problemas que ocorrem na fase de cálculo das distâncias, as técnicas de rearranjo da árvore guia destacaram-se como um ponto fundamental, pois podem amenizar essa distorção (HSIEH et al., 2015). Neste contexto, observam-se vários estudos apontando para a importância da ár- vore guia e para a necessidade de melhorar sua acurácia, de modo a garantir um ali- 20 nhamento final com maior significância biológica. Boyce (BOYCE; SIEVERS; HIG- GINS, 2015) demonstrou que uma simples mudança na ordem dos conjuntos de en- trada, pode produzir resultados diferentes para esse mesmo conjunto. Penn (PENN et al., 2010) mostrou que as incertezas na árvore guia são fontes importantes de incertezas no alinhamento. Capella-Gutierrez e Gabaldon (CAPELLA-GUTIÉRREZ; GABAL- DÓN, 2013) mostraram que a maioria das lacunas (gaps) são inseridas em padrões que seguem a árvore guia. Zhan (ZHAN et al., 2015) usou um método adaptativo de construção da árvore para demonstrar a melhora da acurácia de diversas ferramentas de AMS com o uso de melhores árvores guia. Algumas ferramentas também têm ob- tido melhores resultados por meio do uso de técnicas para construir melhores árvores guia, como GLProbs (YE et al., 2015) e a PnpProbs (YE; LAM; TING, 2016). Hsieh (HSIEH et al., 2015) usou uma adaptação da técnica de bissecção e reconexão da ár- vore (TBR - Tree Bisection and Reconnection), a fim de melhorar a reconstrução de ár- vores guia, combinada com o princípio da evolução mínima (ME - Minimum Evolution Principle) (RZHETSKY; NEI, 1993) para filtrar posições reconectadas desnecessárias e reduzir o tempo de busca, demonstrando que o método pode ajudar outros algoritmos na construção de árvores mais precisas, com tempo de processamento aceitável. 1.3 Motivação e Escopo A partir dos estudos citados na seção 1.2 demonstra-se a importância da árvore guia, também conhecida como árvore filogenética, que é produzida pelo AMS durante a execução da segunda fase do processo de alinhamento. Melhorar a sua acurácia, ou seja, aplicar técnicas que promovam melhorias a fim de gerar uma árvore de tamanho mínimo e, que desta forma, reflita com maior proximidade a linha da evolução das espécies, ainda é um problema na área da Bioinformática. Uma árvore guia mais acurada é uma árvore em que as sequências com a menor distância evolutiva estão agrupadas juntas, ou mais próximas. Dessa forma, pode-se gerar arestas com pesos 21 mínimos, a fim de representar melhor a evolução das espécies e, consequentemente, são capazes de produzir um resultado do AMS com maior significância biológica. Técnicas que promovem mudanças na topologia da árvore guia tem por objetivo produzir uma árvore de tamanho mínimo, para a qual a soma dos tamanhos de todas as suas arestas, aproxima-se ao máximo do tamanho da árvore evolutiva verdadeira, que é uma árvore que representa a verdadeira evolução das espécies. Neste contexto, a acurácia de uma árvore guia é medida pelo resultado da diferença de seu tamanho quando comparado com o tamanho da árvore verdadeira, onde quanto menor a dife- rença, melhor é a árvore produzida. Produzir resultados do AMS com maior significância biológica, com um resultado capaz de representar com maior proximidade a evolução das espécies e demonstrar suas similaridades, o mais próximo da verdadeira evolução, é um fator importante para os pesquisadores das áreas de saúde, da indústria farmacêutica e das ciências biológi- cas. Na área de saúde e na indústria farmacêutica, tais resultados são importantes para determinar quais são as terapias e medicamentos mais adequados para determinada enfermidade ou no combate de vírus e bactérias nocivos a saúde. Sendo assim, constitui-se como motivação deste trabalho desenvolver um método capaz interagir com as ferramentas de AMS e promover melhorias na árvore guia, utili- zando técnicas de rearranjo de árvore, convergindo para resultados finais do AMS com maior significância biológica e contribuir com os trabalhos de biólogos, pesquisadores e profissionais de saúde. 1.4 Objetivos O presente trabalho tem por objetivo o desenvolvimento de um método de rearranjo que promova melhorias na acurácia da árvore guia e produza uma árvore guia com tamanhos mínimos de arestas, mais próxima da árvore evolutiva verdadeira, gerando um resultado com maior qualidade nos alinhamentos produzidos, sem degradar o de- 22 sempenho computacional em termos de tempo de execução e, assim, contribuir para a evolução da significância biológica dos resultados finais produzidos pelo AMS. O método atua nas ferramentas de AMS entre as fases de construção da árvore guia e de construção do AMS, mas não se limita a uma única ferramenta. Desta forma, foi desenvolvido em um módulo separado que recebe como entrada uma árvore guia e sua matriz de distâncias, executa trocas em suas ramificações internas para melhorar a sua acurácia e retorna a árvore guia modificada para a ferramenta de AMS. Para o desenvolvimento do presente trabalho, foi escolhida uma única ferramenta que ser- viu de base para medição dos resultados, que, neste caso, foi a ferramenta MUSCLE (EDGAR et al., 2005). Sendo assim, trata-se de uma estratégia de rearranjo de árvores com o propósito de produzir árvores guias vizinhas da árvore guia inicial, produzida pela ferramenta de alinhamento hospedeira. Desta forma, é possível dota-la da capacidade de selecionar uma árvore melhor e de tamanho reduzido, mais próximo da filogenia verdadeira. Com isso, majora-se a capacidade de produzir melhores resultados no alinhamento das sequências biológicas, com o uso do Alinhamento Progressivo. 1.5 Organização do Trabalho O presente trabalho está dividido em cinco capítulos, incluindo o atual. No Capítulo 2, realiza-se uma revisão bibliográfica referente aos assuntos e conceitos pertinentes a área da Biologia e da Bioinformática, bem como apresenta-se algumas das técnicas de AMS e de rearranjo de árvores pertinentes ao escopo do trabalho da dissertação desenvolvida. No capítulo 3, apresenta-se a proposta do método para rearranjo da árvore guia e todo o trabalho executado para o seu desenvolvimento. No capítulo 4, os resultados obtidos como o uso do método são medidos e comprados com os resultados obtidos pela ferramenta sem o uso do método proposto. Por fim, no Capítulo 5, apresentam-se as conclusões do presente trabalho e os trabalhos futuros. Capítulo 2 Revisão Bibliográfica Neste capítulo são apresentados os conceitos fundamentais sobre Biologia Molecular e Bioinformática, além das estratégias para alinhamentos de sequências e técnicas para reconstrução da árvore guia, que são indispensáveis para o entendimento do contexto de desenvolvimento do presente trabalho. 2.1 Biologia Molecular A Bioinformática é uma ciência multidisciplinar que nasceu da necessidade de se com- preender as funções biológicas dos genes, por meio da vasta quantidade de dados coletados pelos biólogos, além do requisito de interpretar esses dados. Isso envolve disciplinas como a Matemática, a Física, a Química, a Estatística, a Ciência da Com- putação e a Biologia Molecular (COHEN, 2004; PROSDOCIMI et al., 2002). Desta forma, para que os cientistas da computação tenham um bom entendimento do con- texto da Bioinformática, necessitam de compreensão dos conceitos básicos da Biologia Molecular, como organização molecular, filogenia e padrões (COHEN, 2004). Embora a Biologia tenha se impulsionado no século XX, alguns estudos relaci- onados à área remontam aos tempos antigos. Os grandes avanços na área só foram possíveis a partir do surgimento dos microscópios e dos aperfeiçoamentos feitos pelo 24 holandês Anton van Leeuwenhoek (1632 – 1723), bem como pelos posteriores traba- lhos do inglês Robert Hooke (1635 – 1703). Este criou o microscópio composto de duas lentes – a ocular e a objetiva – o que possibilitou a primeira observação da célula (GEST, 2004). O microscópio possibilitou, por exemplo, a descoberta dos espermatozoides, bem como o surgimento da teoria celular, por volta do ano 1838. Nesse período, os alemães Mathias Schleiden (1804 – 1881) e Theodor Schwann (1810 – 1882) concluíram que todas as plantas e animais eram compostos por células e, posteriormente, a descoberta do DNA em 1869 pelo também alemão Johann Friedrich Miescher (1844 – 1895) (DAHM, 2008). Desta forma, a biologia evoluiu para vários campos de pesquisa, classificados pela escala em que os organismos vivos são estudados, os tipos de organismos e os métodos aplicados. A Biologia Molecular surge como uma subdisciplina da Biologia e um campo amplo de estudos que envolve a Bioquímica, a Biofísica e a Genética. Seu estudo está voltado para o nível molecular, com foco na estrutura e função do material genético e nas interações complexas entre as moléculas nos vários sistemas de uma célula, como as interações do DNA (Deoxyribonucleic Acid) , do RNA (Ribonucleic Acid), a síntese das proteínas e as regras que regem essas interações (COHEN, 2004; PROSDOCIMI et al., 2002). 2.1.1 Organização Celular Nos estudos da Biologia busca-se a compreensão da diversidade dos organismos vi- vos existentes e isto levou à constatação de que independentemente do tipo e forma do organismo estudado, desde que sejam organismos vivos, a célula é a unidade bá- sica que representa as suas estruturas e funções. Desta forma, para obter-se maior conhecimento dos organismos vivos, realiza-se um estudo celular e molecular nes- ses organismos, que permite compreender o seu funcionamento (LEMOS; ARAGAO; 25 CASANOVA, 2003). As células são divididas entre os grupos dos eucariontes e dos procariontes (RU- BIN et al., 2000; WHITMAN; COLEMAN; WIEBE, 1998). As células eucarion- tes são mais desenvolvidas e estão presentes nos organismos mais complexos, como plantas e animais. No entanto, apresentam algumas diferenças que podem ser nota- das na representação das Figuras 2.1 e 2.2. As células procariontes, representadas na Figura 2.3, são células mais simples e que estão presentes em organismos menos complexos, com as bactérias (COHEN, 2004). A principal diferença entre os dois grupos de células é a presença de um envol- tório nuclear no grupo eucariontes, o que não ocorre com o grupo dos procariontes. Como observa-se na Figura 2.4, nessa região nuclear encontra-se o material genético, motivo de muitos estudos e pesquisas por parte dos biólogos (LEMOS; ARAGAO; CASANOVA, 2003). Figura 2.1: Exemplo de célula eucarionte animal. Fonte: http://www.simbiotica.org/imagens/celulaanimal.jpg. 26 Figura 2.2: Exemplo de célula eucarionte vegetal. Fonte: http://www.simbiotica.org/imagens/celulavegetal.jpg. Figura 2.3: Exemplo de células procariontes. Fonte: (http://portaldoprofessor.mec.gov.br/fichaTecnicaAula.html?aula=39918). 27 Figura 2.4: Esquema do núcleo de uma célula eucarionte. Fonte: https://www.sobiologia.com.br/conteudos/Citologia2/nucleo5.php. Os estudos das células na área da genômica tiveram grandes avanços desde a des- coberta da estrutura básica do DNA, que junto com o RNA e as proteínas, são as três macromoléculas biológicas primordiais aos seres humanos (LEMOS; ARAGAO; CASANOVA, 2003; COHEN, 2004). O estudo dessas macromoléculas torna-se inte- ressante, especialmente, para o entendimento do funcionamento dos organismos vivos, sendo necessária uma avaliação mais aprofundada para a compreensão das caracterís- ticas de cada indivíduo (ADAMS et al., 1992; BAJORATH; STENKAMP; ARUFFO, 1993). 28 2.1.2 DNA, RNA e Proteínas Para se compreender as estruturas e as funções dos organismos vivos é necessário um entendimento das macromoléculas de DNA, RNA e proteínas e suas interações. No contexto da Bioinformática, estas estruturas são mapeadas como biossequências, ou sequências biológicas. As cadeias que representam o DNA e o RNA são classificadas como sequências de nucleotídeos e, analogamente, as cadeias de proteínas são cha- madas de sequências de aminoácidos (EIDHAMMER; JONASSEN; TAYLOR, 2000; LEMOS; ARAGAO; CASANOVA, 2003). O DNA é a base da hereditariedade e armazena todas as informações dos indiví- duos (LEMOS; BASÍLIO; CASANOVA, 2003). A sua estrutura básica é composta por uma fita dupla de nucleotídeos, os quais podem ser um das quatro bases nitrogena- das, conforme pode ser visto na Figura 2.5. As bases nitrogenadas são a Adenina (A), a Timina (T), a Citosina (C) e a Guanina (G). Essas bases se ligam por meio de uma relação conhecida como ponte de hidrogênio (WATSON; CRICK et al., 1953; LIEW; YAN; YANG, 2005). Figura 2.5: Estrutura do DNA. Fonte (https://www.thoughtco.com/nucleic-acids-373552) 29 A estrutura do RNA, conforme pode ser visto na Figura 2.6, é uma fita simples e, assim como o DNA, é formada pela variação de quatro bases nitrogenadas. Porém, durante o processo enzimático chamando de Transcrição do DNA para o RNA, as po- sições da Timina (T) são substituídas pela Uracila (U). Na Transcrição, as informações contidas no DNA são então transcritas para as moléculas de RNA, as quais possuem o código para a ordenação dos aminoácidos. Estes são sintetizados em diferentes pro- teínas por meio de um processo chamado de Tradução do RNA (LEMOS; ARAGAO; CASANOVA, 2003; PROSDOCIMI et al., 2002), o que pode ser observado na Fi- gura 2.7. Figura 2.6: Estrutura do DNA e do RNA. Fonte (https://www.thoughtco.com/nucleic-acids-structure-and-function-4025779) As proteínas são sintetizadas por meio de um códon, que é a unidade do código genético composta por três nucleotídeos consecutivos e que determina a posição de um aminoácido na cadeia polipeptídica. Existem vinte aminoácidos principais, ou essenciais, que podem ser observados na Tabela 2.1 (LEMOS; CASANOVA, 2000). 30 Figura 2.7: O Dogma central da biologia molecular. Fonte (PROSDOCIMI et al., 2002). Tabela 2.1: Os vinte aminoácidos que são codificados. Nome Símbolo Abreviação Glicina ou Glicocola Gly, Gli G Alanina Ala A Leucina Leu L Valina Val V Isoleucina Ile I Prolina Pro P Fenilalanina Phe ou Fen F Serina Ser S Treonina Thr, The T Cisteina Cys, Cis C Tirosina Tyr, Tir Y Asparagina Asn N Glutamina Gln Q Aspartato ou Ácido aspártico Asp D Glutamato ou Ácido glutâmico Glu E Arginina Arg R Lisina Lys, Lis K Histidina His H Triptofano Trp, Tri W Metionina Met M Além do conjunto dos vinte aminoácidos essenciais, existem outros três conjuntos também utilizados pelos pesquisadores, porém são combinações de outros aminoáci- dos. Os três conjuntos podem ser vistos na Tabela 2.2. 31 Tabela 2.2: Conjuntos extras de aminoácidos. Nome Símbolo Abreviação Asparagina/Ácido Aspartâmico Glx Z Glutamina/Ácido Glutâmico Asx B Qualquer aminoácido X Com as descrições fundamentais da formação dos organismos vivos apresentadas, tornam-se possíveis análises para classificar esses organismos, segundo algumas ca- racterísticas. Estas análises são apresentadas nas seções subsequentes. 2.1.3 Filogenia e Padrões A filogenia é o estudo da evolução dos seres vivos por meio da análise da homologia entre as sequências de DNA. Homologias estão relacionadas com as similaridades resultantes da herança genética advinda de um ancestral comum. Nesse sentido, na filogenia busca-se encontrar uma árvore evolucionária dos seres vivos, partindo do pressuposto que as diferentes espécies derivam de um ancestral comum (GOULD, 1977). Com a descoberta dos padrões que ocorrem em regiões das sequências de DNA e proteínas, possibilita-se a compreensão da relação entre essas biossequências, que pode indicar elementos importantes em suas estruturas e funções. Com isso, tornam- se viáveis estudos mais aprofundado sobre os organismos. Existem suposições de que certas regiões são melhor conservadas durante a evolução, porque são importantes para a estrutura ou função da molécula (LEMOS; ARAGAO; CASANOVA, 2003). Além disso, outro objetivo da descoberta de padrões é a classificação das proteínas em famílias de acordo com os padrões identificados. Tais padrões somente podem ser considerados classificadores se, dada uma proteína desconhecida, ela possuir todos os padrões de uma determinada família e, portanto, será classificada como membro da família (BRAZMA et al., 1998). Com os avanços ocorridos na biologia molecular possibilitou-se o entendimento 32 dos fatores e características que são herdadas pelos diversos seres vivos ao longo das gerações e neste contexto, filogenia e padrões são importantes para a bioinformática. Tanto a filogenia como a análise de padrões buscam determinar como o processo evo- lutivo ocorreu e as características que ao longo do curso da evolução permaneceram preservadas nos organismos (GOULD, 1977). No entanto, a quantidade de dados biológicos disponíveis cresceu substancial- mente nos últimos anos, devido aos avanços tecnológicos e aos numerosos trabalhos de pesquisas. Determinar a filogenia e reconhecer padrões nessa expressiva massa de dados é uma tarefa que consome uma quantidade considerável de recursos com- putacionais. Neste contexto, o problema da reconstrução da filogenia é fundamental na biologia molecular, na bioquímica e na bioinformática, para garantir boas análi- ses em termos de significância biológica e otimizá-las (HSIEH et al., 2015; WANG; JIANG, 1994). Assim, as estratégias de alinhamento de sequências são imprescin- díveis para a realização de inferências sobre esses dados (EDGAR; BATZOGLOU, 2006). Identificou-se que um dos pontos principais em um alinhamento é a constru- ção da árvore guia, ou filogenética. Uma árvore guia bem construída proporcionará um alinhamento com maior precisão, permitindo uma análise mais próxima da relação evolutiva verdadeira (ZHAN et al., 2015; HSIEH et al., 2015). 2.2 Alinhamento de Sequências O alinhamento de sequências é uma técnica para se identificar as regiões de simila- ridade em um conjunto de biossequências, o que pode ser consequência das relações funcionais, estruturais ou evolutivas (LIEW; YAN; YANG, 2005). Tal abordagem con- siste em investigar por sequências homólogas ou proteínas com genes determinados, e com estruturas disponíveis em bancos de dados públicos de genomas e proteínas. Como citado anteriormente, a homologia entre duas sequências é um bom indicador que sugere um antepassado em comum. Executar a análise manual dos dados obtidos 33 por meio dos estudos e pesquisas biológicas é uma tarefa inviável e dispendiosa (ZA- FALON, 2014), devido à quantidade de informações disponíveis nas bases de dados. Estas crescem ano após ano, especialmente com o advento dos avanços tecnológicos (LIU; SCHMIDT; MASKELL, 2010). Assim, os alinhamentos assumiram um papel preponderante para assistir os pesquisadores em suas análises. As técnicas de alinhamento de sequências são estratégias que auxiliam os biólogos na execução das diversas aferições nos grupos de biossequências com variabilidade biológica. Destacam-se como uma das ferramentas mais importante da bioinformá- tica para análise dessas sequências (NOTREDAME; HOLM; HIGGINS, 1998). Estas técnicas são utilizadas para: reconstrução filogenética (HSIEH et al., 2015), para pre- dição de estruturas (KOCEV et al., 2013), análises filogenéticas, predição de função e reação em cadeia da polimerase (NOTREDAME; HOLM; HIGGINS, 1998), auxi- liando também no processo de reconhecimento de padrões (EDGAR; BATZOGLOU, 2006; RIDDER; RIDDER; REINDERS, 2013), no qual, atualmente, técnicas de Deep Learning têm sido aplicadas (GAO; ZHANG; WEI, 2018; BUSIA et al., 2018). De uma maneira simplificada, os algoritmos que implementam as estratégias de alinhamento de sequências devem executar uma comparação par-a-par entre todos os resíduos de duas cadeias de caracteres que representam os nucleotídeos ou aminoá- cidos. O objetivo é localizar as regiões de igualdade (matches). Para concluir o seu objetivo, o algoritmo pode promover rearranjos nas biossequências, com inserção de espaços, também conhecidos como gaps, nas regiões em que diferenças (mismatches) forem localizadas. A ideia é obter-se um resultado que reflita o maior nível de si- milaridade, ou a menor distância entre as sequências e, para isso, alguma função que possa mensurar o nível de identidade das sequências deve ser utilizada (EDGAR; BAT- ZOGLOU, 2006). Tal função, deve usar uma medida, ou esquema de pontuação, que pondere a quantidade de matches e de mismatches, recompensando os matches e pena- lizando os mismatches. Assim, ao fim do processo de alinhamento, a melhor solução 34 ou resultado ótimo será produzido com a maior pontuação possível (EDGAR; BAT- ZOGLOU, 2006; KHURI, 2008). Pode-se observar que o alinhamento de sequências é um problema de otimiza- ção e, para o qual, as estratégias que utilizam a Programação Dinâmica produzem os melhores resultados, ou seja, a melhor pontuação ou alinhamento exato. Dentre as abordagens existentes, as mais utilizadas são a de Needleman-Wunsch (NEEDLE- MAN; WUNSCH, 1970), para alinhamentos globais, e a de Smith-Waterman (SMITH; WATERMAN, 1981), para alinhamentos locais. Exemplos de resultados dessas abor- dagens são apresentados na Figura 2.8 e melhor explicados nas próximas seções. No entanto, ambas estratégias possuem alto custo computacional, o que as inviabiliza para operações com mais do que duas sequências. Figura 2.8: Alinhamento global e alinhamento local. Fonte: (PROSDOCIMI et al., 2002). 2.2.1 Algoritmo de Needleman-Wunsch Trata-se do algoritmo que busca por uma solução com o maior nível de similaridade, baseando-se nas sequências como um todo. Desta forma, nas estratégias que usam alinhamentos globais, o objetivo é analisar as sequências envolvidas inteiras e não apenas localizar pontos em particular (ZAFALON, 2014). 35 O algoritmo de Needleman-Wunsch é a abordagem mais conhecida e que utiliza a Programação Dinâmica para alinhar globalmente sequências de nucleotídeos ou ami- noácidos (NEEDLEMAN; WUNSCH, 1970), utilizando uma abordagem determinís- tica. Esta sempre retornará o mesmo resultado, para o mesmo conjunto de entrada, com o melhor alinhamento possível para duas sequências dadas (GUSFIELD, 1997). Resumidamente, dadas duas sequências de entrada, uma matriz de pontuação e uma função para preencher a matriz são fornecidas ao algoritmo, que então executa um alinhamento par-a-par das sequências fornecidas. A matriz deve ter tamanho (N, P), em que N é o tamanho da maior sequência e P é o tamanho da menor sequência. Para que o algoritmo produza o resultado desejado, ou seja, o melhor alinhamento possível, a matriz de pontuação deve ser preenchida de forma que quando um match for encontrado, uma pontuação positiva seja atribuída à posição da matriz que corres- ponda aos dois resíduos comparados e quando um gap precisar ser inserido, ou um mismatch for localizado, uma pontuação negativa seja atribuída a essa posição (ZA- FALON, 2014; NAIDU; NARAYANAN, 2016). Os caracteres das sequências são dispostos na primeira linha e primeira coluna da matriz e o algoritmo percorre todos os elementos da matriz, fazendo uma comparação de todos contra todos, preenchendo a matriz com as pontuações resultantes de cada comparação. Ao término do preen- chimento da matriz, realiza-se uma escalada reversa (backtracking) para a obtenção do melhor alinhamento, conforme observa-se no exemplo da Figura 2.9 (NEEDLE- MAN; WUNSCH, 1970), iniciando pela última posição da matriz e seguindo para a próxima de maior pontuação, podendo ser a posição da diagonal, a superior ou anterior esquerda. Como mencionado anteriormente, o algoritmo de Needleman-Wunsch é uma es- tratégia adequada quando aplicada aos alinhamentos globais, em que se busca por similaridade nas sequências inteiras. No entanto, mesmo em sequências com pouca si- milaridade, existem regiões que são de interesse para os pesquisadores e nesses casos, 36 Figura 2.9: A matriz de pontuação gerada pelo algoritmo de Needleman-Wunsch. Fonte: Adaptado de (ZAFALON, 2014). a abordagem mais adequada que pode ser aplicada são os algoritmos de alinhamentos locais (SMITH; WATERMAN, 1981). 2.2.2 Algoritmo de Smith-Waterman Os alinhamentos locais têm por pressuposto localizar pontos de similaridade espe- cíficos nas duas sequências analisadas. Estes pontos de similaridades locais podem representar uma característica procurada por pesquisadores durante determinada aná- lise e que são muito utilizados na indústria farmacêutica, bioquímica, genômica, entre outras, pois podem indicar locais em que uma determinada molécula pode atuar (ZA- FALON, 2014). O algoritmo de Smith-Waterman (SMITH; WATERMAN, 1981) é uma aborda- gem que se baseia no algoritmo de Needleman-Wunsch (NEEDLEMAN; WUNSCH, 1970), sendo a abordagem mais conhecida e utilizada para alinhamentos locais. Assim 37 como o algoritmo de Needleman-Wunsch, a estratégia de Smith-Waterman é determi- nística e utiliza Programação Dinâmica para obter sempre o melhor alinhamento para as sequências fornecidas (ZAFALON, 2014). Desta forma, os algoritmos compar- tilham diversos pontos, como uma matriz de pontuação, preenchida de acordo com uma função para pontuar os matches e penalizar os gaps e mismatches. A principal diferença entre os dois, é que no algoritmo de Smith-Waterman somente valores posi- tivos são atribuídos na matriz de pontuação. Quando uma pontuação negativa ocorre, o valor 0 é atribuído ao local da matriz correspondente ao par de resíduos compara- dos, conforme demonstra-se na Figura 2.10 (SMITH; WATERMAN, 1981; GOTOH, 1982). Figura 2.10: A matriz de pontuação gerada pelo algoritmo de Smith-Waterman. Fonte: Adaptado de (ZAFALON, 2014). Da mesma forma que ocorre no algoritmo Needleman-Wunsch, ao finalizar o pre- 38 enchimento da matriz de valores, realiza-se uma escalada reversa (backtracking) para a obtenção dos locais de alinhamento, iniciando sempre pelo maior valor da matriz e terminando o rastreamento quando a posição inicial da matriz for localizada (ZAFA- LON, 2014). Os algoritmos de Needleman-Wunsch e Smith-Waterman foram idealmente de- senvolvidos para alinhamentos de pares de sequências utilizando-se da Programação Dinâmica, que é uma abordagem com alto custo computacional e, como mencionado anteriormente, pode compreender uma complexidade de tempo e espaço O(LN) (WA- TERMAN; SMITH; BEYER, 1976), onde L representa o tamanho da sequência e N representa o número de sequências do conjunto analisado, com 1 ≥ N ≤ ∞. Isso é um ponto relevante e que impossibilita o seu uso com conjuntos com três ou mais sequências (WANG; JIANG, 1994). Este fato apresenta-se como um problema na conjuntura atual da Bioinformática, visto que cada vez mais deseja-se realizar alinha- mentos com inúmeras sequências, dos mais variados organismos, simultaneamente (COHEN, 2004), especialmente devido aos resultados providos pelos sequenciadores NGS (GLENN, 2011; LIU et al., 2012). Para contornar esse problema, que se apresenta com um desafio na área de Bioin- formática, surgiram várias estratégias baseadas em heurísticas, que são os alinhamen- tos múltiplos de sequências. No entanto, todas as estratégias que se utilizam dessas heurísticas, possuem em comum o mesmo problema, que é a necessidade de balan- cear os resultados para que se possa entregar alinhamentos com significância biológica e desempenho de execução do algoritmo aceitáveis (EDGAR; BATZOGLOU, 2006; COHEN, 2004). Neste ponto, técnicas de reconstrução filogenética e rearranjo de ár- vores, surgem como uma possibilidade de otimizar os resultados obtidos, por meio de abordagens que visam melhorar a árvore guia e produzir, consequentemente, melhores resultados com alinhamentos de sequências. 39 2.3 Alinhamento Múltiplo de Sequências Sabe-se que a abordagem usando Programação Dinâmica para alinhar múltiplas sequên- cias simultaneamente, produz um alinhamento exato. No entanto, é uma abordagem impraticável, devido ao alto custo computacional destes algoritmos (LIU; SCHMIDT; MASKELL, 2010; WANG; JIANG, 1994). Neste contexto, os algoritmos de Alinhamento Múltiplo de Sequências referem- se a uma série de soluções heurísticas para o alinhamento de sequências, levando em consideração eventos evolutivos como mutações, inserções, exclusões e rearranjos dos resíduos biológicos, sob certas condições (CHATZOU et al., 2015). Esta é uma tarefa básica e de importância central na Bioinformática e tem muitas aplicações nas pesqui- sas e análises biológicas, como a inferência filogenética e a predição da estrutura da proteína 3D (ZHAN et al., 2015; OGDEN; ROSENBERG, 2006). Considera-se que, durante o processo evolutivo, resíduos podem ser inseridos ou removidos do DNA de um determinado organismo, o que se conhece com indels, gerando uma mutação e, portanto, uma nova ramificação na árvore evolutiva. Com o objetivo de amenizar o problema do custo computacional, diversas pesqui- sas focam no desenvolvimento dessas heurísticas, que têm suas bases na teoria das probabilidades e que possibilitam a construção de alinhamentos múltiplos de sequên- cias, na maioria das vezes, com uma boa significância biológica e com custo com- putacional viável (EDGAR; BATZOGLOU, 2006). No entanto, devido a esse caráter probabilístico, existem perdas no resultado final do alinhamento, mas que geralmente são aceitáveis. Mesmo assim, várias pesquisas buscam formas de melhorar o resul- tado final, como por exemplo as técnicas de reconstrução filogenética e rearranjo de árvores. Existem diversas heurísticas aplicadas ao contexto da Bioinformática que podem ser aplicadas a diversos cenários do problema do Alinhamento Múltiplo de Sequências, que se discute a seguir. 40 2.3.1 Simulated Annealing Simulated Annealing (SA) (KIRKPATRICK et al., 1983) é uma heurística que se baseia na analogia com a termodinâmica, sendo uma metáfora do processo térmico annealing ou recozimento, no qual o material é resfriado lentamente de forma que, enquanto sua estrutura congela, ocorra um estado de energia mínima. É uma estratégia comumente utilizada em problemas de otimização que envolvem a busca por um máximo global. De forma análoga ao recozimento, o algoritmo define um ponto inicial i em um estado j, gerando um ponto de vizinhança i’ do ponto i e movendo-se do ponto i para o i’ usando um critério probabilístico que é dependente da temperatura no estado j. Essa temperatura é análoga à do recozimento físico e é usada como parâmetro de controle. Se a solução encontrada em i’ é melhor que a solução existente, então este novo ponto é aceito e o anterior descartado. Se a nova solução é pior do que a solução existente, então a probabilidade de aceitar o ponto é definida como exp(-(f (i’) - f (i)) / T (j)), em que f(.) é o valor da função objetivo em um determinado ponto, e T(j) é a temperatura no estado j. Depois que um certo número de pontos de vizinhança é avaliado, a temperatura é diminuída e o novo estado é j+1 é criado. Devido à forma exponencial, a probabilidade de aceitação de um ponto de vizinhança é maior em alta temperatura, e é menor à medida que a temperatura é reduzida. Desta forma, o algoritmo procura em muitos pontos de vizinhança no início, mas em um número menor de pontos à medida que a temperatura é reduzida e converge para uma solução global ótima (AMARAN et al., 2016). 2.3.2 Busca Tabu A Busca Tabu (Tabu Search) (RIAZ; WANG; LI, 2004) é um método de otimização linear combinado com estratégias de inteligência artificial, indicado para problemas de decisões críticas e que necessitam de uma vasta busca no seu espaço de solu- ções (GLOVER; LAGUNA, 1999). Pode ser aplicado no alinhamento global de bi- 41 ossequências ou na tentativa de refinamento em descoberta de padrões. Utiliza-se de estruturas de memória de curto e longo prazo no processo de busca, que permitem ex- plorar, além da otimização local, regiões do espaço de pesquisa. Em sua forma básica é um procedimento de busca de vizinhança modificado que emprega memória adap- tativa para acompanhar o histórico de solução relevante, juntamente com estratégias para explorar essa memória (AMARAN et al., 2016). 2.3.3 Algoritmos Genéticos Algoritmos Genéticos (GA) (NOTREDAME; HIGGINS, 1996; GONDRO; KINGHORN, 2007) são inspirados na Teoria da Evolução das Espécies e utilizam conceitos evo- lutivos, como hereditariedade, mutação, recombinação e seleção natural (REEVES, 1997). São muito aplicados em problemas de busca e otimização com vasto espaço de soluções (SCHWEFEL; RUDOLPH, 1995) e em reconhecimentos de padrões (PAL; WANG, 2017). Em alinhamentos múltiplos de sequências, são utilizados por obter bons resultados em termos de significância biológica e os elementos que representam as soluções possíveis são submetidos aos processos de mutação, recombinação e se- leção gênica, para evoluir sua população e, então, são mensuradas por uma função objetivo (GOLDBERG; HOLLAND, 1988). Em geral, com um algoritmo genético cria-se uma população de cadeias e cada uma dessas cadeias é chamada de cromos- somo. Cada uma dessas cadeias cromossômicas é basicamente um vetor de pontos no espaço de busca. Novos cromossomos são criados usando funções de seleção, muta- ção e cruzamento. O processo de seleção é guiado pela avaliação da aptidão ou função objetivo de cada cromossomo e seleção dos cromossomos, que é feita de acordo com seus valores de aptidão. Cromossomos adicionais são então gerados usando funções de cruzamento e mutação. As funções de cruzamento e mutação asseguram que uma diversidade de soluções seja mantida. Algoritmos genéticos são comumente utilizados porque são fáceis de implementar e adotados em vários pacotes comerciais de software 42 de otimização e simulação (AMARAN et al., 2016). 2.3.4 Colônia de Formigas Colônia de Formigas (MOSS; JOHNSON, 2003) é uma técnica bioinspirada comu- mente utilizada para a resolução de problemas de otimização e busca de caminho mínimo, que se apoia a um modelo matemático consistente que permite obter bons resultados em tempo hábil (PAPADIMITRIOU; STEIGLITZ, 1998). Nesta heurística, busca-se entender a maneira como as formigas estabelecem o melhor caminho do ni- nho até as fontes de comida (DORIGO; BLUM, 2005; LÓPEZ-IBÁÑEZ; STÜTZLE; DORIGO, 2016). O algoritmo segue o padrão de forrageamento de formigas em busca de alimento, no qual a identificação do caminho é feita pelas formigas por meio de uma decisão probabilística, usando seus traços de feromônio que agem como mensageiros. É aplicada em alinhamentos múltiplos de sequências, de modo que o alinhamento é feito pelas formigas que atravessam a sequência para coincidir com os resíduos corres- pondentes, até que uma solução seja encontrada e o feromônio é atualizado (KAUR; CHAND, 2016). 2.3.5 Alinhamento Progressivo O Alinhamento Progressivo (FENG; DOOLITTLE, 1987), esquematizado na Figura 2.11, é uma das técnicas mais utilizadas, sendo a primeira estratégia de construção prática do AMS e é a chave para a maioria dos programas de AMS (WANG et al., 2015). Utiliza-se de uma abordagem capaz de produzir resultados com boa significância bio- lógica, em um tempo computacional O(S2) (SIEVERS et al., 2011), onde S representa o número de sequências do conjunto analisado, com 1 ≥ S ≤ ∞. O Alinhamento Progressivo usa fatores probabilísticos combinados com algoritmos de Programação Dinâmica, com o objetivo de resolver ou minimizar o problema do alto custo compu- tacional do Alinhamento Múltiplo de Sequências. 43 Figura 2.11: Exemplo de um Alinhamento Progressivo. Fonte: (EDGAR, 2004a). O Alinhamento Progressivo é uma técnica implementada em ferramentas ampla- mente utilizadas por pesquisadores da área de Bioinformática, como as da família Clustal (HIGGINS; SHARP, 1988; SIEVERS; HIGGINS, 2018), a T-COFFEE (NO- TREDAME; HIGGINS; HERINGA, 2000), a MAFFT (KATOH; STANDLEY, 2013; KATOH; ROZEWICKI; YAMADA, 2017), a Kalign (LASSMANN; SONNHAM- MER, 2005), a MUSCLE (EDGAR, 2004b), entre outras. Em sua abordagem original, constrói-se uma árvore guia comparando iterativa- mente todas as sequências do conjunto de entrada entre si. Isto é utilizado para calcu- lar uma matriz de pontuação, também conhecida como matriz de distâncias, de modo a mensurar as distâncias entre todas as sequências do conjunto. Nesta comparação, um alinhamento inicial par-a-par é construído por meio do algoritmo de Needleman- Wunsch (NEEDLEMAN; WUNSCH, 1970) ou por meio de uma comparação veto- rial rápida como a k-tupla (GUERRA; BUCKLER, 2017), que é implementado pela MAFFT, a MUSCLE e a T-Coffee (CHATZOU et al., 2015). A árvore guia, também conhecida como árvore filogenética, é construída para re- presentar o relacionamento evolutivo entre sequências de entrada (FENG; DOOLIT- TLE, 1987), com o auxílio da matriz de distâncias. As árvores guia, para o Alinha- mento Progressivo, geralmente são obtidas por abordagens simples e baseadas em mé- 44 todos que medem a distância evolutiva entre as sequências, como Neighbor-Joining ou UPGMA (GUSFIELD, 1997). Por fim, existe o alinhamento dos perfis das sequências evolutivamente mais próximas, utilizando-se da árvore guia para alinhar primeiro as sequências que possuem as menores diferenças entre si e que, portanto, encontram-se mais próximas na árvore guia (WANG et al., 2015). Como percebe-se, um algoritmo que aborda a heurística de Alinhamento Progres- sivo segue um pipeline de execução bem definido, que pode ser dividido em três fa- ses (WALLACE; BLACKSHIELDS; HIGGINS, 2005; WANG et al., 2015), como observa-se na Figura 2.12: 1. Alinhamento par-a-par e construção da matriz de pontuação: cada possível par de sequências do conjunto de entrada é alinhado e calculam-se as distâncias evolutivas destes pares, com algoritmos de Programação Dinâmica e alguma função objetivo, por exemplo, como soma de pares ponderada (WSP - Weighted Sum-of-Pairs) (ALTSCHUL; CARROLL; LIPMAN, 1989). Em um conjunto com S sequências, haverá S∗(S−1)/2 pares. O resultado desta etapa é uma ma- triz de pontuação preenchida com os valores das distâncias e que será utilizada na próxima fase do pipeline; 2. Construção da árvore guia: a matriz calculada na fase anterior serve de entrada para esta fase, que é responsável pela construção da árvore guia. Esta agrupa as sequências de acordo com a ordenação da matriz de pontuação, utilizando-se de algum método de arranjo (XU; TIAN, 2015), sendo que as menos distantes são agrupadas primeiro. A árvore guia servirá de entrada na etapa posterior e há di- versos métodos para a sua construção, como o UPGMA (Unweighted Pair Group Method using Arithmetic averages) (SOKAL, 1958) ou NJ (Neighbor-Joining) (SAITOU; NEI, 1987), que agrupam sucessivamente as sequências mais simila- res, conforme observa-se na Figura 2.13. Nesta, pode-se concluir que humanos e macacos são as raças mais similares e, portanto, são agrupadas. 45 3. Alinhamento múltiplo: com a árvore guia construída na fase anterior, o al- goritmo conduz o alinhamento pelos grupos de sequências mais similares, que na árvore guia estão agrupadas, ou seja, inicia selecionando as duas sequências mais similares, cuja pontuação de distância é a menor na matriz. Em seguida, na árvore guia é selecionada a próxima sequência mais similar às duas anteriores, que é incorporada ao alinhamento. Desta forma, todas as sequências são adicio- nadas ao alinhamento, até que a última sequência seja agrupada e o alinhamento final seja obtido. O processo executado n− 1 vezes, em que n é o número de sequências do conjunto de entrada. Figura 2.12: As etapas do Alinhamento Progressivo. Fonte: Elaborada pelo autor. O Alinhamento Progressivo é uma estratégia que na maioria das vezes é capaz de alinhar conjuntos de algumas milhares de sequências com comprimentos variados. Embora possa produzir resultados com boa significância biológica e em tempo factível, enfrenta dificuldades com conjuntos na escala milhões de sequências (SIEVERS et al., 2011). 46 Figura 2.13: Exemplo de árvore guia. Fonte: Elaborada pelo autor. Acrescenta-se a isso uma forte dependência da ordem em que as sequências es- tão posicionadas no conjunto de entrada (BOYCE; SIEVERS; HIGGINS, 2015). Isto torna as técnicas de reconstrução da filogenia e rearranjo da árvore guia um importante campo de estudos, a fim de resolver o problema da ordem das sequências na árvore e, consequentemente, a sua acurácia. Assim, permite-se aproximar o máximo possível da árvore verdadeira, a qual refletirá as mutações ocorridas com as espécies durante o processo evolutivo (HSIEH et al., 2015). 2.4 O Princípio da Evolução Mínima O princípio da evolução mínima (ME) (KIDD; SGARAMELLA-ZONTA, 1971) é uma das primeiras abordagens para construção de árvores guia baseadas em uma ma- triz de distâncias. Nela os comprimentos dos ramos são atribuídos a várias topologias de árvores, a fim de selecionar dentre todas as possíveis topologias, aquela que possui a menor soma dos comprimentos dos ramos (BASTKOWSKI et al., 2015). 47 Esta abordagem é utilizada no contexto da Bioinformática para inferência filoge- nética, baseando-se na premissa de que a evolução dos seres vivos ocorre de maneira lenta e gradativa. Portanto, a árvore guia com menores distâncias entre seus nós e, consequentemente, com a menor soma dos comprimentos estimados, tem maior pro- babilidade de ser uma árvore evolutiva verdadeira. Desta forma, procura-se pela topo- logia de árvore que fornece uma soma mínima do comprimento de suas ramificações (RZHETSKY; NEI, 1993). Os métodos que utilizam essa abordagem são muito populares, pelo fato de seu uso ser mais adequado para a construção de árvores maciças, que resultam de alinhamentos de grandes conjuntos de sequências (BASTKOWSKI et al., 2015). Uma aplicação com o propósito de determinar a posição correta de uma sequência dentro de uma dado conjunto de entrada, pode ser visto em (FILIPSKI et al., 2015), no qual apresenta-se o método PhyClass, que busca determinar a posição filogenética apropriada de cada sequência na árvore guia, obtendo uma boa precisão da árvore em comparação com abordagens de máxima vizinhança. Como mencionado anteriormente, uma árvore guia mais precisa, ou seja, mais próxima da árvore evolutiva verdadeira é muito importante para obter-se um alinhamento de sequencia mais acurado. 2.5 Técnicas de Reconstrução e Rearranjo de Árvores Mesmo com os bons resultados obtidos com o uso dos métodos e ferramentas anteri- ormente citados, Boyce (BOYCE; SIEVERS; HIGGINS, 2015) aponta que ferramen- tas baseadas em Alinhamento Progressivo possuem forte dependência da ordem das sequências de entrada, o que pode gerar resultados diferentes para o mesmo conjunto de entrada, apenas alterando a ordem das sequências do conjunto. Zhan (ZHAN et al., 2015) demonstrou que melhorias na árvore guia aumentam a acurácia de diversas ferramentas de AMS. Com essas questões, destaca-se a importância das técnicas que visam melhorar a qualidade da árvore guia, com métodos de reconstrução filogenética 48 e rearranjo da árvore guia. Os algoritmos de AMS usam a árvore guia com alguma técnica de Alinhamento Progressivo para gerar o resultado final, porém empregam técnicas diferentes para construir a árvore (NELESEN et al., 2008). Nos últimos anos, várias teorias e mé- todos que usam modelos de evolução probabilística e de mutações dos sítios entre as sequências foram propostos para melhorar a precisão e a velocidade de reconstrução da árvore guia. Como citado anteriormente, o objetivo é encontrar uma árvore guia o mais próximo possível da árvore evolutiva verdadeira, o que não é obtido na maioria dos casos. O problema da reconstrução da árvore guia é um desafio clássico da bioinformática e possui muita relevância devido a sua utilização para classificação das espécies e para demonstrar as similaridades entre os organismos vivos. Essa classificação segue uma hierarquia que categoriza as espécies em ordem, de modo a agrupar os organismos vivos de acordo com a sua similaridade ou distância evolutiva. Tal classificação deve ser feita a partir da história de ancestralidade comum entre as espécies, com vistas a encontrar-se uma topologia para a árvore guia mais próxima da filogenia verdadeira. Com isso, pode-se classificar as sequências biológicas de acordo com suas diferenças, o que deve ser um reflexo das distâncias evolutivas entre elas (GUSFIELD, 1997; HSIEH et al., 2015). A árvore guia é muito importante na análise e busca por solução de vários problemas biológicos, como na predição da estrutura e função das proteínas e no desenvolvimento de novos medicamentos (COHEN, 2004; HSIEH et al., 2015). Como citado anteriormente, o Alinhamento Progressivo é sensível aos problemas que ocorrem na fase do alinhamento inicial, os quais não são possíveis de se resolver nas fases posteriores do processo. Isto se deve à característica gulosa dos algoritmos, o que impacta na precisão e qualidade da árvore guia. Sendo assim, algumas técnicas de refinamento da árvore guia foram propostas com o objetivo de otimizar a sua pre- cisão, de modo a produzir melhores resultados finais (GIRIBET, 2007), ou seja, uma 49 alinhamento final mais preciso e mais próximo da história evolutiva dos seres. Desta forma, algumas heurísticas foram propostas e utilizadas em algoritmos para implementar estratégias de rearranjo de árvores, com o objetivo de encontrar uma ár- vore ótima, que é a mais próxima daquela conhecida como árvore evolutiva verdadeira. Com isso, almeja-se obter uma reconstrução filogenética otimizada, em um espaço de busca reduzido (HSIEH et al., 2015). A seguir, serão discutidas algumas dessas técni- cas e programas de AMS que implementam árvores guia. 2.5.1 Técnicas para Rearranjo de Árvores Na análise filogenética, os métodos numéricos são conhecidos pela sua eficiência e re- petição dos resultados para um dado conjunto de análise, o que torna o seu uso prefe- rencial. Os métodos numéricos que fazem uso de critérios para otimizar os resultados são os mais desejáveis, devido à capacidade de gerarem árvores hipotéticas e compará- las por meio de alguma função de medida, a fim de selecionar a melhor árvore. No entanto, devido ao grande espaço de busca desses métodos, eles são conhecidos pelo seu alto custo computacional, ao contrário da maioria dos métodos numéricos que não utilizam critérios de otimização (GIRIBET, 2007). No tocante aos métodos que não se utilizam de otimização, os mais aplicados são baseados em distância (Distance-Based Methods) e os baseados em caracteres (Character-Based Methods). O primeiro é um método numérico que mede as distân- cias entre as sequências e armazena os resultados em uma matriz, a qual é usada em fases posteriores do alinhamento para construir a árvore guia. Esse é o método adotado pelo NJ e pelo UPGMA e são métodos rápidos, mas sem critérios de otimização. No entanto, informações biológicas importantes podem ser perdidas quando ocorre essa transformação dos símbolos que representam os resíduos em distâncias contadas par- a-par. No segundo caso, as sequências são alinhadas com base em métodos probabilís- ticos, que medem as diferenças entre os caracteres para construir a árvore guia. Essa 50 é a abordagem usada por métodos como o da Máxima Vizinhança (ML - Maximum- Likelihood) e pelo método da Máxima Parcimônia (MP - Maximum-Parsimony). Os dois são os principais métodos que utilizam estratégias com critérios de otimização da árvore, permitindo a análise completa de conjuntos de dados complexos com milhares, ou até milhões, de sequências (HSIEH et al., 2015; GIRIBET, 2007). 2.5.2 Estratégias para Rearranjo de Árvores A fim de obter-se melhores resultados, uma classe de algoritmos chamados Branch Swapping (troca de ramos), ou simplesmente Swappers, foi desenvolvida para pro- mover a troca de ramos da árvore. O objetivo desta classe de algoritmos é melhorar uma árvore que tenha sido construída anteriormente, seja ela gerada pelo método de construção de árvore adotado pelo algoritmo ou gerada pelo método de troca de ramos utilizado no refinamento da árvore (GIRIBET, 2007). Das diversas estratégias para rearranjo de árvores, a mais simples é o Nearest Neighbor Interchange (NNI) (DAY, 1983), usado pelo algoritmo Phylogenetic Ma- ximum Likelihood (PHYML) (GUINDON; GASCUEL, 2003). Sabe-se que uma rami- ficação interna da árvore binária sem raiz possui quatro subárvores conectadas e que se pode promover trocas das subárvores e obter mais duas novas árvores, como pode- se verificar na Figura 2.14. O NNI promove essas trocas para obter as duas possíveis árvores e compara-as com a original. Desta forma, seleciona entre as três subárvores, aquela que possui a maior pontuação ou probabilidade de ser uma árvore verdadeira. Esse método tem como ponto positivo a velocidade de execução, uma vez que os movi- mentos podem ser calculados localmente. Seu ponto negativo é que o método pesquisa apenas localmente nas quatro possíveis subárvores e frequentemente obtém resultados ótimos locais (local optima), principalmente quando analisa conjuntos de sequências de genes com sinais conflitantes (HSIEH et al., 2015; GIRIBET, 2007). Um resultado ótimo local, na maioria dos casos, não é o desejado pelos pesquisadores, pois os mé- 51 todos que conduzem a esses resultado acabam por ignorar as soluções ótimas globais (global optima), que, em geral, são mais desejadas. Figura 2.14: As duas possíveis operações NNI em uma ramificação interna da árvore. Fonte: (LI; TROMP; ZHANG, 1996). Um método mais amplo é o Subtree Pruning and Regrafting (SPR) (BORDEWICH; SEMPLE, 2005), implementado pelo algoritmo Randomized Axelerated Maximum Li- kelihood (RAxML) (STAMATAKIS; HOOVER; ROUGEMONT, 2008). Na Figura 2.15, pode-se observar o funcionamento do SPR, em que uma subárvore interna aleatória é podada e então é pesquisado em toda a árvore principal qual o melhor ponto para reconectar a subárvore e produzir uma nova árvore de tamanho reduzido. Pesquisando na árvore inteira pelo melhor ponto de reconexão, o método evita um resultado com um ótimo local ruim. Porém, a etapa 2 consome muito tempo de com- putação, uma vez que para cada possível ponto de reconexão da árvore, o SPR precisa recalcular toda a probabilidade da árvore a fim de comparar o resultado com a árvore anterior. Se o tamanho da nova árvore for maior que a anterior, ela é descartada, caso contrário, a árvore anterior é descarta e a nova árvore será usada nas novas iterações do algoritmo (HSIEH et al., 2015; GIRIBET, 2007; WU, 2008). O Tree Bisection and Reconnection (TBR) (BRYANT, 2004) é um método de rear- ranjo mais elaborado que, da mesma forma que SPR, corta uma árvore em duas partes, quebrando uma ramificação interna. Em seguida, seleciona um ramo da subárvore e então reconecta-o em outra posição da árvore principal, formando uma nova árvore. Pode-se observar que ao contrário do SPR, o TBR pode modificar a topologia da su- bárvore podada e da árvore principal e isso deve-se ao fato de que, ao contrário do SPR em que somente a ramo podado é testado para a reconexão, o TBR testa todos 52 Figura 2.15: As operações SPR em uma ramificação interna da árvore. Fonte: (GIRIBET, 2007). os ramos internos da subárvore, como observa-se na Figura 2.16. No entanto, mesmo com o TBR não existe garantias de encontrar a árvore guia verdadeira. O TBR gera mais vizinhos do que NNI e o SPR, o que lhe permite reconstruir uma árvore guia ver- dadeira com mais frequência que os demais métodos (HSIEH et al., 2015; GIRIBET, 2007). O espaço de busca do TBR é mais extenso, devido a necessidade de testar todos os possíveis pontos de reconexão e recalcular a probabilidade de cada possível árvore, o que o torna um método mais demorado do que o SPR e o NNI. Tipicamente, para um conjunto composto por n sequências, o NNI executará 2(n−3) iterações em busca de uma árvore melhor, enquanto que o SPR requer n2 iterações e o TBR requer n3. 53 Nem todos os pontos de reconexão geram bons resultados e evitar avaliar esses pontos é uma forma de reduzir o espaço de busca do método e melhorar o desempenho do método TBR (HSIEH et al., 2015). Isto pode ser feito baseando-se no Principio da Evolução Miníma (DESPER; GASCUEL, 2002; BORDEWICH et al., 2009). Em (HSIEH et al., 2015) foi demonstrado um método TBR melhorado que pode auxiliar outros algoritmos na construção de árvores mais precisas, com um espaço de busca reduzido. Com o método geram-se mais topologias vizinhas utilizando o ME para selecionar possíveis posições de reconexão que acelerem o tempo de busca. O ME adota uma matriz de distâncias entre as sequências biológicas, para selecionar uma árvore, cujo comprimento é mínimo e estimado dentro da estrutura de mínimos qua- drados (DENIS; GASCUEL, 2003). Será abordado em mais detalhes, na seção 2.5.3, o método TBR melhorado, bem como a sua utilização para refinar árvores produzidas pelos métodos de Alinhamento Progressivo. (HSIEH et al., 2015; GIRIBET, 2007). 2.5.3 O Método TBR O TBR é o mais amplo dentre os três métodos citados anteriormente e pode produzir os melhores resultados. No entanto, o seu espaço de busca é maior que os demais métodos apresentados, o que gera maior consumo de tempo computacional. Isto pode levar à necessidade de busca por soluções que possam diminuir o espaço e acelerar o tempo de execução. Nessa linha de entendimento, o método Tree Rearrangement + Maximum Like- lihood + Minimum Evolution (TRMLE) (HSIEH et al., 2015), busca diminuir o espaço de busca com o uso da ME e eliminar testes desnecessários com soluções que não produzem resultados melhores. O método possui as seguintes etapas: 1. Modifica-se a topologia da árvore para gerar topologias vizinhas; 2. Estima-se os comprimentos dos ramos e a probabilidade da nova árvore; 54 Figura 2.16: As operações TBR em uma ramificação interna da árvore. Fonte: (GIRIBET, 2007). 3. Caso a probabilidade da nova topologia seja melhor que a atual, a anterior é descartada e a nova árvore será utilizada na próxima iteração. As etapas que podem ser observadas na Figura 2.17 são repetidas até que a proba- bilidade não sofra mais evolução ou uma condição de término seja satisfeita. O TBR escolhe as posições de reconexão aleatoriamente e a probabilidade da árvore resultante pode estar longe da filogenética verdadeira. Para resolver o problema, o TRMLE com- bina o TBR com ME para selecionar as posições corretas de reconexão e as operações do método TBR modificado são decompostas em duas fases descritas na sequência: 1. Fase 01: 55 (a) As arestas de uma árvore T são classificadas em ordem decrescente por seus comprimentos; (b) A maior aresta de T (i2, j2) é selecionada e os seus nós finais são movidos, da seguinte forma: i. A subárvore de T induzida por i2, j2 e os descendentes de j2 são sepa- rados de T; ii. Uma nova aresta (i1, i3) é adicionada em T; iii. É determinada a distância de movimento, denotado por d; iv. A subárvore é movida com base em d para a posição (id, id + 1); (c) Considere T’ como a árvore resultante do processo anterior (Figura 2.17 (b)): i. A nova distância média de T’ é calculada; ii. A nova distância média de T’ pode ser obtida ajustando com precisão a distância de T; 2. Fase 02: (a) A subárvore J2 de T’ induzida por (i2, j2) e os descendentes de i2, são separados de T’; (b) Uma nova aresta (h1, h3) é adicionada; (c) É determinada outra distância de movimento, denotada por s; (d) A subárvore é movida com base na distância de movimento s para posição (hs, hs + 1) (Figura 2.17 (c)). (e) Considere T” como a nova árvore resultante (Figura 2.17 (d)). i. A nova distância média de T" pode ser obtida ajustando com precisão a distância de T’. 56 Após as fases 1 e 2, calcula-se a probabilidade de T", denotada por LT”. Se LT” for maior que a probabilidade da árvore original T, a topologia de T’ está mais próxima da topologia verdadeira do que T. Quanto maior a distância entre LT e LT”, mais confiança tem-se no rearranjo de T para T". Figura 2.17: As operações da TBR modificadas. Fonte: (HSIEH et al., 2015). A dinâmica proposta no método TRMLE para selecionar a troca dos nós mais dis- tantes e que tem maior probabilidade de produzir melhores resultados, demonstrou-se eficaz para melhorar a acurácia da árvore guia com consumo menor de tempo com- putacional. Esta característica pode auxiliar outros algoritmos conhecidos com o pro- blema da reconstrução de árvores guia, como o MUSCLE, para produzir resultados finais com maior qualidade, maior significância biológica e sem degradar de maneira considerável o tempo computacional. 57 2.6 Ferramentas de AMS As heurísticas citadas anteriormente são aplicáveis na busca por uma solução no pro- blema do Alinhamento Múltiplo de Sequências, sendo implementadas em diversas ferramentas computacionais. Desta forma, essa seção dedica-se a expor as principais ferramentas computacionais usadas na Bioinformática e que implementam essas heu- rísticas. As ferramentas atuais estão envolvidas com problema da grande quantidade de da- dos biológicos disponíveis, o que as obriga a uma evolução constante, principalmente devido o advento dos Sequenciadores de Nova Geração (NGS). Estes produzem volu- mes de dados de sequências de DNA consideravelmente superiores aos sequenciado- res do tipo Sanger, até então muito utilizados (GLENN, 2011; LIU et al., 2012). Essa questão acaba por ser um desafio que precisa de constantes evoluções nas plataformas das ferramentas de AMS, com atenção para o melhoramento da precisão do alinha- mento final e com relação ao tempo de execução e ao consumo de memória (EDGAR, 2004a; EDGAR; BATZOGLOU, 2006). Na sequência, serão discutidas algumas das ferramentas mais conhecidas e utilizadas. 2.6.1 Clustal Omega As ferramentas da família Clustal foram implementadas por Des Higgins (HIGGINS; SHARP, 1988), que combinou um algoritmo de Programação Dinâmica com estraté- gia de Alinhamento Progressivo e, desde então, são amplamente aplicadas em AMS. Assim, a árvore guia também assumem um papel relevante para a operação dessas ferramentas. Clustal Omega (SIEVERS et al., 2011) é a versão mais recente da família Clustal, que trouxe aumento considerável de escalabilidade em relação às versões anteriores, conseguindo alinhar conjuntos com centenas de milhares de sequências em algumas horas. Ela é capaz de fazer uso de multi-processadores, com qualidade de alinhamento 58 superiores as suas versões anteriores. Quando compara-se a Clustal Omega com outros programas de AMS de alta qualidade, usando-se conjuntos menores de sequências, a Clustal Omega pode alcançar resultados iguais. Como uso de conjuntos maiores, supera outros pacotes em termos de tempo e qualidade de execução. A escalabilidade necessária para lidar com alinhamentos de grandes conjuntos, é obtida com a utilização do algoritmo mBED (BLACKSHIELDS et al., 2010) na etapa de construção da árvore guia. Isto permite obter uma complexidade O(N log N), redu- zindo consideravelmente o tempo de computação e os requisitos de memória necessá- rios para agrupar grandes números de sequências e demonstrar a qualidade dos agru- pamentos comparando-os com as árvores guia. Para produzir árvores guia com pre- cisão semelhante aos métodos tradicionais, o algoritmo mBed trabalha incorporando cada sequência em um espaço de n dimensões proporcional a log N, substituindo cada sequência por um vetor de elementos n, em que cada elemento é simplesmente a dis- tância de um dos n elementos. Em seguida, utilizando-se de métodos de agrupamento padrões (XU; TIAN, 2015), como K-means ou UPGMA, tais vetores são agrupados de forma rápida e eficiente. Na fase posterior de refinamento dos resultados finais, é utilizado o algoritmo HHAlign, que se baseia no modelo oculto de Markov (HMM - Hidden Markov Model). 2.6.2 DIALIGN DIALIGN (MORGENSTERN et al., 1998) é uma ferramenta para alinhamentos múl- tiplos de sequências de DNA e proteínas, que combinando recursos de alinhamento global e local, combinado com um fator probabilístico na busca por regiões de mo- tifs, que podem representar importantes pontos de conservação. Essas características o torna útil para aplicação com sequências que não são alinhados de forma correta com abordagens tradicionais. Os alinhamentos são construídos a partir de semelhanças locais das sequências 59 emparelhadas e é uma abordagem muito útil para descobrir regiões funcionais con- servadas em sequências que compartilham apenas homologias locais, que não estão relacionadas de outra forma. Uma opção de ancoragem permite usar informações ex- ternas e conhecimentos especializados. O alinhamento par-a-par permite obter um resultado exato ou pode utilizar aborda- gem estocástica para alinhamentos múltiplos de sequência. Porém, não faz uso de comparação de resíduos e nem de penalizações (gaps) (MORGENSTERN, 2014), baseando-se em um esquema de comparação em diagonal, como esquematizado na Figura 2.18; A versão mais recente do DIALIGN opcionalmente usa correspondências para o banco de dados PFAM para detectar homologias fracas. Figura 2.18: Cálculo de diagonal no DIALIGN. Fonte: (MORGENSTERN et al., 1998). 2.6.3 MAFFT A MAFFT (Multiple Alignment using Fast Fourier Transform) (KATOH et al., 2002) é um ferramenta de alinhamento de múltiplo sequências que possui várias opções para uso do método progressivo, do método de refinamento iterativo e de outros métodos. Comumente utilizada para Alinhamento Múltiplo de Sequências, utiliza-se da Trans- formada Rápida de Fourier (FFT) para alinhar sequências de nucleotídeos ou aminoá- cidos, obtendo alinhamentos com boa significância biológica e com custo computa- cional reduzido em termos de tempo de execução, quando comparada as abordagens existentes. 60 Com uso da FFT, as sequências de aminoácidos são convertidas em sequências compostas de volume e polaridade para cada resíduo, o que auxilia a identificação rápida de regiões homologas entre as sequências. O sistema de pontuação simplificado permite reduzir o tempo de CPU e aumentar a precisão do resultado final, mesmo em sequências muito distantes e que possuem extensas regiões com inserções. O MAFFT implementa os métodos progressivos FFT-NS-1 e FFT-NS-2 e o método de refinamento iterativo FFT-NS-i. O tempo de CPU do FFT-NS-2 é drasticamente re- duzido em comparação com a CLUSTAL, mantendo a precisão do resultado final. O FFT-NS-i chega a ser 100 vezes mais rápido que T-COFFEE, sem penalizar a preci- são do resultado final, quando o conjunto das sequências de entrada excede 60 taxas (KATOH et al., 2002). Na MAFFT, um Alinhamento Progressivo inicial FFT-NS-1 é construído por meio de um cálculo aproximado das distâncias entre cada par de sequências do conjunto de entrada, baseado em um esquema de pontuação de 6-tuplas compartilhadas entre as sequências sendo alinhadas. Essa matriz de distâncias inicial é utilizada para a construção de uma árvore guia por meio do método UPGMA, com tempo de UCP de O(N2), onde N é o número de sequências, e, então, são alinhadas progressivamente seguindo a ordem das ramificações da árvore guia (KATOH et al., 2005; KATOH et al., 2002). Um segundo Alinhamento Progressivo FFT-NS-2 é construído, porém, uma nova matriz de distâncias é calculada considerando o alinhamento construído pelo FFT-NS- 1. Desta forma, um novo Alinhamento Progressivo baseia-se em uma árvore cons- truída a partir da nova matriz de distância, do qual espera-se obter um resultado mais preciso (KATOH et al., 2005; KATOH et al., 2002). O resultado obtido pelo método FFT-NS-2 é submetido ao método de refinamento iterativo FFT-NS-i, a fim de obter melhorias na acurácia do alinhamento. O alinha- mento é dividido em dois grupos e realinhados por meio da técnica de particionamento 61 restrito dependente de árvore (HIROSAWA et al., 1995). Este é repetido até que não seja mais obtido um resultado de pontuação melhor para o alinhamento em relação à pontuação anterior (KATOH et al., 2005; KATOH et al., 2002). Atualmente o MAFFT encontra-se na versão 7 (KATOH; STANDLEY, 2013), com novas funcionalidades para interface web, opções para adicionar sequências não ali- nhadas em um alinhamento existente, ajuste de direção do alinhamento de nucleotí- deos, alinhamento restrito e processamento paralelo por meio de multithreading e do uso de GPUs (Graphics Processing Unity) (ZHU et al., 2015). Novas funcionalidades foram adicionadas recentemente na interface web (KA- TOH; ROZEWICKI; YAMADA, 2017) para lidar com grandes volumes de dados e op- ções para refinar iterativamente os resultados do AMS. Funções adicionais permitem a seleção interativa de sequências e fazer inferência filogenética para pré-processamento e pós-processamento de MSA. A principal limitação do MAFFAT, é a dificuldade para lidar com sequências pouco relacionadas ou biologicamente distantes. 2.6.4 SAGA A SAGA é uma abordagem híbrida que usa Programação Dinâmica como parte do processo, sendo a primeira ferramenta que implementou a heurística do algoritmo ge- nético para alinhamentos múltiplos de sequências. Na Figura 2.19 demonstra-se o funcionamento da ferramenta, que utiliza as técnicas da heurística de algoritmo gené- tico para evoluir a população de alinhamentos até obter-se uma condição de parada (NOTREDAME; HIGGINS, 1996); 62 Figura 2.19: Esquema do algoritmo implementado na SAGA. Fonte: Adaptado de (NOTREDAME; HIGGINS, 1996). 2.6.5 MUSCLE A MUSCLE (Multiple Sequence Comparison by Log-Expectation) é uma ferramenta para Alinhamento Múltiplo de Sequências que implementa a heurística do Alinha- mento Progressivo e que possui três estágios de execução esquematizados na Figura 2.20. Ao final da execução de cada estágio, o algoritmo disponibiliza um alinhamento múl- 63 tiplo. A sua estratégia básica é semelhante à utilizada pela MAFFT, no qual refina- mentos horizontais são aplicados ao Alinhamento Progressivo, fornecendo melhorias significativas na precisão e velocidade (EDGAR, 2004b). Figura 2.20: Esquema de funcionamento do algoritmo MUSCLE. Fonte: Adaptado de (EDGAR, 2004b). O primeiro estágio cria um rascunho de Alinhamento Progressivo que será me- lhorado nos próximas estágios. Utiliza-se de uma medida de similaridade computada entre todos os possíveis pares de sequências do conjunto de entrada, por meio de um método probabilístico de contagem k-mer (GUERRA; BUCKLER, 2017), ou cons- truindo o alinhamento global dos pares por meio da medida de identidade fracionária. A partir da medida de similaridade entre todas as sequências do conjunto, uma matriz de distância triangular é calculada considerando-se as semelhanças entre os pares. Por fim, uma árvore guia é construída a partir da matriz de distância, adotando- 64 se um algoritmo baseado na UPGMA ou Neighbor-Joining e uma raiz para a árvore é identificada. Finalmente, utilizando-se da árvore guia, o Alinhamento Progressivo é construído seguindo a ordem de ramificação da árvore, produzindo um alinhamento múltiplo de todas as sequências de entrada até a raiz da árvore. O segundo estágio é uma fase que pode ser iterativa e é responsável por produ- zir uma melhoria progressiva do alinhamento, por meio da evolução da árvore guia. Com isso, é possível produzir um novo Alinhamento Progressivo de acordo com essa árvore. Nesse estágio, a medida de similaridade entre cada par de sequências é calcu- lada usando a identidade fracionária computada no alinhamento múltiplo atual. Uma nova árvore é produzida por meio do cálculo de uma matriz de distâncias, utilizando- se da distância de Kimura e aplicando-se um método de agrupamento na matriz de distâncias (EDGAR; BATZOGLOU, 2006). A árvore obtida é comparada com a árvore obtida na etapa anterior, que pode ser a árvore do primeiro estágio ou a árvore construída na iteração anterior do segundo estágio. A comparação identifica o conjunto de nós internos para os quais a ordem de ramificação foi alterada. O novo Alinhamento Progressivo é construído, alterando- se apenas as partes do alinhamento para os quais as ramificações internas da árvore sofreram alterações, até que alinhamento encontre a raiz. Neste ponto, o algoritmo pode terminar ou retornar para mais uma iteração do segundo estágio ou seguir para o terceiro estágio. Desta forma, se o segundo estágio for executado mais de uma vez e o número de alterações não diminuir, o processo de melhoria da árvore será considerado convergente e a iteração será encerrada. O terceiro estágio é uma fase de refinamento iterativo que se utiliza de uma variante do particionamento restrito dependente de árvore(SAITOU; NEI, 1987). Neste, cada ramificação da árvore guia é excluída, gerando dois grupos de sequências disjuntos, para quais todos os nós serão visitados em ordem de distância decrescente a partir da raiz de cada subárvore. Com isso, pode-se extrair um perfil de cada subconjunto 65 do alinhamento atual para produzir um novo alinhamento perfil-a-perfil. Descartando as colunas sem resíduos (gaps), os perfis são realinhados e calcula-se a pontuação da soma de pares (SP - Sum-of-Pairs) do novo alinhamento. Se a pontuação aumentar, o novo alinhamento é mantido, caso contrário é descartado. Se todas as arestas foram visitadas sem que uma mudança seja feita ou que um número máximo de iterações definido pelo usuário foi atingido, o algoritmo é finalizado. Caso contrário, ele retorna para uma nova iteração do terceiro estágio. As arestas visitadas em ordem decrescente de distância da raiz têm o efeito de primeiro realinhar sequências individuais, depois grupos intimamente relacionados (EDGAR, 2004a; WANG et al., 2015). 2.7 Considerações Neste capítulo, para um bom entendimento do trabalho, apresentou-se os conceitos básicos da biologia molecular, das heurísticas para Alinhamento Múltiplo de Sequên- cias e para reconstrução da árvore guia, bem como uma revisão bibliográfica das fer- ramentas mais utilizadas para o problema de rearranjo de árvores e da reconstrução filogenética. Apresentaram-se também os resultados obtidos pelo método TRMLE, o qual será uma base para desenvolvimento do método proposto pelo presente trabalho, a fim de melhorar a acurácia das ferramentas que utilizam o Alinhamento Progressivo. Desta forma, pretende-se contribuir com a produção de alinhamentos finais com mais signi- ficado biológico, por meio de uma árvore guia com tamanho minimizado e próxima da filogenia verdadeira. Além disso, pretende-se contribuir com um método que man- tenha o tempo de execução em níveis aceitáveis e que permita operar com grande volumes de dados. Isto destaca-se como de suma importância para os trabalhos dos pesquisadores, principalmente devido ao grande volume de dados biológicos que estão sendo produzidos nos últimos anos, devido ao advento dos sequenciadores NGS. No próximo capítulo, será apresentado o desenvolvimento do trabalho proposto. Capítulo 3 Desenvolvimento do Trabalho Este capítulo tem por objetivo apresentar os detalhes das atividades executadas para implementação do método proposto no presente trabalho. 3.1 O Método Proposto O método proposto no presente trabalho foi nomeado de TreeRMEP, que é abrevi- ação do termo Rearranjo de Árvores Com o Princípio da Evolução Mínima (Tree Rearrangement with Minimum Evolution Principle). O método utiliza-se os conceitos de refinamento de árvores encontrados em (GIRI- BET, 2007), combinados, especificamente, com a estratégia TBR descrita em (HSIEH et al., 2015), que contribui para redução do espaço de busca e aceleração da procura pela melhor árvore, baseando-se no conceito do Princípio da Evolução Mínima (ME) (KIDD; SGARAMELLA-ZONTA, 1971), no qual procura-se pela topologia de árvore que fornece uma soma mínima dos comprimentos de suas ramificações (RZHETSKY; NEI, 1993) e sua premissa básica é de que a evolução das espécies ocorre de maneira lenta e progressiva. Portanto, uma árvore com distâncias mínimas entre seus nós tem maior probabilidade de ser a árvore filogenética verdadeira e representar com maior proximidade a evolução verdadeira das espécies (BASTKOWSKI et al., 2015). 67 Com o TreeRMEP promovem-se trocas na posição dos nós da árvore guia e assim altera-se sua topologia, com objetivo de encontrar uma árvore com tamanhos mínimos, menor que a árvore guia anterior. Isto é uma tarefa com grande consumo de tempo computacional e não são todas as mudanças que trazem melhorias. Neste ponto, o ME é empregado para selecionar primeiro os nós com maior proba- bilidade de trazer melhorias e, desta forma, o método deve evitar as mudanças que não produzem bons resultados, diminuindo o espaço de busca e acelerando a execução do método, reduzindo o consumo do tempo computacional. As mudanças na topologia da árvore requerem ajustes nos tamanhos das arestas modificadas e das novas arestas criadas e, assim, é necessário o desenvolvimento de uma função para recalcular esses tamanhos. Por fim, a nova árvore produzida precisa ser avaliada e comparada com o tamanho da árvore guia inicial para determinar se houve uma melhora, ou seja, se o tamanho da nova árvore é melhor do que a árvore inicial. Caso a nova árvore seja menor que a anterior, essa é descarta e substituída pela nova árvore. Na Figura 3.1 encontra-se representado o fluxo de execução do algoritmo 1 do método TreeRMEP, que recebe como parâmetros de entrada uma árvore gerada por uma ferramenta de AMS e a sua matriz de distâncias, retornando na saída do processo, uma nova árvore. Inicialmente o método converte uma árvore dada como entrada para uma estrutura de árvore binária e que será utilizada pelo método. Dessa forma, torna-se o método independente da estrutura de árvore padrão usado pelas ferramentas de AMS, per- mitindo a sua portabilidade para outras ferramentas. Para isso, é necessário apenas a construção de um método auxiliar que interprete a estrutura padrão da ferramenta AMS e transforme na estrutura de árvore binária usada pelo TreeRMEP. 68 Figura 3.1: Fluxograma de execução do método. Fonte: Elaborado pelo autor. O uso de uma árvore binária como uma estrutura de dados capaz de armazenar todos os dados de um nó em um único local, mostrou-se uma estratégia mais segura e rápida para o desenvolvimento do trabalho. A estrutura da árvore binária imple- mentada e adequada para o acoplamento está representada na Figura 3.2. Pode-se observar que todos os dados necessários para construção e manipulação da nova ár- vore guia estão reunidos em uma única estrutura e, desta forma, o processo de leitura e transferência das estruturas da ferramenta AMS para a estrutura btree do TreeRMEP mostrou-se seguro e estável. 69 Algorithm 1 Algoritmo de rearranjo proposto procedure TREERMEP(tree,m_dist) . tree: árvore inicial . m_dist: matriz de distâncias btree← new btree(tree, m_dist) . Construir árvore binária m_ord← new array() . Matriz de ordenação nos← nos(btree) . Número de nós da árvore binária cont← 0 while cont <= nos*0,8 do . Executar em 80% dos nós, . evitando mudanças ruins m_ord← ordenar(btree) . Ordenar nós da árvore principal ind← 0 while (ind < nos) do no_sel← btree(m_ord[ind]) . Selecionar o nó de posição ind S← sub-árvore em T induzida por {u, v} dist← determinar posição para movimento de S em T no_dis← btree(m_ord[dist]) . Selecionar o nó de posição dist if no_dist.parenth <> no_sel.parenth then . Mesmo pai, ignora new_btree←mover S para posição dist em T if new_btree < btree then btree← new_btree ind← ind + 1 cont← cont + 1 tree← criar nova árvore usando btree return tree Figura 3.2: A Estrutura de dados da árvore binária. Fonte: Elaborada pelo autor. 70 Com a árvore binária construída, ordena-se as suas arestas pelos tamanhos em or- dem decrescente, aplicando-se as técnicas descritas em (HSI