Técnicas Algorítmicas para Construção de Árvores Filogenéticasyw/capes/capes-cofecub-2009/projeto-karla... · Rev. Cient. Fac. Lourenço. Filho - v.4, n.1, 2005 83 molecular

Técnicas Algorítmicas para Construção de Árvores Filogenéticas

Lia Cysne Pinteiro Gerardo Valdisio Rodrigues Viana

Universidade Estadual do Ceará

Fernando Antônio de Carvalho Gomes

Marina Gomes Viana

Universidade Federal do Ceará Resumo:

A construção de árvores filogenéticas auxilia a Biologia a explicar os possíveis relacionamentos

entre as espécies atuais e a deduzir as histórias evolutivas das mesmas. Conhecidas simplesmente como filogenia, tais árvores possuem folhas que representam as espécies e nós que correspondem a seus ancestrais. A partir das seqüências de DNA, disponíveis em grandes bases, é possível inferir filogenias utilizando-se de dados como distâncias e características, relativos aos genes de cada espécie. A distância estima a distância evolutiva entre as espécies, enquanto a característica refere-se à presença ou ausência de certos genes em determinados genomas. O objetivo deste trabalho é apresentar algumas formalizações para o problema da filogenia, com abordagem da Teoria da Computação, que possibilitem obter sua solução em tempo hábil, considerando que o tempo de busca da melhor solução é inadmissível pois este é um problema NP-Completo [Boadlaender, 1992]. Palavras-chave: Biologia Computacional, Filogenia, Evolução.

Introdução

Graças à ciência moderna, sabe-se atualmente que a diversidade biológica entre os grupos

de organismos existentes na Terra é resultado de um processo vagaroso e progressivo de

transformações sofridas pelas espécies, ao qual se deu o nome de evolução [SETÚBAL, 1997].

O desenvolvimento de técnicas capazes de explicar a história evolutiva dos organismos atuais é

uma das aplicações mais antigas da Biologia Computacional.

Tais técnicas aceitam como entrada as seqüências de DNA de diferentes organismos ou de

proteínas, para reconstruir o parentesco entre as espécies. Em seguida, essas informações são

82 Rev. Cient. Fac. Lour. Filho - v.4, n.1, 2005

associadas a uma escala temporal, o que é chamado de filogenia molecular. A representação

gráfica desses resultados é feita na forma de árvores filogenéticas [PROSDOCIMI, 2003].

Na Figura 1 tem-se um exemplo de uma árvore filogenética, onde as folhas representam

espécies de primatas, nós externos correspondem a entidades biológicas, já os nós internos

correspondem aos seus possíveis ancestrais; enquanto as arestas expressam as relações

evolutivas, ou seja, mudanças de propriedades entre os nós.

Observando-se ainda a Figura 1, é possível notar que os seres humanos e os chimpanzés

estão mais próximos entre si do que das demais espécies de primatas, fato que possibilita

concluir que ambos devem descender de um ancestral comum, do qual nenhum dos outros se

origina.

Figura 1– Exemplo de árvore filogenética para alguns primatas [SETÚBAL, 1997]

No entanto, a filogenia da Figura 1 pode corresponder a uma árvore hipotética, pois os

dados dos antepassados mais longínquos não estão disponíveis. Portanto, são realizadas

comparações entre os organismos atuais para que se possa inferir tais ancestrais, o que faz com

que as árvores construídas não sejam obrigatoriamente verdadeiras [SETÚBAL, 1997].

Já as árvores filogenéticas representam uma maneira legítima de entender os processos

biológicos e a evolução dos diversos caracteres. Estes estudos e as ferramentas criadas para este

fim têm aplicações tão diversas como procurar entender a origem do homem ou reconstituir a

história epidemiológica da AIDS a partir de dados do genoma do HIV [PROSDOCIMI, 2003].

Este trabalho tem como objetivo dar uma breve introdução a uma das aplicações mais

antigas da biologia computacional, a filogenia; explanando os conceitos básicos da biologia

Rev. Cient. Fac. Lourenço. Filho - v.4, n.1, 2005 83

molecular e apresentando os algoritmos existentes para auxiliar na construção de árvores

filogenéticas.

1 BIOLOGIA COMPUTACIONAL

De maneira ampla, a Biologia Computacional pode ser entendida como sendo a aplicação

de técnicas e ferramentas da ciência da computação aos problemas da biologia, ou seja, trata-se

de uma área interdisciplinar voltada para o desenvolvimento de modelos quantitativos para

explicar determinados fenômenos biológicos. As técnicas computacionais têm sido mais

necessárias e conseqüentemente mais úteis a uma determinada área da biologia, a biologia

molecular [SETÚBAL, 1997].

