Métodos computacionais

reconstrução de filogenias

Métodos computacionais

Palavras marcadas com um asterisco (*) são definidas ao final de cada página, num vocabulário.

Links em laranja são links para páginas externas

Links em verde são links para outras páginas deste site

Estratégias para busca de árvores mais parcimoniosas

INTRODUÇÃO

Como foi mencionado anteriormente, o método de reconstrução de filogenias empregado por Hennig é perfeitamente aplicável a pequenas matrizes de dados (poucos caracteres e/ou táxons terminais), conduzindo-nos a soluções parcimoniosas com relativa facilidade. Contudo, para matrizes de tamanho apenas moderado, a construção das árvores representando as informações de cada caráter e sua combinação em árvores parcimoniosas já se torna uma tarefa demasiadamente trabalhosa, infactível até, para nossos cérebros. Para proceder à análise de tais matrizes, portanto, necessitamos do emprego de programas computacionais.

ÁRVORES NÃO ENRAIZADAS E POLARIZAÇÃO A POSTERIORI

O método de inferência filogenética de Hennig e suas variantes não computacionais (manuais) iniciam-se com a polarização dos caracteres, o que, em geral, é feito através do método de comparação com grupos externos. A isto se chama polarização a priori*. Contudo, os algorítimos empregados pelos computadores para buscar as hipóteses filogenéticas mais parcimoniosas fazem o procedimento inverso: primeiro encontram a árvore não-enraizada mais curta (mais parcimoniosa) e, depois, empregam o grupo externo para 'enraizar' a árvore, o que define, então, a polarização dos caracteres (polarização a posteriori*). Veja, na Figura 1, abaixo, um exemplo de uma árvore não enraizada:

figura 1 - árvore não enraizada

A figura acima mostra uma árvore não enraizada. Ela representa uma hipótese incompleta das ralações filogenéticas entre as espécies 'A', 'B', "C' e 'D'. A hipótese é incompleta, porque não contém informação sobre a direção em que a evolução ocorre. Ela indica, ainda, que o caráter '1' sofre uma modificação entre os dois pares de espécies, mas não indica qual dos dois estados do caráter '1' é o plesiomórfico, sabe-se, apenas, onde sua mudança ocorre, num ou noutro sentido.

Uma árvore não enraizada define um número restrito de hipóteses filogenéticas diferentes, dentre as inúmeras árvores que poderiam associar um determinado número de táxons. A hipótese final é definida pelo ponto em que a árvore original será enraizada e quem define o ponto onde ela será enraizada é o grupo externo. A figura abaixo explica isto:

figura 2 - árvore não enraizada e
definição de hipóteses

A figura acima mostra as quinze hipóteses possíveis para explicar as relações entre quatro táxons terminais. Apenas cinco delas (1, 4, 8, 11 e 13) são congruentes com a árvore não enraizada mostrada acima (igual à da Fig. 1).

As diferenças entre elas devem-se somente ao ponto de enraizamento, que define a direção em que a evolução ocorreu.

(de Wiley & Lieberman, 2010)

Os programas de computador, então, primeiro constroem as árvores não-enraizadas, depois plotam, nelas, os caracteres e contam o número de transformações (passos) que eles têm de sofrer em cada hipótese para, finalmente, escolherem a(s) hipótese(s) mais parcimoniosa(s). Só então, as hipóteses mais parcimoniosas são enraizadas, considerando a posição dos grupos externos, definindo-se a polarização dos caracteres (Fig.3):

figura 3 - Polarização a posteriori

A figura acima mostra: 1) a matriz de caracteres (em cima); 2) os locais em que cada caráter sofre uma modificação em uma árvore não enraizada (no meio); e 3) as polarizações dos caracteres em duas árvores derivadas da mesma árvore não-enraizada, considerando duas espécies diferentes como grupo-esterno.

(de Wiley & Lieberman, 2010)

