Artur Lira
– [email protected]
Thiago Rocha
– [email protected]


Contexto
Reconstrução Filogenética
 Por DNA
 Por ordem dos genes.






Maximum Parsimony
Breakpoint Analysis
GRAPPA
Impactos Na Biologia Computacional
Conclusão
Referências

Filogenia
 hipóteses de relações evolutivas(relações filogenéticas) entre
diferentes espécies.
 Representação em árvore
Orangotango
Gorila
Chimpanzé
Humano

Reconstrução Filogenética
 Processo de inferir as relações evolutivas de um
determinado conjunto de espécies a partir de
conhecimentos em genética.
▪ Seqüenciamento de DNA
▪ Ordem dos genes (Whole Genome Based Phylogeny
Reconstruction)


Cada espécie é representada por sua
seqüência genética
Assume-se que cada caractere tem o
potencial de evoluir
 Substituições A <-> T <-> G <-> C
AAGACTT
AAGGCCT
AGGGCAT
AGGGCAT
-2 106 anos
TGGACTT
TAGCCCT
TAGCCCA
-3 106 anos
TAGACTT
AGCACTT
AGCACAA
AGCGCTT
-1 106 anos
Atualmente

Nós da árvore são permutações dos genes da
espécie
1 –5 3 4 -2 -6
ou
6 2 -4 –3 5 –1
A
A
C
D
X
B
E
Y
E
Z
C
F
B
D
W
F
1
2
3
4
5
6
7
8
9
10
3 –8 –7 –6 –5 -4
9
10
8
10
• Inversão
1
2
• Transposição
1
2
3
9
4
5
6
7
• Transposição Invertida
1
2
3
9 -8 –7 –6 –5 –4
10

Raras mudanças genômicas
 Baixa freqüência de eventos evolutivos se
comparado com substituições nas seqüências de
DNA.
▪ Evoluções muito profundas podem ser inferidas com
maior fidelidade

Problemas NP-Hard
 N° de árvores possíveis é gigantesco
▪ (2x-5)!! = 3 * 5 * 7 * ... * (2x-5), onde x = n° de espécies
 Anos para se resolver maioria dos conjuntos de espécies
estudados.
 Resultado não necessariamente é um ótimo global.
Ótimo local
Score
Ótimo global
Árvores Filogenéticas

Busca minimizar (a partir de um critério) o
número de pontos de mutação necessário para
explicar as relações evolutivas entre as espécies.

Definição: Dado um conjunto S de strings de
mesmo comprimento e alfabeto, encontre uma
árvore T como folhas sendo elementos de S e
todos os nós internos strings de mesmo
comprimento e alfabeto de S, de forma que tal
árvore minimize o somatório dos comprimentos
das arestas.
ACT
GTA
ACA
ACT
GTT
ACA
GTT
GTA
ACA
GTA
ACT
GTT
ACT
GTT
2 GTT GTA
1
2
GTA
ACA
ACA
GTT
ACT
ACA ACT
1
3
3
MP score = 7
MP score = 5
ACA
ACT
GTA
ACA GTA
2
1
1
MP score = 4
Melhor Opção
GTT
GTA
A
2
X
3
B
C
2
E
Y
5
Z
2
J
6
2
2
C
3
D
MP score = 27
2
2
W
B
E
K
3
L
2
2
2
F
2
D
MP score = 19
E
2
P
2
B
A
2
F
2
A
Q
1
R
2
2
1
2
2
D
MP score = 16
Melhor Opção
S
B
2
M
F

Breakpoint:
 Dois genomas G e G’ com o mesmo conjunto de
genes
 Existe um breakpoint em (gi , gj) de G se e
somente se:
▪ (gi , gj) e (-gj , -gi) não aparecem em G’

Breakpoint Distance (BD)
 Número de breakpoints entre dois genomas

Mediana de 3 genomas
 O genoma que minimiza o BD entre 3 genomas

A partir de 3 permutações com sinal A, B e C,
encontre uma quarta permutação D que:
 Minimize a soma das distâncias d(A;D) + d(B;D) +