A fim de desvendar as características que os seres vivos possuem ou possuirão no futuro,

os biólogos começaram a desenvolver métodos de seqüenciamento do genoma, que foram

evoluindo e ao longo dos anos deram origem aos seqüenciadores automáticos de DNA. A partir

deste momento, surgiu uma demanda por soluções computacionais mais eficientes para analisar

a gigantesca quantidade de seqüências e ajudar a resolver os problemas relacionados ao estudo

dos genomas [SETÚBAL, 1997].

Assim nasceu a Biologia Computacional, uma área cercada por algoritmos complexos e

problemas ainda sem solução conhecida. Muitos problemas não apresentam soluções exatas, e

muitas vezes estão bem longe da solução correta, pois são resultados de heurísticas.

A biologia computacional, no entanto, necessita transpor a barreira da comunicação entre

os profissionais das diferentes áreas que a compõem. Visto que, enquanto biólogos estão mais

interessados em resolver problemas concretos, levando em consideração os erros e as incertezas

que ocorrem na prática; os cientistas da computação por sua vez procuram soluções eficientes

para problemas bem definidos e abstratos. Fato que faz com que os modelos criados por estes

fiquem distantes da realidade dos problemas biológicos. Porém, este problema já vem sendo

solucionado com a formação de profissionais conhecidos como bioinformatas.


1.1 Sistemática Filogenética

O objetivo central do trabalho da sistemática é a diversidade biológica. Os sistematas1

devem procurar descrever essa diversidade, tentando encontrar uma ordem subjacente a ela e

compreendendo os processos que são responsáveis pela geração da mesma e por fim apresentar

um sistema geral de referências sobre a diversidade biológica [AMORIM, 1997].

Quando se discute a relação de parentesco entre as espécies, o conceito mais básico em

termos de evolução é que, para quaisquer duas espécies, é necessário formular-se uma hipótese

de que existiu ao menos um ancestral comum a ambas. Já no caso de três espécies, a hipótese

feita é que há uma ancestral comum a duas delas que não é comum à terceira. Ampliando esse

pensamento de forma a abranger todas as espécies, obtém-se uma espécie ancestral de todas as

outras que sofre divisões subseqüentes até se obter as espécies atuais, o que se costuma chamar

de árvore filogenética.

Um grupo de espécies descende de um ancestral comum, quando compartilha alguma

característica entre si. Tais ancestrais podem ser classificados em recentes ou distantes.

Características herdadas de um ancestral recente aparecem em um número bem mais reduzido

de espécies que as herdadas de ancestrais distantes. Espécies que compartilham um ancestral

recente são bastante similares, possuindo várias características herdadas de um ancestral comum

[AMORIM, 1997].

A homologia é a ferramenta básica que permite a comparação entre pares de espécies

distintas. Características conhecidas como homólogas são aquelas herdadas de uma

característica ancestral comum, podendo ser qualquer uma recebida por herança.

Características herdadas de um ancestral distante são compartilhadas pela maioria ou por

todas as espécies de uma linhagem e são conhecidas como características ancestrais. Tais

características são condições pré-existentes de uma estrutura que foi alterada resultando em

condições novas, que são homólogas e diferentes entre si. Características derivadas são aquelas

que diferem de sua forma ancestral. Tais características são condições mais recentes de uma

estrutura, que surgiram por uma modificação de uma condição anterior.

1 cientistas que estudam a sistemática


Portanto, os sistematas podem inferir o estado de uma característica em algum ancestral e

a partir daí determinar como ela se modificou nos descendentes e assim descobrir como ela

mudou ao longo da evolução [PURVES, 2001]. Porém , existem três processos que tornam os

padrões evolutivos complexos:

i) evolução convergente: em duas espécies diferentes, características ancestrais diferentes

são alteradas, mas resultam em características derivadas com uma semelhança genética;

ii) evolução paralela: em duas espécies diferentes, uma mesma característica ancestral é

alterada de modo idêntico, produzindo nas duas espécies uma característica derivada

semelhante e

iii) reversões evolutivas: em uma determinada espécie, uma característica derivada sofre

uma modificação que gera uma característica derivada semelhante à condição ancestral original

[AMORIM, 1997].

Logo, esses processos podem gerar características superficialmente similares, mas que não

se originam de um ancestral comum, portanto, não são homólogas, tais característica são ditas

homoplásticas.

Para se construir a filogenia de um determinado grupo, é necessário seguir os seguintes

passos:

i) Determinar o grupo focal, grupo de organismos cuja filogenia se quer determinar.

ii) Escolher as características que serão usadas na análise e identificar suas possíveis

formas.

iii) Determinar as características ancestral e derivada, o que geralmente é o passo mais

difícil.