O uso de programas de computador nos permite empregar diferentes estratégias na busca de árvores parcimoniosas, de acordo com o tamanho de nossa matriz de dados. Para matrizes pequenas ou moderadas (com até cerca de 20 táxons terminais) podemos usar métodos de busca exata, que encontrarão, com certeza, a(s) árvore(s) mais parcimoniosa(s). Para matrizes maiores, entretanto, o emprego destes métodos leva um tempo proibitivo e frequentemente extrapola a capacidade de computação das máquinas. Nestes casos, empregam-se métodos heurísticos* que vão encontrar árvores parcimoniosas, embora não necessariamente as mais parcimoniosas possíveis.

MÉTODOS EXATOS

Dois tipos de métodos exatos são implementados nos programas atuais de computador:

1) Busca exaustiva

Os algoritmos* que fazem a busca exaustiva constroem todas as árvores dicotômicas* possíveis para explicar as relações entre os táxons do grupo de estudo. As transformações dos vários caracteres é então 'marcada' em cada uma dessas árvores e o comprimento (número de transformações dos caracteres) de cada uma delas é calculado. As árvores mais parcimoniosas são, então, retidas na memória do computador e apresentadas como resultado do processo.

Para construir todas as árvores, os algoritmos estabelecem várias “rotas”, cada uma constituindo um conjunto de árvores obtidas a partir da modificação de uma primeira árvore. Como o entendimento deste processo é necessário para o entendimento de alguns dos demais processos descritos a seguir, vamos explicá-lo com algum detalhe, tomando por base o algoritmo descrito por Swofford & Olsen (segundo Kitching et al, 1998):

Passo 1: Com os primeiros três táxons na matriz de dados, constrói-se a única árvore (não enraizada) possível para descrever as relações entre esses três táxons (“árvore-raiz”) (Fig. 4). Note que todas as modificações na posição dos táxons terminais, nesta árvore, vão resultar nas mesmas relações entre eles:

figura 4 - árvore inicial (árvore-raiz)

Árvore não enraizada inicial no processo de busca exata, mostrando a relação entre os três primeiros táxons na matriz de dados (em cima). As outras três árvores (embaixo) são formas alternativas da mesma árvore que, não estando enraizadas, representam as mesmas relações entre os três táxons.

Passo 2: Partindo-se da árvore inicial, adiciona-se o próximo táxon da matriz. Note que este quarto táxon pode ser adicionado em três posições diferentes (Fig. 5), cada uma resultando em uma árvore distinta, representando relações efetivamente diferentes para os quatro táxons. Cada uma dessas árvores alternativas, resultantes da inclusão deste quarto táxon, dá início a uma rota diferente para a construção de árvores subsequentes (veja o passo 3, abaixo).

figura 5 - estabelecimento das rotas
iniciais

As três árvores resultantes da adição do quarto táxon (D - embaixo) à árvore inicial (em cima). Note que cada uma dessas árvores representa uma hipótese diferente para as relações entre os táxons A, B, C e D. Essas árvores definem as três primeiras rotas de busca (veja abaixo, no texto).

Passo 3: A cada uma das árvores obtidas no passo 2 (Fig. 5), vamos adicionar o quinto táxon (E), em todas as posições alternativas que representem hipóteses distintas para as relações entre ele e os demais táxons. Na Figura 6, representa-se a adição deste quinto táxon a apenas uma das árvores obtidas no passo anterior (uma rota). O mesmo seria feito com as outras duas árvores (que representariam outras duas rotas).

figura 6 - adição do quinto táxon

As cinco árvores resultantes da adição do quinto táxon (E) à primeira das três árvores obtidas a partir da adição do quarto táxon (D) à árvore inicial apresentada na Figura 4. Note que cada uma dessas árvores representa uma hipótese diferente para as relações entre A, B, C, D e E.

Esta representa uma das três rotas possíveis para a construção de árvores; as outras duas derivariam da adição de E em todas as posições possíveis nas outras duas árvores representadas na Figura 4.

Se a matriz de dados incluir apenas cinco táxons, então todas as 15 árvores dicotômicas que se poderia construir teriam sido conseguidas ao término deste terceiro passo. Se a matriz tivesse mais táxons, passar-se-ia ao quarto passo, em que o sexto táxon seria adicionado em todas as sete posições possíveis em cada uma das 15 árvores obtidas no passo três. Cada uma destas 15 árvores daria início a uma nova rota. Para seis caracteres, o total de árvores obtido seria igual a 105! Veja que o número de árvores sobe vertiginosamente a cada adição de um novo táxon.

