Árvores Filogenéticas

setembro/2002 2

O que são Árvores Filogenéticas ?

As árvores filogenéticas tentam fazer uma representação da evolução das espécies.

siamang gibbon orangutan gorilla

human chimpanzee

setembro/2002 3

O que são Árvores Filogenéticas ?

Veja alguns exemplos aqui: http://aleph0.clarku.edu/~djoyce/java/Phyltree/page2.html

setembro/2002 4

Problemas com as Árvores Filogenéticas

Não temos muitas informações sobre os ancestrais mais distantes das espécies atuais.

Geralmente a reconstrução de árvores filogenéticas é baseada em pesquisas já realizadas e em comparações entre as atuais espécies.

setembro/2002 5

Algumas considerações

Vamos considerar aqui o caso mais simples, sem:

• Convergências ou evoluções paralelas• Reversão

setembro/2002 6

O Tipo de entrada mais simples Matriz dos estados das características

( Character State Matrix )

Linhas: (A, B, C, D, E) = Objetos

Colunas: (c1, c2, c3, c4, c5) = Características

Os objetos são as folhas da árvore e as características representam as arestas que ligam os ancestrais aos descendentes (que adquiriram uma nova característica).

setembro/2002 7

Character State Matrix

ABCDE

c1 c2 c3 c4 c51

1

1

1

111

1

1 1

11

1

0

0

00

0

0

0 0

0

00

0

setembro/2002 8

O problema da filogenia perfeita em árvore

Instância: Um conjunto O de objetos e um conjunto C com m características,

cada um tendo no máximo r estados.

Pergunta: Para cada estado s (0 ou 1) de cada caracter c , o conjunto de todos os nós para os quais o estado é s com relação a c devem formar uma sub-árvore.

Applet para filogenia perfeita:http://linneus20.ethz.ch

:8080/5_5_2.html#SECTION00652110000000000000

setembro/2002 9

Algoritmo dividido em duas partes

1) Descobrimos se há compatibilidade entre as características.

2) Caso seja compatível, construiremos a árvore filogenética.

setembro/2002 10

Algoritmo para Compatibilidade

1) Para cada organismo, identificamos quais

as características que ele tem (ordem é relevante) - Matriz L.

2) Para cada característica, verificamos se algum par de organismos não é

compatível.

setembro/2002 11

Algoritmo para constatar a compatibilidade

ABCDE

c1 c2 c3 c4 c51

1

1

1

111

1

1 1

11

1

0

0

00

0

0

0 0

0

00

0

-1

-1

-1

1

1-11

-1

1 2

32

2

0

0

00

0

0

0 0

0

00

0

L

D tem características 2, 3 e 4 , enquanto B tem características 3 e 5. Resultado = False

setembro/2002 12

Algoritmo para constatar a compatibilidade

c1 c2 c3 c4 c50

0

0

0

000

0

1 0

01

0

1

1

10

0

0

1 1

0

01

1

L

ABCDE

c6

01

0

0

0

0

0

0

0

000

0

1 0

04

0

-1

-1

10

0

0

-1 4

0

0-1

-1

05

0

0

0

Em cada coluna da matriz L, se há mais de um valor diferente de 0, eles são iguais. Resultado = True

setembro/2002 13

Algoritmo para constatar a compatibilidade

Entrada: Matriz M de estados das características.Saída: TRUE se admite uma filogenia perfeita e FALSE caso contrário.

for each Lij do // Inicializa a matriz auxiliar L

Lij <- 0

for i <- 1 to n do // Computa L k <- -1 for j <- 1 to m do

if Mij = 1 then

Lij <- k // k é a coluna mais próxima à esquerda de j tal que Mik = 1. k <- j

for each column j of L do //Checa as colunas de L if Lij Llj for some i, l and both Lij and Llj are nonzero then return FALSEreturn TRUE

setembro/2002 14

Construção da árvore filogenética

01010

0

0

000

0

0

0

0

0

0

0

0

0

0

00

1

11

1

1

1

1

1

root

c4

c5

A

c1

c2

B

C

c6

c3

DE

C1 C2 C3 C4 C5 C6A

BCDE

setembro/2002 15

Algoritmo para construir a árvoreEntrada: Matriz M binária de estados das características.Saída: A árvore filogenética.

Create rootfor each object i do curNode <- root

for j <- 1 to m do if Mij = 1 then if there already exists edge (curNode, u) labeled j then curNode <– u else Create node u Create edged (curNode, u) labeled j curNode <- u Place i in curNode

for each node u except root do Create as many leaaves linked to u as there are objects in u

setembro/2002 16

Construtores de Árvores

Applet para filogenia perfeita:http://linneus20.ethz.ch

:8080/5_5_2.html#SECTION00652110000000000000

Index para várias formas de filogeniahttp://www.rna.icmb.utexas.edu/linxs/1/phylogeny.html