iv) Distinguir entre características homólogas e homoplásticas.

Observando-se a Figura 2, é possível notar que a filogenia não descreve os ancestrais e

nem coloca uma data nas ramificações entre as linhagens. A Figura 2 mostra apenas a ordem

seqüencial das ramificações: as mais antigas estão na esquerda e as mais recentes na direita.


Figura 2 – Uma filogenia provável entre 8 vertebrados [PURVES, 2001]

Para combinar as informações provenientes dessas diferentes características, e reconstruir

as árvores filogenéticas, os sistematas usam vários métodos. O mais usado deles utiliza-se do

princípio da parcimônia, que se baseia na teoria de que a melhor hipótese para explicar um

processo é aquela que requer o menor número de passos, ou seja, a mais simples. Para a análise

filogenética, isso significa minimizar o número de mudanças evolutivas que devem ser

assumidas em relação a todos os caracteres em todos os grupos da árvore.

Já para a reconstrução de filogenias baseadas em dados moleculares, costuma-se usar o

método da máxima verossimilhança. Este método baseia-se na reconstrução filogenética através

da busca por uma árvore que maximize a probabilidade dos dados observados. Os algoritmos

computacionais empregados nesses métodos são desenvolvidos para lidar com o fato de que

mutações que resultam na substituição de nucleotídeos são comuns, mas que suas freqüências

podem ser estimadas independentemente por meio de outras informações genéticas [PURVES,

2001]. Deste modo, o emprego de algoritmos heurísticos pode auxiliar enormemente na busca

pela árvore ideal.


1.2 Representações Básicas

A análise das relações filogenéticas pode ser dividida em duas etapas principais; na

primeira ocorre a construção das listas de caracteres para a análise, ou seja, o estabelecimento

das homologias, sua codificação e ordenação, resultando na matriz de dados; enquanto que, na

segunda etapa, se escolhe a árvore ótima por meio da análise numérica dessa matriz. A

construção da matriz de dados é um passo muito importante na obtenção de filogenias, pois a

qualidade da árvore filogenética final depende diretamente de sua construção.

Existem duas categorias principais nas quais se enquadram as matrizes que servem de

entrada para reconstruções filogenéticas: Matriz de Características e Matriz de Distâncias.

A matriz de características agrupa as características fenéticas de cada espécie, que podem

assumir vários estados discretos ou contínuos. Nesse tipo de matriz as linhas representam as

diferentes espécies e as colunas as características (Figura 3).

Figura 3 – Matriz de Características [SETÚBAL, 1997]

A matriz de distâncias agrupa dados numéricos comparativos entre as espécies, a distância

evolutiva entre as mesmas. Como é formada pela distância entre dois pares de espécies e tal

distância é simétrica, estas matrizes sempre são triangulares (Figura 4).

Figura 4 – Matriz de Distância [SETÚBAL, 1997]


1.2.1 Árvores Aditivas

As matrizes de distância são utilizadas para inferir árvores ultramétricas e árvores aditivas.

O conceito de espaço métrico é importante no processo de construção de árvores

filogenéticas por distâncias, pois ajuda a verificar a qualidade dos dados e melhorar a

confiabilidade da análise filogenética [ARAÚJO, 2003].

Um espaço métrico é um conjunto de objetos O, tal que para todo par (i,j) є O associa-se

um número real não-negativo dij com as seguintes propriedades:

(i) dij > 0 para i ≠ j, (ii) dij = 0 para i = j, (iii) dij = dji para todo i e j,

(iv) dij ≤ dik + dkj para todo i, j e k (desigualdade triangular).

Os objetos da matriz de entrada M devem formar um espaço métrico. Logo, observando-se

a propriedade (iii), pode-se concluir que a matriz será simétrica. A árvore construída com base

em M tem n folhas, pois a matriz é de ordem nxn

O peso do caminho entre quaisquer dois nós i e j, deve ser igual a Mij. Se uma árvore T

puder ser construída a partir da matriz aditiva M, então T será uma árvore aditiva. Uma matriz

aditiva pode ser caracterizada pelo seguinte lema, conhecido por “Condição dos Quatro Pontos”

Lema 1: Uma matriz de estados M é aditiva se, e somente se, dados quaisquer quatro

objetos i, j, k e l de M, vale uma das seguintes propriedades:

(i) dik + djl = dil + djk (ii) dil + dkj = dij + dkl (iii) dik + djl = dij + dkl

A matriz da Figura 5 é um exemplo de matriz aditiva, já que obedece a propriedade de

número (i).

Figura 5 – Exemplo de Matriz Aditiva [ARAÚJO, 2003]

Como a árvore aditiva não possui raiz, não é possível através da mesma predizer a