Após se adicionar todos os táxons, seguindo todas as rotas possíveis, então se calcularia o comprimento de cada uma das árvores obtidas, retendo, como resultado, aquelas igualmente mais parcimoniosas.

2) Branch-and-Bound

Como se viu, com o aumento do número de táxons analisados, o número de árvores que podem ser construídas atinge rapidamente números astronômicos, de tal forma que, mesmo para um computador, a busca exaustiva passa a consumir um tempo proibitivo, podendo, ainda, exceder a capacidade de computação da máquina. Para se encontrar todas as árvores mais parcimoniosas existentes, existe um outro método de busca exaustiva que não precisa, necessariamente, pesquisar todas as árvores possíveis. Os passos para a busca da árvore mais parcimoniosa, pelo método de branch-and-bound são os seguintes:

Passo 1: Constrói-se uma árvore inicial, contendo todos os táxons. Em geral, esta árvore é construída empregando-se um dos métodos heurísticos discutidos abaixo. O comprimento desta árvore é tomado como o limite (bound) superior na busca das árvores subsequentes;
Passo 2: Começa-se a construir árvores, como no processo de busca exaustiva. Aqui, entretanto, cada vez que um táxon é adicionado em uma posição, o comprimento da árvore é calculado. Quando este comprimento atinge o limite superior (bound) determinado no primeiro passo, aquela rota é abandonada, já que a adição de novos táxons vai elevar o comprimento das próximas árvores naquela rota, acima do comprimento da árvore inicial (que será, portanto, mais parcimoniosa que as próximas árvores a serem geradas naquela rota).
Caso se chegue ao fim de uma rota e a árvore final, com todos os táxons, tenha comprimento igual ao do limite superior estabelecido, ela é guardada como uma das soluções mais parcimoniosas. Se, por outro lado, ela for mais curta que o limite superior, então a primeira árvore é abandonada, o comprimento desta nova árvore é tomado como novo limite e a busca continua em outras rotas. Quando todas as rotas forem examinadas, as árvores mais parcimoniosas terão sido encontradas.

O método de branch-and-bound, desta forma, pode reduzir consideravelmente o número de árvores a ser construído e avaliado e o tempo de computação pode, então, ser bastante diminuído. Apesar disto, este método não é aplicável a matrizes superiores a cerca de 25 táxons, a partir de quando o tempo de computação também se torna impraticável. A duração do processo vai depender da eficiência do algoritmo de busca, da quantidade de homoplasia nos caracteres e da velocidade de computação da máquina empregada na análise. A eficiência da busca pode ser aumentada com a implementação de algumas estratégias, como: a) uso de métodos heurísticos eficientes para garantir que o limite superior inicial seja o menor possível; e b) emprego de rotinas que reconheçam e adicionem primeiro, à árvore, táxons muito divergentes, o que leva a grandes aumentos iniciais no início do processo, fazendo com que o limite superior seja atingido rapidamente e possibilitando a eliminação precoce de um grande número de rotas.

Nos piores cenários, em que grande parte do comprimento da árvore se deve às modificações ocorridas nos táxons terminais, o método de branch-and-bound se torna equivalente ao de busca exaustiva.

MÉTODOS HEURÍSTICOS

Para a análise de matrizes grandes (acima de cerca de 25 táxons e dependendo da quantidade de homoplasias e da qualidade do computador empregado), é necessário o emprego de métodos heurísticos na busca das árvores mais parcimoniosas. Esses algoritmos procuram as árvores mais parcimoniosas por aproximação, por tentativa-e-erro. Eles partem da construção de uma árvore inicial que é, então, rearranjada, em busca de árvores de comprimento menor. O resultado deste processo nem sempre são as árvores do menor comprimento possível.