d(C;D)

NP hard
A
D
C
B


Implementação desenvolvida em 1997 por
Sankoff e Blanchette
Lida com dados simples e específicos
 Organismos com apenas um cromossomo ou
organelas com um único cromossomo.
 Cada cromossomo representado por uma ordem
orientada de genes

Enumera todas as (2n-5)!! árvores de n nós.

Utiliza redução de MPB para TSP (Travelling
Salesman Problem)
 Representação de cada gene por um par de
cidades conectadas por uma aresta.
Complexidade computacional é exponencial
para qualquer número de genomas.
• Estima-se 200 anos para amostra de 13
genomas com 105 genes cada num único
processador.

Para cada árvore T do conjunto de árvores
Inicialmente defina um nó para cada permutação
Repita
Para cada nó interno v com vizinhos A,B,C
Resolva a MPB A B, C que gera D
Se colocar D em v melhora o score da árvore T, altere a
árvore e marque v como visitado.
enquanto existir um nó interno de T não visitado

Genome Rearrangement Analysis under
Parsimony and other Phylogenetic Algorithms
 Bernard M.E. Moret, David A. Bader, Tandy Warnow
▪ University of New Mexico
 http://www.cs.unm.edu/~moret/GRAPPA/

Segue a idéia de BPAnalysis, mas com
otimizações:
 Re-Engenharia
 Paralelismo
 Heurísticas semelhantes ao hill-climbing e Maximum
Parsimony que busquem solucionar problemas NPHard de forma otimizada


Identificação de gargalos na implementação
Exemplos:
a. loop unrolling, reduzindo o tempo de execução
em um fator maior que 6.
b. Reuso de Memória alocada.
c. Métodos mais eficientes para cálculo de
distâncias entre genomas em tempo polinomial.


Eficiente geração paralela das árvores de BPAnalysis
Cada processador manipula uma fração das árvores.




Divide-To-Conquer
Possibilidade de “pausar” o processamento.
Aumento de desempenho na ordem de 1 milhão.
Cache Sensitivo
a. BPAnalysis: 60MB
b. GRAPPA: 1.8MB

Princípio de Localidade
a. BPAnalysis: pobre localidade região de alta localidade em 12MB
b. GRAPPA : boa localidade, região de alta localidade em 600KB


Teste com plantas aquáticas da família Campanulaceae
13 genomas, 105 genes cada
1997: BPAnalysis : 200 anos em um único processador (est.)
2000: GRAPPA v1.1 usando o “512-processor Los Lobos
Supercluster machine”: 2 minutos. Melhoria em fator de
200.000 por processador.
2003: GRAPPA v2: 2 minutos em um único processador. Melhoria
num fator de 1 bilhão.

Implementação mais eficiente que
BPAnalysis
 Redução do tempo de análise em média de 2 anos
para um dia.
 Redução de custos na pesquisa e
desenvolvimento de drogas.


Reconstrução Filogenética abre um novo e
complexo campo de pesquisa na biologia
computacional
Problemas complexos que demandam
algoritmos de alta performance e grande
escala para serem solucionados.

SETUBAL, J. C.; MEIDANIS, J. C. Introduction to Computational
molecular biology. 1° ed. Thomson. 1997.

GRAPPA. Disponível em: http://www.cs.unm.edu/~moret/GRAPPA/

A High-Performance Computational Tool For Phylogeny
Reconstruction From Gene-Order Data. Disponível em:
http://www.cs.unm.edu/~moret/botsoc.pdf. Último acesso: 9 Jan 2008

MORET, B. M. E. ; WYMAN, S. ; BADER, A. B. ; WARNOW, T.; YAN, M.
Phylogenies from Gene Order Data: A Detailed Study of Breakpoint
Analysis (2001). Disponível em: http://citeseer.ist.psu.edu/466513.html .
Último acesso: 9 Jan 2008
Artur Lira
– [email protected]
Thiago Rocha
– [email protected]