ancestralidade entre os objetos. Ou seja, não se pode concluir que nó é o ancestral de todos os

nós ou que nó vem antes de outro.


1.2.2 Árvores Ultramétricas

Uma árvore aditiva é considerada uma árvore ultramétrica quando pode ser enraizada de

maneira que a distância de todas as folhas até a raiz seja a mesma; que em termos de biologia

significa que as espécies estudadas evoluem de um ancestral comum na mesma taxa.

Dada uma matriz simétrica M para n objetos, uma árvore ultramétrica para M, segundo

[GUSFIELD, 1997], é uma árvore enraizada, com n folhas, sendo cada folha correspondente a

uma linha da matriz M. Um nó interno da árvore é rotulado com uma entrada da matriz M e tem

pelo menos dois filhos. Os rótulos dos nós internos são estritamente decrescentes ao longo de

qualquer caminho da raiz até uma folha. E para quaisquer duas folhas i e j na árvore, Mij é o

rótulo do ancestral comum mais próximo entre i e j. (vide Figura 6)

Figura 6 – (a) Exemplo de Matriz simétrica M. (b) Árvore ultramétrica para a

matriz M. [ARAÚJO, 2003]

Uma matriz simétrica M de números reais define uma distância ultramétrica se, e somente

se, para quaisquer três índices i, j e k, o máximo entre Mij, Mik e Mjk não é único. Quando M

define uma distância ultramétrica, dizemos que M é uma matriz ultramétrica.

1.3 Utilidade das Árvores Filogenéticas

As árvores filogenéticas contêm informações úteis na investigação científica em uma

grande variedade de questões biológicas, tais como a Biogeografia2, Zoologia e a Botânica, pois

a função da metodologia filogenética na biologia é de ordenar o conhecimento sobre a

diversidade [AMORIM, 1997].

2 ramo da biologia que estuda a distribuição dos táxons nas regiões e os fatores que determinaram essa distribuição.


Porém, técnicas filogenéticas também são usadas pela biologia molecular para

compreender a origem e diferenciação de macromoléculas em grandes grupos. No entanto, nem

sempre há uma compreensão filogenética apropriada dos resultados obtidos com o

seqüenciamento de proteínas e ácidos nucléicos.

Árvores filogenéticas também auxiliam na resolução de problemas práticos, tais como o

controle e combate de parasitas responsáveis por doenças, como vírus, protozoários, fungos e

metazoários. Uma vez que se sabe que determinados parasitas pertencem a um grupo

monofilético3 e certamente possuem características enzimáticas comuns, que podem ser alvo de

uma única ação farmacológica; torna-se mais fácil buscar soluções para caracteres

compartilhados do que para cada uma das manifestações isoladas das espécies. Essas doenças

também poderiam ser mais facilmente controladas se fosse admitido que doenças humanas já

estavam presentes no ancestral comum do homem com seu grupo mais próximo, e feito uma

conexão histórica dos hospedeiros e dos parasitas.

Outra utilidade possível da filogenia seria a ordenação dos caracteres, determinando assim

o nível de surgimento de cada uma das características encontradas na espécie humana, o que é

de grande utilidade, pois, a determinação do nível evolutivo do surgimento de enzimas e

mecanismos de controle encontrados no ser humano permitiria que fossem feitos testes de

reação imunológica ou de toxidade, utilizando outros sistemas biológicos antes de sua aplicação

no homem. Tais testes já são realizados, porém, a ausência de conhecimentos filogenéticos

precisos faz com que muitos desses testes tenham seus resultados analisados de modo deficiente

ou que tenham o poder de previsão extremamente restrito. A informação filogenética também

pode fornecer subsídios importantes para decisões relativas a transplantes de órgãos ou tecidos

de outras espécies [AMORIM, 1997].

3 conjunto de espécies, que inclui um ancestral e todas as suas espécies descendentes


2 ÁRVORES FILOGENÉTICAS E COMPUTAÇÃO

Como já mencionado anteriormente neste trabalho, até a década de 50, os métodos

utilizados na construção de árvores filogenéticas eram em sua essência métodos intuitivos.

Contudo, ao final dessa década e juntamente com o surgimento dos computadores eletrônicos,

foi criada por Peter Sneath e Roberte Sokal a escola fenética, baseada no princípio da taxonomia

numérica.

Com os métodos fenéticos, as matrizes de dados têm tratamento numérico e produzem

diagramas ramificados, nos quais o agrupamento ou segregação de táxons é realizado com base

na média da semelhança total dos caracteres existentes na matriz de dados. O princípio da

taxonomia numérica assegura a obtenção da mesma classificação diversas vezes, desde que

sejam sempre utilizados os mesmos dados, o que garante uma suposta objetividade.