Um problema importante que se apresenta no emprego dos métodos heurísticos é o das “ilhas de árvores”. Para entender este problema, vamos imaginar que todas as árvores possíveis de se construir estejam distribuídas numa superfície de tal forma que árvores com topologias e comprimentos muito semelhantes estejam agrupadas e que estes agrupamentos estejam separados uns dos outros por uma matriz de árvores menos parcimoniosas. Estes agrupamentos de árvores de comprimento semelhante seriam as “ilhas” (Fig. 7).

figura 7 - ilhas de árvores

A figura ao lado mostra agrupamentos de árvores (representadas por linhas verticais) de topologias e comprimentos semelhantes em 'ilhas' separadas por árvores menos parcimoniosas. (O aumento da parcimônia corresponde a uma redução do comprimento da árvore).

Podemos imaginar os métodos heurísticos como barcos que “navegam” nesta superfície de árvores, com a recomendação de seguir sempre em direção a árvores mais parcimoniosas. Seguindo esta regra, eles ficam “encalhados” quando encontram uma ilha de árvores mais curtas que a média. Isto porque, para saírem desta ilha, eles têm de navegar por uma área ocupada por árvores menos parcimoniosas, o que os leva de volta à ilha da qual saíram. Desta forma, se houverem várias ilhas de árvores resultantes dos dados disponíveis e as topologias das árvores em cada ilha diferirem muito das árvores de outras ilhas, esses métodos só encontrarão as árvores realmente mais parcimoniosas, se elas estiverem na primeira ilha encontrada; caso contrário, as árvores encontradas serão subparcimoniosas.

Uma solução para este problema é repetir o processo várias vezes, iniciando-o de diferentes pontos, de tal forma que o “percurso” na superfície de árvores seja sempre diferente e a chance de se encontrar a(s) ilha(s) que contenha(m) as árvores mais parcimoniosas seja aumentada.

1) Adição passo-a-passo (stepwise addition)

Este processo começa pela construção de uma árvore de três táxons. A ela vão sendo adicionados os demais táxons, um a um, até que a árvore esteja completa. Há várias formas de se definir quais três táxons vão constituir a árvore inicial e, depois, em que ordem e em que ramo os demais táxons serão adicionados a ela:

Na ordem em que os táxons se encontram na matriz. Os três primeiros táxons da matriz de dados são empregados na construção da árvore inicial e os demais táxons são acrescentados na ordem em que eles se se encontram na matriz. O comprimento de cada árvore obtida com a adição de um novo táxon em cada ramo disponível na árvore anterior é avaliado e a árvore mais curta selecionada para a adição do táxon seguinte. Dificilmente este procedimento encontra as árvores de comprimento mínimo.
Ao acaso. Um gerador de números pseudo-randômicos é empregado para numerar os táxons que são, então, ordenados segundo estes números e incluídos na árvore, nesta ordem, como no método anterior. Também não é um método muito eficiente de busca das árvores mais parcimoniosas.
“Simples”. Aqui, um táxon é escolhido como táxon de referência. Ele pode ser qualquer um dos táxons na matriz, mas, em geral, é escolhido entre os grupos externos. Em seguida, calcula-se a distância Manhatan (um índice de dissimilaridade) entre o táxon de referência e todos os demais. O táxon de referência e os dois mais próximos dele (menor distância) são empregados para a construção da árvore inicial. Os demais táxons são incluídos na ordem crescente de suas distâncias ao táxon de referência.
Mais próximo. Neste caso, a ordem em que os táxons são adicionados à árvore em construção não é pré-determinada como nos métodos anteriores. Primeiro o comprimento de todas as árvores de três táxons é calculado e a mais curta delas escolhida para ser a árvore inicial. Em seguida, o comprimento da árvore de quatro táxons é calculado para a adição de todos os táxons restantes, em cada posição possível. A árvore mais curta é retida para o próximo passo. Nos passos subsequentes, a adição de cada novo táxon é avaliada como para a adição do primeiro táxon. Este método requer muito mais tempo de computação do que os antecedentes. Nos métodos acima, o número de árvores a ser avaliado era igual ao número de ramos em que cada novo táxon poderia ser adicionado; neste último método, o número de árvores a ser avaliado a cada passo é igual ao número de ramos disponíveis para a adição do novo táxon multiplicado pelo número de táxons disponíveis para serem adicionados.

