Árvores Filogenéticas
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
setembro/2002
chimpanzee
2
O que são Árvores Filogenéticas ?
Veja alguns exemplos aqui:
http://aleph0.clarku.edu/~djoyce/java/Phyltree/page2.html
setembro/2002
3
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
4
Algumas considerações
Vamos considerar aqui o caso mais simples, sem:
• Convergências ou evoluções paralelas
• Reversão
setembro/2002
5
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
6
Character State Matrix
setembro/2002
c1
c2
c3
c4
c5
A
1
1
0
0
0
B
0
0
1
0
1
C
1
1
0
0
1
D
0
1
1
1
0
E
1
1
0
0
1
7
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
8
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
9
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
10
Algoritmo para constatar a compatibilidade
c1
c2
c3
c4
A
1
1
0
0
0
-1
1
0
0
0
B
0
0
1
0
1
0
0
-1
0
3
C
1
1
0
0
1
-1
1
0
0
2
D
0
1
1
1
0
0
-1
1
2
0
E
1
1
0
0
1
-1
1
0
0
2
setembro/2002
c5
L
D tem características 2, 3 e 4 ,
enquanto B tem características 3 e 5.
Resultado = False
11
Algoritmo para constatar a compatibilidade
L
c1 c2
c3
c4
c5
c6
A
0
0
0
1
1
0
0
0
0
-1
4
0
B
1
1
0
0
0
0
-1
1
0
0
0
0
C
0
0
0
1
1
1
0
0
0
-1
4
5
D
1
0
1
0
0
0
-1
0
1
0
0
0
E
0
0
0
1
0
0
0
0
0
-1
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
12
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
Lij <- 0
// Inicializa a matriz auxiliar L
for i <- 1 to n do
k <- -1
for j <- 1 to m do
if Mij = 1 then
// Computa L
Lij <- k
k <- j
// k é a coluna mais próxima à esquerda de j tal que Mik = 1.
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 FALSE
return TRUE
setembro/2002
13
Construção da árvore filogenética
C1 C2 C3 C4 C5 C6
A
B
C
D
E
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0
0
0
0
1
0
0
root
c4
c5
c1
c2
c3
c6
E
A
setembro/2002
C
D
B
14
Algoritmo para construir a árvore
Entrada: Matriz M binária de estados das características.
Saída: A árvore filogenética.
Create root
for 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
15
Construtores de Árvores
Applet para filogenia perfeita:
http://linneus20.ethz.ch:8080/5_5_2.html#SECTION00652110000000000000
Index para várias formas de filogenia
http://www.rna.icmb.utexas.edu/linxs/1/phylogeny.html
setembro/2002
16