Nesta seção serão abordados alguns algoritmos numéricos que foram propostos com o

passar do tempo, sempre tendo como base a idéia fundamental da escola fenética, a de se formar

grupos por similaridade global.

2.1 Filogenia baseada em distância

A construção de uma árvore filogenética baseada em distância tem como entrada uma

matriz de distância, que são utilizadas para inferir árvores ultramétricas e árvores aditivas. O

Algoritmo Waterman é usado para construir árvores filogenéticas aditivas, enquanto que o

Algoritmo de Farach, Kannan e Warnow é utilizado para construir árvores ultramétricas

[GUSFIELD, 1997]; este estabelece que as distâncias medidas na árvore devem se encontrar em

um intervalo entre uma matriz de limite inferior (Ml) e outra de limite superior (Mh). De modo

que Mijl ≤ dij ≤ Mijh , onde dij é a distância média entre dois objetos i e j na árvore. Tal

propriedade torna o problema mais realista, visto que matrizes ultramétricas são raras.


Figura 7 - Possuem respectivamente exemplos de matrizes de entrada Ml e Mh [ARAÚJO, 2003]

Uma árvore ultramétrica mostra informações importantes, uma vez que podemos

identificar melhor quem é ancestral de quem, qual nó veio antes, em que ponto ocorreu uma

divergência e fez com que um ancestral produzisse duas espécies diferentes.

2.2 Filogenia baseada em características

Um dos aspectos que devem ser levados em consideração quando são utilizadas matrizes

de característica é a existência de problemas como convergência, evolução paralela e reversão

de estados. No entanto é possível se evitar os eventos de convergência e reversão de estados,

fazendo com que o conjunto de todos os nós de uma árvore T que possuam o mesmo estado

para uma determinada característica formem uma subárvore de T. Uma filogenia com esta

propriedade é uma filogenia perfeita.

A filogenia perfeita da matriz da Figura 8 é mostrada na Figura 9. Uma característica

rotulando uma aresta indica que a transição de um estado ‘0’ para ‘1’ ocorre ao longo desta

aresta, tal que a subárvore abaixo da aresta contém todos os objetos que tem o estado ‘1’ para

aquela característica.

Figura 8 – Exemplo de matriz de estados com filogenia perfeita [ARAÚJO, 2003]

Se um conjunto de objetos definidos por uma matriz de estados admite uma filogenia

perfeita, então as características são compatíveis.


Figura 9 – Filogenia correspondente à matriz da Figura 8 [ARAÚJO, 2003]

Um algoritmo proposto por Gusfield para resolver de maneira polinomial o problema da

filogenia perfeita possui duas fases: na primeira, verifica se a matriz de entrada M admite uma

filogenia perfeita. Caso positivo, então a segunda fase consiste na construção de uma possível

filogenia.

Segundo [GUSFIELD, 1997], a filogenia perfeita para uma matriz M é representada por

uma árvore T com raiz. Onde toda característica em M corresponde a uma aresta em T, e a

mesma representa uma transição do estado ‘0’ para o ‘1’ para aquela característica. Além disso,

a raiz sempre tem estado ‘0’ para todas as características. Portanto, ao se percorrer o caminho

que ligando a folha do objeto i à raiz, as arestas ao longo do caminho correspondem às

características para as quais o objeto i tem estado ‘1’.

Lema 2: Uma matriz binária M admite uma filogenia perfeita se, e somente se, para cada

par de características i e j, ou os conjuntos 1i4 e 1j5 são disjuntos, ou um deles contém o outro.

4 O conjunto de características de um objeto cujo valor é 1. 5 O conjunto de objetos que têm o valor 1 para uma determinada característica.


Figura 10 – Segundo o Lema 2, a matriz não admite filogenia perfeita, pois as

colunas c1 e c5 não satisfazem suas condições, já que, 1c1 ∩ 1c5 ≠ Ø e 1c1 não está contido em 1c5 nem vice-versa, portanto tais características são ditas não

compatíveis [SETÚBAL, 1997].

O algoritmo utilizado para verificar se uma matriz admite ou não filogenia perfeita é

composto de três fases, onde cada um delas tem um tempo de execução de O(nm):

A ordenação utilizando o algoritmo radix sort, que pode ser encontrado em [CORMEN,

2002].

O cálculo da matriz auxiliar Lnxm.

A verificação de cada coluna, em busca de diferentes de zero e entre si.

Utilizando o radix sort, para ordenar as colunas da matriz da Figura 8, obtém-se a matriz

da Figura 11(a). Com base nessa matriz e seguindo as instruções do procedimento descrito no

Quadro 1, é possível obter a matriz da Figura 11(b). Analisando-se cada uma das colunas da