Uma desvantagem de todos os métodos acima é que eles retêm apenas uma árvore em cada passo, quando um novo táxon é adicionado, mesmo que algumas ou várias árvores parciais igualmente parcimoniosas forem encontradas. Estas árvores são produzidas quando mais de um táxon pode ser adicionado num dado momento ou quando há mais de um ramo aos quais um determinado táxon pode ser adicionado, gerando árvores igualmente parcimoniosas.

Outro problema é que a escolha de um determinado táxon a ser adicionado, num determinado passo, pode ser a solução mais parcimoniosa naquele momento, mas pode representar uma solução sub-ótima, depois que novos táxons são adicionados, gerando uma árvore final que não seja a mais parcimoniosa. Estes métodos, portanto, não têm como avaliar o efeito da adição de um táxon no resultado final, mas, apenas, naquele momento. Uma solução para este problema é a retenção de mais de uma árvore em cada passo, gerando rotas de busca alternativas para os passos subsequentes.

2) Permuta de ramos (branch swapping)

Os processos de permuta de ramos rearranjam os ramos de uma primeira árvore obtida a partir de um outro método, na tentativa de encontrarem árvores de comprimento menor. Assim, um ramo da árvore inicial é retirado e recolocado em uma posição diferente, produzindo uma nova árvore. O comprimento desta nova árvore é, então, comparado com o da árvore original. Se ele for mais longo, a nova árvore é descartada, se for mais curto, ela é retida. O processo continua e as árvores mais parcimoniosas vão substituindo as de maior comprimento, até que o processo termine. Vários critérios para se rearranjar os ramos de uma árvore podem ser empregados. Alguns deles são os seguintes:

Permuta de vizinhos mais próximos (NNI – nearest neighbour interchange). Considera que cada ramo interno de uma árvore (uma espécie ancestral) liga duas “sub-árvores” de um lado com duas do outro lado. Uma permuta de vizinhos mais próximos troca um ramo de uma das sub-árvores por outro da outra sub-árvore (Fig. 8).

figura 8 - permuta de vizinhos mais
próximos

Na primeira permuta o ramo “C” da sub-árvore da direita (vermelha) foi permutado com o ramo “D” da sub-árvore da esquerda (azul). Na segunda permuta, o ramo “E(FG)” foi trocado pelo ramo “C”.

Poda e re-enxerto (SPR – subtree pruning and regrafting). Aqui, uma árvore é dividida em duas em um nó, produzindo duas sub-árvores, uma com um ramo livre e outra não. A sub-árvore com o ramo livre é, então, re-enxertada em um ramo interno ou em um táxon terminal da outra sub-árvore (Fig. 9). O ramo livre, neste caso, seria a 'raiz' da sub-árvore e define o ponto pelo qual ela vai ser re-enxertada na outra sub-árvore. Embora seja eficaz na redução do comprimento de árvores pouco parcimoniosas, este método é pouco eficiente na otimização de árvores, quando se lida com matrizes grandes ou com grandes quantidades de homoplasias (Nixon, 1999).

figura 9 - poda e re-enxerto (spr)

O ramo AB da sub-árvore da esquerda (vermelha) foi podado e re-enxertado, por meio de seu ramo livre a G, na sub-árvore da direita (azul).

Bi-secção e re-conexão de árvores (BB – branch braking; TBR – tree bisection and reconection). Uma árvore é dividida entre dois nós e os ramos livres deixados em cada uma delas é extirpado, produzindo duas sub-árvores não-enraizadas. As duas sub-árvores são, então, re-conectadas através da criação de um novo ramo que ligue um ramo selecionado em uma das sub-árvores a outro ramo selecionado na outra sub-árvore. o 'novo ramo' criado seria a raiz que poderia ser colocada em cada uma das várias posições possíveis na sub-árvore não enraizada, definindo, desta forma, diferentes pontos pelos quais ela poderia ser reconectada à outra sub-árvore. Todas as bi-secções e re-conexões possíveis são avaliadas (Fig. 10).

figura 10 - bi-secção e reconexão de árvores (TBR)

