Análise filogenética #2

Prévia do material em texto

Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 1
Árvores Filogenéticas
1 Introdução
• todos os fundamentos da biologia moderna estão associados à teoria da evolução
de Darwin.
• de aspectos de anatomia, passando por comportamento e chegando à genética,
toda a metodologia de análise requer uma apreciação das mudanças nos
organismos com o tempo.
• é impossível analisar as relações entre seqüências de genes sem considerar, direta
ou indiretamente, o modo como estas seqüências sofreram modificações ao longo
do tempo.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 2
2 Taxonomia
• a disponibilidade de seqüências de atributos, que descrevem parte das (não
confunda com todas as!) características de organismos, nos remetem às seguintes
questões:
� os atributos correspondentes estão devidamente alinhados (sequence
alignment)?
� uma vez alinhadas, como estas seqüências estão relacionadas?
� e de um modo geral, uma vez alinhadas, como os organismos dos quais estas
seqüências foram obtidas estão relacionados?
• o estudo dos relacionamentos entre grupos de organismos é chamada taxonomia
(ou taxinomia), a qual representa um dos ramos mais antigos da biologia clássica.
• em outras palavras, a taxonomia envolve a classificação de objetos em grupos, é
uma atividade que sempre foi exercida pelos homens de todos os tempos e foi
estabelecida como um ramo científico por Carolus Linnaeus (1707-1778).
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 3
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 4
• a filogenia ou história evolutiva das espécies está fundamentada em um conceito
da teoria da evolução que afirma que grupos com organismos que apresentam
atributos similares descendem de um ancestral comum.
• a sistemática filogenética é, portanto, um método de classificação taxonômica
baseado na história evolutiva, tendo sido desenvolvida em 1950 por um
entomologista alemão chamado Willi Hennig.
• as relações evolutivas são representadas na forma de árvores filogenéticas, que
descrevem os relacionamentos entre as seqüências.
2.1 Metodologias para reconstrução de árvores filogenéticas
• há duas metodologias distintas para se obter uma árvore filogenética:
� métodos fenéticos ou não-baseados em modelo evolutivo: são aqueles que
consideram o estado corrente das seqüências de atributos, não importando a
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 5
história evolutiva, ou seja, a dinâmica dos passos intermediários. A árvore que
melhor explica os relacionamentos entre as seqüências de atributos é
denominada fenograma.
� métodos cladísticos ou baseados em modelo evolutivo: são aqueles que
consideram as possibilidades de resultado de um processo evolutivo,
importando a dinâmica dos passos intermediários, e adotam a árvore que melhor
explica os relacionamentos entre as seqüências de atributos resultantes, sempre
com base em uma hipótese evolutiva. Esta hipótese evolutiva pode estar
baseada em algum modelo evolutivo ou em algum critério de otimalidade. A
árvore que melhor explica os relacionamentos entre as seqüências de atributos é
denominada cladograma. Na árvore adotada, o comprimento dos ramos pode ser
informativo (quando a hipótese está baseada em um modelo evolutivo),
resultando em um filograma.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 6
procarioto 1
procarioto 2
procarioto 3
eucarioto 1
eucarioto 2
eucarioto 3
CLADOGRAMA
procarioto 1
procarioto 2
procarioto 3
eucarioto 2
eucarioto 3
eucarioto 1
FILOGRAMA
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 7
• algoritmos computacionais baseados na metodologia fenética empregam cálculo
de distância para reconstruir as árvores a partir de uma seqüência de atributos.
São, portanto, enormementente influenciados pelo papel de cada atributo da
seqüência.
• adotar o mesmo papel para cada atributo é um procedimento altamente
questionável, mas muito utilizado. Ele se justifica na ausência de informação para
se tomar outras atitudes.
• os algoritmos baseados na metodologia fenética conduzem a técnicas computacio-
nais extremamente eficientes e com propriedades estatísticas desejáveis.
• a metodologia fenética supera a metodologia cladística quando os atributos
presentes das seqüências são extremamente objetivos.
• no entanto, na presença de atributos menos objetivos, como aqueles que envolvem
aspectos de morfologia, e na existência de múltiplos objetivos a serem satisfeitos,
a metodologia cladística é seguramente superior.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 8
• a que corresponde cada atributo da seqüência?
� tamanho e forma de estruturas visíveis;
� presença ou ausência de alguns fatores;
� tipos de comportamento frente a diversas situações;
� seqüências de DNA;
� dados de expressão gênica;
� alguma combinação dos atributos acima;
� etc.
• estes atributos podem, portanto, assumir valores discretos ou contínuos, havendo
medidas de similaridade específicas para cada caso.
• por exemplo, em uma seqüência de DNA, existem 4 valores possíveis para cada
atributo, cada um correspondendo a um nucleotídeo.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 9
2.2 DNA como unidade básica da taxonomia
• vantagens associadas ao uso de DNA como unidade taxonômica:
� o estado de cada atributo pode ser definido de forma não-ambígua;
� um número elevado de atributos pode ser obtido;
� é possível caracterizar a divergência entre seqüências não apenas em termos
de distância, mas também levando-se em conta a natureza da divergência:
substituição de nucleotídeos, inserções/deleções ou rearranjo de genoma.
• desvantagens associadas ao uso de DNA como unidade taxonômica:
� necessidade de aplicação de técnicas de alinhamento de seqüências;
� dificuldade de atribuir funcionalidade (grau de importância) a cada atributo.
A aat tcg ctt cta gga atc tgc cta atc ctg
B ... ..a ..g ..c .t. ... ... t.. ... ..a
C ... ..a ..c ..c ... ..t ... ... ... t.a
D ... ..a ..a ..g ..g ..t ... t.t ..t t..
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 10
• supondo a capacidade de atribuir funcionalidade às seqüências, por exemplo,
delimitando genes, há um entendimento intuitivo de que organismos
evolutivamente mais próximos devem apresentar seqüências mais similares,
enquanto que indivíduos evolutivamente mais distantes devem apresentar
seqüências mais dissimilares.
• dado um conjunto de seqüências de bases, ou melhor ainda, um conjunto de
seqüências de genes, é possível reconstruir um relacionamento evolutivo entre
estas seqüências, ou genes.
• é possível estender esta hipótese aos organismos de onde os atributos foram
extraídos?
• nem sempre, pois os genes não necessariamente tiveram a mesma história
evolutiva que aquela apresentada pela espécie em que ele está contido.
• a probabilidade de se estimar uma topologia equivocada para a árvore é
diretamente proporcional à correlação entre as seqüências de atributos.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 11
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 12
2.3 A validade científica e a correção de uma árvore
• a aplicação de pacotes de software distintos a um conjunto de seqüência de
atributos é muito provável que produza respostas distintas.
• alterações mínimas nos dados podem também conduzir a mudanças significativas
nos resultados.
• supondo que os dadossão confiáveis, que um algoritmo adequado foi escolhido e
nenhuma outra hipótese foi violada, é possível determinar a árvore correta e
demonstrar sua validade científica?
• a resposta é negativa, pois nenhuma resposta será suficientemente conclusiva.
• a taxonomia está constantemente em revisão, conforme novos dados são obtidos e
ferramentas de análise mais poderosas são empregadas.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 13
3 A explosão combinatória de possibilidades
• quantidade de árvores distintas para o caso de 3 seqüências de atributos:
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 14
• quantidade de árvores distintas para o caso de 4 seqüências de atributos:
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 15
• 5 seqüências: 105 árvores candidatas
• 15 seqüências: 213.458.046.676.875 árvores candidatas
• 20 seqüências: 8.200.794.532.637.891.559.375 árvores candidatas
• n seqüências: ( )( )!22
!32
2 −
−
− n
n
n
• a situação “melhora” quando se toma árvores sem raiz: ( )( )!32
!52
3 −
−
− n
n
n
• encontrar a melhor árvore é um problema NP-hard (DAY, 1987)
3.1 Demonstração
• para duas folhas (n = 2) existe apenas uma topologia possível:
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 16
• a 3a folha, ao ser inserida, pode se combinar com os outros nós de três formas
diferentes:
• a 4a folha, ao ser inserida, pode se combinar com os outros nós de cinco formas
diferentes, e assim sucessivamente, até a enésima folha, que poderá se combinar
com os demais nós de 2n−3 maneiras diferentes. Assim, a fórmula para n folhas
fica:
( ) ( )∏
=
−=−⋅⋅⋅⋅
n
i
in
2
3232...531
• multiplicando o numerador e o denominador da última expressão por:
( ) ( ) ( )2)1(22)2(2...864222
1
2
−−⋅−−⋅⋅⋅⋅⋅=−∏
−
=
nni
n
i
resulta
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 17
( ) ( ) ( ) ( )
( ) ( )4262...642
32425262...654321
−⋅−⋅⋅⋅⋅
−⋅−⋅−⋅−⋅⋅⋅⋅⋅⋅⋅
nn
nnnn
• dividindo todos os n−2 fatores no denominador por 2, o número de árvores pode
finalmente ser apresentado na forma:
( )
( )!22
!32
2 −
−
− n
n
n
4 Formalização do conceito de árvore
4.1 Representação de uma árvore com raiz
• uma árvore com raiz T pode ser representada por um par ordenado T = (N, f),
onde:
¾ N é um conjunto de nós da árvore, sendo um deles o nó-raiz;
¾ f é uma função que associa a cada nó i ∈ N, com exceção do nó raiz, um único nó
f(i), denominado antecessor imediato ou pai de i. Cada associação de
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 18
antecedência imediata entre dois nós, realizada pela função f, representa um arco
da árvore;
¾ dado que um caminho (percurso pela árvore) é uma seqüência sem repetição de
arcos em que o segundo nó de cada arco coincide com o primeiro nó do arco
seguinte, então, para quaisquer pares de nós, existe um caminho único que leva de
um destes nós ao outro.
• dada a árvore da figura 1, então temos:
¾ N = {A, B, C, D, E, F, G}, sendo D o nó raiz;
¾ f(A) = B; f(C) = B; f(B) = D; f(F) = E; f(G) = E; f(E) = D.
• f(D) não está definido, pois o nó-raiz não apresenta antecessor imediato;
• não é possível afirmar que f(A) = D, pois embora D seja antecessor de A, D não é
antecessor imediato de A, papel que cabe ao nó B. No entanto, f(f(A)) = D;
• dado que um antecessor imediato é também denominado de nó-pai, todos os nós
que são antecedidos por ele são denominados nós-filhos.
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 19
D
B
CA
E
GF
Figura 1: Exemplo que árvore, sendo D o nó raiz
• nós-filhos que têm o mesmo nó-pai são denominados de nós-irmãos, sendo que o
número de nós-irmãos associados a um dado nó-pai é denominado grau do nó-pai.
• os nós ligados à raiz por arcos formam sub-árvores, que têm estes nós (no caso da
figura 1, são B e E) como sub-raízes. Tomando cada sub-árvore como uma nova
árvore, esta também pode ser sub-dividida adotando-se o mesmo procedimento.
• um nó de grau zero é chamado folha ou nó terminal;
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 20
• o nível de um nó é dado pela sua distância até a raiz, ou seja, pelo número de
arcos que devem ser percorridos. O nível pode ser dado também pelo número de
aplicações recursivas da função f. Tomando o exemplo da figura 1, dado que
f(f(A)) = D, então o nó A é dito ter nível 2;
• a altura de uma árvore é dada pelo nível máximo das folhas daquela árvore;
• quando o grau de qualquer nó que não seja nó terminal é definido como sendo
igual a k, então a árvore é chamada de árvore k-ária.
• dentre as árvores ordenadas de grau limitado destaca-se a árvore binária, onde
cada nó não-terminal tem dois nós-filhos. Neste caso, dizemos que um filho
corresponde à sub-árvore da direita e o outro à sub-árvore da esquerda;
• a caminhada por uma árvore binária é a principal operação básica. Através dela
pode-se percorrer todos os nós seqüencialmente e ter acesso a um nó específico.
Três formas de caminhada freqüentemente utilizadas são:
Análise de Dados em Bioinformática – Prof. Von Zuben
DCA/FEEC/Unicamp
Tópico 6: Árvores Filogenéticas 21
� caminho pré-fixado: raiz → sub-árvore da esquerda → sub-árvore da direita. O
caminho pré-fixado na árvore da figura 1 produz a seqüência D, B, A, C, E, F, G;
� caminho central: sub-árvore da esquerda → raiz → sub-árvore da direita. O
caminho central na árvore da figura 1 produz a seqüência A, B, C, D, F, E, G;
� caminho pós-fixado: sub-árvore da esquerda → sub-árvore da direita → raiz. O
caminho pós-fixado na árvore da figura 1 produz a seqüência A, C, B, F, G, E, D.
5 Referências bibliográficas
BROWN, S.M. “Molecular Phylogenetics: Computing Evolution”, New York University, School
of Medicine, Notas de Aula.
DAY, W.H.E. “Computational complexity of inferring phylogenies from dissimilarity
matrices”, Bull. Math. Biol, 49:461-467, 1987.
PRADO, O.G. “Computação Evolutiva Empregada na Reconstrução de Árvores Filogenéticas”,
Dissertação de Mestrado, Faculdade de Engenharia Elétrica e de Computação
(FEEC/Unicamp), Dezembro de 2001.