mesma, conforme o mencionado no algoritmo do Quadro 1, conclui-se que a matriz da Figura 8

admite filogenia perfeita, pois nenhuma das colunas da matriz da Figura 11(b) possui elementos

não nulos diferentes entre si.

(a) (b)

Figura 11 – (a) Matriz de estado da Figura 10 com ordenação de colunas. (b) Matriz auxiliar L, calculada para verificar se a matriz de estados da Figura 10 é

aditiva [ARAÚJO, 2003]


Quadro 1 – Algoritmo que decide quando uma matriz binária admite ou não filogenia perfeita [SETÚBAL, 1997]

Entradas: Matriz binária M,

Saída: TRUE se M admite uma filogenia perfeita

FALSE caso contrário

Início //assuma que todas as colunas são distintas Ordene as colunas em ordem decrescente com base na quantidade de 1’s de cada uma, usando o radix-sort

//Inicialize a matriz auxiliar L Para cada Lij faça

Lij := 0 FimPara

//calculando Lij Para i de 1 a n faça

K := -1 Para j de 1 a m faça

Se Mij = 1 então Lij := k //k é a coluna mais à direita da esquerda de j //onde Mik = 1. Se tal coluna não existe, k =-1 k := j FimSe

FimPara FimPara

//checando as colunas de L Para cada coluna j de L faça Se Lij ≠ Llj para qualquer i, l e Lij ≠ 0 e Llj ≠ 0 então Retorne FALSE FimSe FimPara

Retorne TRUE

Fim

Uma vez constatado que a matriz admite filogenia perfeita, começa-se a construção da

árvore com um único nó: a raiz e para cada objeto na matriz, procuram-se as características para

as quais seu estado é ‘1’. Se ainda não existir uma aresta rotulada com tal característica, um


novo nó é criado e ligado ao nó corrente por uma aresta rotulada com essa característica. O

novo nó torna-se o nó corrente. Se já existe uma aresta rotulada com essa característica, o nó

corrente é considerado o ponto final da aresta e a análise continua a partir da próxima

característica. O algoritmo gasta O(nm), pois cada objeto de M é verificado exatamente uma vez

e o processo tem um tempo constante de O(m) por elemento.

A árvore da Figura 9 pode ser construída por meio do algoritmo do Quadro 2 e com base

na matriz da Figura 8.

Quadro 2 – Algoritmo que constrói uma filogenia perfeita a partir de uma matriz binária [SETÚBAL, 1997]

.Entradas: Matriz binária M com colunas ordenadas decrescentemente pelo número de 1’s.

Saída: Filogenia perfeita para M

Início Cria Raiz

Para cada objeto i faça noCorrente := raiz Para j de 1 a m faça Se Mij = 1 então Se já existe uma aresta(noCorrente, u) então noCorrente := u senão Cria nó u Cria aresta(noCorrente, u) rotulada de j noCorrente := u FimSe FimSe FimPara

Coloque i no noCorrente FimPara

Para cada nó u exceto a raiz faça Crie uma quantidade de folhas ligadas a u igual à quantidade de objetos em u

FimPara Fim

Como as matrizes nem sempre admitem uma filogenia perfeita, serão apresentadas a

seguir abordagens para reconstrução de filogenias que não são perfeitas. Tais filogenias

obedecem a um critério de otimização, onde as árvores construídas devem minimizar uma

função objetivo.

De acordo com [SETÚBAL, 1997], existem duas abordagens, a do critério da parcimônia

e a do critério da compatibilidade. O critério da parcimônia admite eventos de convergência e

reversão, mas tenta minimizar suas ocorrências, enquanto que o critério da compatibilidade


tenta-se evitar tais eventos, excluindo as características que os causam, tenta-se encontrar o

número máximo de características que admitam uma filogenia perfeita, excluindo o menor

número de características possíveis. Ambos são problemas de otimização, o que os torna mais

difíceis que o problema da filogenia perfeita, que era um simples problema de decisão.

A parcimônia de uma Árvore Filogenética se refere ao número total de transições

ocorridas nas arestas da árvore. Uma árvore é dita ser parcimoniosa se sua parcimônia é a

máxima possível, o que significa que não é possível construir uma árvore com uma quantidade

menor de transições. Pois tem como fundamento o conceito de que a natureza é econômica, ou

seja, durante o processo de evolução, o número de modificações é mínimo. O problema de

encontrar uma filogenia baseada em características pode ser dividido em dois subproblemas:

Problema da parcimônia pequeno que consiste em como avaliar quão boa é a árvore obtida;

Problema da parcimônia grande que se preocupa em como procurar uma árvore no

conjunto de todas as árvores possíveis de maneira eficiente.