A árvore inicial foi dividida no ramo que une (C(AB)) a (D(E(FG)). Os ramos livres definidos pela bi-secção foram eliminados e as duas sub-árvores resultantes ligadas por B e G, que foram conectados por um ramo criado para uni-los.

Entre os métodos de permuta de ramos, o TBR é o mais eficiente. Entretanto, ele também está sujeito a ser aprisionado em ilhas de árvores igualmente parcimoniosas com topologias apenas ligeiramente diferentes. Uma estratégia geral para reduzir as chances da análise encalhar numa dessas ilhas inclui as seguintes medidas (Nixon, 1999):

Fazer várias buscas (réplicas), cada qual começando por um conjunto de árvores muito diferentes. Iniciar diferentes buscas por árvores com topologias diferentes aumenta a chance de se investigarem várias ilhas diferentes, aumentando a chance de se encontrarem as árvores mais parcimoniosas.
Reduzir o número de árvores retidas em cada réplica, minimizando o tempo despendido em cada ilha. Esta medida representa uma mudança de estratégia na busca de árvores, já que, antes, acreditava-se que apenas com a retenção de todas as árvores igualmente parcimoniosas, em cada passo da permuta de árvores, seria possível encontrar as árvores mais parcimoniosas (e.g. Forey et al., 1992). Entretanto, tem sido apontado que aumentar o número de árvores retidas em cada réplica não é uma medida eficiente, porque essas árvores, oriundas de uma mesma ilha, variam muito pouco para levar a busca a novas ilhas diferentes umas das outras.
Do conjunto de árvores resultantes de muitas réplicas, tomar subconjuntos para buscas mais intensivas, com a retenção de muitas ou todas as árvores resultantes.

Com estas estratégias, a velocidade de busca pode ser aumentada em cerca de 50 vezes, e frequentemente se encontram árvores mais parcimoniosas do que as encontradas pelo uso do método TBR simples. Apesar disto, a análise de matrizes grandes (com mais de 100 táxons) e/ou com grande número de homoplasias ainda pode ser demasiadamente demorada. Para melhorar a eficiência dos processos de busca, novas estratégias foram desenvolvidas e implementadas nos programas modernos de análise filogenética, que serão apresentados no tema "Métodos modernos".

Vocabulário

Algorítimo: uma sequência de instruções que devem ser seguidas na ordem em que são apresentadas para a solução de um problema. Programas de computador são construídos na forma de algorítimos.
A posteriori: interpretação feita com base em informações prévias. No contexto da análise filogenética, refere-se à determinação da polaridade dos caracteres, depois que a(s) hipótese(s) mais parcimoniosa(s) para as relações filogenéticas entre as espécies do grupo de estudo foram encontradas.
A priori: interpretação feita com base em suposições anteriores à obtenção de informações. No contexto da análise filogenética refere-se à determinação da polaridade dos caracteres, antes de se iniciar a busca pela(s) hipótese(s) mais parcimoniosa(s) para as relações filogenéticas entre as espécies do grupo de estudo.
Dicotômico: bifurcado. Árvores dicotômicas são aquelas em que cada ramo se divide em dois ramos (exceto os ramos terminais, que não se dividem).
Heurístico: conjunto de regras e/ou métodos empregados para solucionar um problema complexo, empregando estratégias que ignoram parte da informação e em que o sucesso é medido pela quantificação da proximidade de um objetivo. São 'atalhos' usados para a solução de problemas complexos.

REFERÊNCIAS

Kitching, I.J.; Forey, P.L.; Humphries, C.L. & Williams, DM. 1998. Cladistics – The Theory and Practice of Parsimony
Analysis. 2ed. The Systematics Association Publication no. 11. Oxford, Oxford University.

Nixon, K.C. 1999. The parsimony ratchet, a new method for rapid parsimony analysis. Cladistics 15:407-414.

Wiley, E. O. & Lieberman, B. S. 2011. Phylogenetics – Theory and Practic of Phylogenetic Systematics. Hoboken, John
Wiley & sons.

Este tema continua em:

"métodos modernos"

ver

reconstrução de filogenias