2.2.1 Problema da parcimônia pequeno

O problema da parcimônia pequeno consiste em: dada a topologia da árvore, encontrar

uma atribuição de estados aos nós internos que minimize o número de transições, determinando

o custo da filogenia. De acordo com [SWOFIORD, 1990], o algoritmo para determinar o custo

de uma árvore com raiz sobre o critério de parcimônia de Wagner pode ser visto na Figura 15.

A Figura 12 apresenta um exemplo da execução para o método de Wagner. A partir da

árvore sem raiz da Figura 12(a), calcula-se através de algoritmo do Quatro 3 que o custo da

árvore é 5.

Figura 12 - Exemplo de execução para método de Wagner [ARAÚJO, 2003].


2.2.2 Problema da parcimônia grande

Resolvido o problema de como determinar o custo de uma árvore, resta então encontrar a

melhor árvore que explique os dados. É justamente isso que o problema da parcimônia grande

faz, procura a melhor árvore no espaço de todas as árvores possíveis. O problema tem como

entrada uma matriz de estados e o objetivo do mesmo é encontrar uma árvore de parcimônia

com o menor custo.

Quadro 3 – Algoritmo do critério da parcimônia de Wagner [ARAÚJO, 2001] Entradas: Matriz M de características de estados binário ou múltiplo.

Saída: Custo de um árvore como raiz

Início CustoArvore := 0

Para cada nó folha i faça i := Si

// Si é o conjunto dos estados da característica atribuída à espécie em M FimPara

Enquanto k for diferente do descendente imediato da raiz faça

Para cada k que Sk ainda não tenha sido definido faça

Se Si ∩ Sj ≠ Ø então Sk := Si ∩ Sj

// Si ∩ Sj equivale ao intervalo fechado [ak ; bk] Senão Sk recebe o menor intervalo fechado [ak ; bk] //contendo um elemento de cada um dos conjuntos Si e Sj CustoArvore := CustoArvore + (bk - ak) FimSe

FimPara

FimEnquanto

// seja xr o estado atribuído à raiz Se xr ⊄ Sk então

Se xr < ak então CustoArvore := CustoArvore + (ak - xr) // ak – xr é a distância de xr a SK FimSe

Se xr > bk então CustoArvore := CustoArvore + (xr - ak) // xr – ak é a distância de xr a SK FimSe FimSe

Retorna CustoArvore

Fim


O problema da parcimônia grande é NP-difícil, pois considerando-se uma árvore com duas

folhas, há somente uma topologia para esta árvore. Para produzir uma árvore com 3 folhas,

existem três possibilidades de ramificações para que se possa adicionar uma nova folha. Desta

forma, pode-se mostrar que há 1 * 3 * 5 * ... * (2n - 3) = ∏=

−n

k

k2

)32( árvores com espécies nas

folhas e nós internos não rotulados e este número cresce exponencialmente com o número de

folhas n.

Uma alternativa é utilizar Branch & Bound [CORMEN, 2002], pois no pior caso, esse

algoritmo tem a mesma complexidade de uma enumeração. No caso da construção de árvores

parcimoniosas, entretanto, verifica-se na prática que a aplicação da técnica reduz o tempo de

busca da solução ótima. Mais informações podem ser obtidas em [SHAMIR, 2001].

2.3 Aplicativos para a construção de filogenias

O PHYLIP (the PHYLogeny Inference Package) é um pacote de análise filogenética

criado por Joseph Felsenstein na Universidade de Washington. Esse pacote pode resolver a

maioria das análises filogenéticas existentes na literatura atual. O pacote inclui métodos como o

da parcimônia, o da matriz de distância e o likelihood. E pode trabalhar com os seguintes tipos

de entrada de dados: seqüências moleculares, freqüência de gene, matriz de distância e

características discretas.

O PHYLIP está disponível gratuitamente na internet e foi escrito para funcionar na maior

diversidade de sistemas computacionais possível. O código fonte encontar-se em C e os

executáveis são distribuídos já compilados e rodam no Windows (95/98/NT/2000/me/xp),

MacOS 8 e 9, MacOS X, e Linux. O pacote é acompanhado de uma documentação principal que

dá uma introdução ao mesmo, além de uma documentação para cada grupo de programa e uma

específica para cada um dos 35 programas que o compõe.

Os dados de entrada são lidos a partir de um arquivo-texto. A maioria dos programas

procura pelos dados de entrada em um arquivo chamado “infile”. A primeira linha desse arquivo

contém a quantidade de espécies e características. Cada característica pode assumir além dos


estados ‘0’ e ‘1’, os estado ‘?’, que representa um estado desconhecido e P ou B, que tem o

mesmo significado, indicam que ambos os estados 0 e 1 são estados de polimorfismo.

A saída é escrita em arquivos especiais denominados “outfile” e “outtree”. As árvores

escritas no outtree estão no formato Newick, um padrão informal que foi estabelecido em 1986

pelos autores dos principais pacotes de filogenia.

Conclusão

Existem muitos outros algoritmos para construção de filogenias, na literatura, além dos

que foram aqui relatados. Além de tudo o que já se foi realizado pela ciência da computação

para ajudar a biologia, ainda pode-se fazer muito mais, com a implementação de novas

heurísticas cujas soluções se aproximem cada vez mais da solução ótima. Porém, com este

trabalho procurou-se apenas esclarecer ao leitor o que são árvores filogenéticas, como elas são

construídas e qual a importância da computação durante essa construção.

Algorithmic Techniques for Construction of Phylogenetic Trees

Abstract:

The construction of phylogenetic trees helps Biology to explain the possible relationship among recent species and find out their evolutionnary history. Known simply as phylogeny, those trees have leaves that represent the species and nodes which represent their ancestors. Using DNA sequences, supplying by the modern science, it´s possible to infer phylogenies using data such as: distance and character. Distance estimates the evolutionary distance between the species, mean while character is related to existence or not of certain genes in some genomes. The aim of this paper is to present some Algorithmic Techniques

for the phylogeny problem, with approach of the Theory of the Computation, that make possible to get its solution in skillful time, considering that the process of searching of the best solution is NP-complete [Boadlaender, 1992]

Keywords: Computational Biology, Phylogeny, Evolution.


Referências

AMORIM, Dalton S. Elementos básicos da sistemática filogenética. 2. ed, Ribeirão Preto. Holos, 1997.

ARAÚJO, Graziela S. Filogenia e Proteomas. Mato Grosso do Sul , 2003. 84 p. Dissertação (Mestrado em Ciência da Computação) – Departamento de Computação e Estatística, Universidade Federal do Mato Grosso do Sul.

BOADLAENDER, H.; FELLOWS, M.; WARNOW, T. Two Strikes against perfect phylogeny, in Proceedings of the 19th Colloquium on Automata, Languages and Porgramming, NY: Springer-Verlag, 1992.

CORMEN, T. et al., Algoritmos: Teoria e Prática, São Paulo: McGraw-Hill, 2002.

FARACH, M.; KANNAN, S.; WARNOW, T., A robust model for finding optimal evolutionary trees. [SL] Algorithmica 13 (155-179), 1995.

GUSFIELD, D., Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology. [SL] Cambridge University Press, 1997.

PROSDOCIMI, Francisco et al. Bioinformática: manual do usuário. Biotecnologia Ciência & Desenvolvimento, n° 29, jan. 2003

PURVES, et al. Vida: A ciência da Biologia. 6. ed, Porto Alegre: Artmed Editora, 2001.

MEIDANIS, J.; SETÚBAL, J. C. Introduction to computational molecular biology. [SL] Brooks/Cole Publishing Co., 1997.

SHAMIR, R. Algorithms for molecular biology. Lecture Note, 2001.

SWOFIORD, D.L.; OLSEN, G.L. Phylogeny reconstruction molecular systematics . Massachusetts. Sunderland, 1990.

Lia Cysne Pinteiro

Graduada em Ciência da Computação, Universidade Estadual do Ceará, 2005. e-mail: [email protected]


Gerardo Valdisio Rodrigues Viana

Doutorando em Ciência da Computação - UFC/2005- Mestre em Ciência da Computação - UFC/1995-1996 Professor Adjunto - UFC/UECE/FLF Áreas de interesse: Otimização Combinatória, Algoritmos, Metaheurísticas e Bioinformática. e-mail: [email protected] [email protected]

Fernando Antônio de Carvalho Gomes

Pós-Doutorado - University of Ottawa, U.O., Canadá., 2000-2001. Doutor em Ciência da Computação - Universite de Montpellier II (Scien. et Tech Du Languedoc), U.M. II, França, 1989-1992 Mestre em Ciência da Computação - Universidade Federal da Paraíba, UFPB, Brasil, 1987-1989; Professor Adjunto da Universidade Federal do Ceará, 1996- Áreas de interesse: Otimização Combinatória, Algoritmos, Metaheurísticas, Bioinformática, Data Mining. e-mail: [email protected] [email protected] Marina Gomes Viana

Graduada em Ciências Biológicas, Universidade Federal do Ceará, 2001-2005 [email protected]

Documents

Técnicas Algorítmicas para Construção de Árvores Filogenéticasyw/capes/capes-cofecub-2009/projeto-karla... · Rev. Cient. Fac. Lourenço. Filho - v.4, n.1, 2005 83 molecular