Inférence de phylogénies. Inférence d’arbres phylogénétiques Méthodes de distance Input:...
Preview:
Citation preview
- Page 1
- Infrence de phylognies
- Page 2
- Infrence darbres phylogntiques Mthodes de distance Input:
Matrice de distances D Construire un arbre qui ralise cette
matrice: chaque paire (x,y) de feuilles est relie par un chemin
dont le score est gal la distance D(x,y) entre x et y. Mthodes de
parcimonie: Arbre qui explique lvolution des espces par un nombre
minimum de mutations. Deux composantes principales: Calcul dun
score dun arbre donn. Recherche, parmi tous les arbres, larbre de
score minimal. Mthodes probabilistes Maximisation de la
vraisemblance dun arbre Infrence Baysienne, base sur la probabilit
postrieure des hypothses en fonction des donnes.
- Page 3
- I. Mthodes de distance Distance additive tant donne une matrice
de distance D, existe-t-il un arbre binaire avec un tiquetage des
branches qui ralise la matrice, i.e. telque pour chaque paire de
feuilles i, j, la somme des tiquettes des branches du chemin qui
relie i et j est gal D(i,j). Si oui, la matrice D est additive. A A
0581211 B 5091312 C 89065 D 13603 E 1112530 ABCDE E D C B A 2 3 1 4
1 3 2 1
- Page 4
- Condition des 4 points D est additive si et seulement D
satisfait la condition des 4 points: Pour tout choix de 4 feuilles
A, B, C, D, deux des sommes suivantes sont gales et suprieures la 3
me : D(A,B) + D(C,D), D(A,D) + D(B,C) et D(A,C)+D(B,D) A C B D A C
B D A C B D
- Page 5
- Distances additives Une distance qui satisfait la condition des
4 points est une distance additive. A B C D 1 2 1 1 3 A A 0335 B
046 C 04 D 0 ABCD
- Page 6
- Distance ultramtrique D est ultramtrique ssi il existe un arbre
binaire racin avec tiquetage des nuds tq Le long dun chemin de la
racine une feuille les valeurs des tiquettes des nuds dcroissent
strictement; larbre ralise la matrice, i.e. pour chaque paire de
feuilles i, j, le LCA de i et j est tiquet D(i,j). A A 02444 B
20444 C 44033 D 44301 E 44310 ABCDE A BC D E 2 4 3 1
- Page 7
- Distance ultramtrique Contrainte plus forte quune distance
additive: Toute distance ultramtrique est additive A A 02444 B
20444 C 44033 D 44301 E 44310 ABCDE A BC D E 2 4 3 1 1 1 0.5 1.5 1
1 0.5
- Page 8
- Distance ultramtrique A A 0581211 B 5091312 C 89065 D 13603 E
1112530 ABCDE A BCD E 2 3 1 4 1 21 3 C D E 3 Contrainte plus forte
quune distance additive: Toute distance ultramtrique est additive
Mais toute distance additive nest pas ultramtrique
- Page 9
- Distance ultramtrique A A 0581211 B 5091312 C 89065 D 13603 E
1112530 ABCDE A BCD E 2 3 1 4 1 21 3 C D E 3 5 Contrainte plus
forte quune distance additive: Toute distance ultramtrique est
additive Mais toute distance additive nest pas ultramtrique
- Page 10
- Distance ultramtrique A A 0581211 B 5091312 C 89065 D 13603 E
1112530 ABCDE A BCD E 2 3 1 4 1 21 3 C D E 3 5 Contrainte plus
forte quune distance additive: Toute distance ultramtrique est
additive Mais toute distance additive nest pas ultramtrique 6
!!
- Page 11
- Distance ultramtrique T est un arbre ultramtrique associ la
distance ultramtrique D ssi: T contient n feuilles, chacune tiquete
par une ligne de D; Chaque nud interne est tiquet par une case de D
et a au moins deux fils; Le long dun chemin de la racine une
feuille les valeurs des tiquettes des nuds dcroissent strictement;
Pour deux feuilles quelconques i, j, D(i,j) est ltiquette du
dernier anctre commun de i et j dans T. T, sil existe, est une
reprsentation compacte de D. Remarque: T a au plus n-1 nuds
internes. Donc, si D a plus de n-1 valeurs, il nexiste pas darbre
ultramtrique pour D.
- Page 12
- Distance ultramtrique D est ultramtrique si et seulement si D
satisfait la condition des 3 points: Pour tout choix de 3 feuilles
A, B,C, parmi les trois distances D(A,B), D(A,C) et D(B,C), deux
sont gales et suprieures la troisime. Preuve: => vident ABC
D(A,C) = D(B,C) D(A,B)
- Page 13
- Distance ultramtrique D est ultramtrique si et seulement si D
satisfait la condition des 3 points: Preuve:
- Distance ultramtrique Cas gnral: A x y D(x,y) = ? Ce quon sait
par construction: D(A,x)= , D(A,y) = et D(A,x) < D(A,y) La
condition des 3 points => D(x,y) = D(A,y) =
- Page 16
- Distance ultramtrique Cas gnral: A x y D(x,y) = ? Ce quon sait
par construction: D(A,x)= , D(A,y) = et D(A,x) > D(A,y) La
condition des 3 points => D(x,y) = D(A,x) =
- Page 17
- Distance ultramtrique Cas gnral: A x y D(x,y) < ? Ce quon
sait par construction: D(A,x)= D(A,y) = , La condition des 3 points
=> D(x,y) <
- Page 18
- Distance/arbre ultramtrique Thorme: Si D est une matrice
ultramtrique, alors larbre ultramtrique de D est unique. En effet,
dans la preuve prcdente, les classes sont forces . Consquence: Si D
reflte effectivement la distance dvolution entre les espces, alors
larbre obtenu est ncessairement le vrai arbre. Thorme: Si D est
ultramtrique, alors larbre ultramtrique peut- tre construit en
temps O(n 2 ). De plus, on peut dterminer en O(n 2 ) si une
distance est ultramtrique ou non.
- Page 19
- Distance ultramtrique Si T est un arbre ultramtrique pour D, il
existe un tiquetage des branches de T qui ralise D tel que tous les
chemins de la racine nimporte quelle feuille sont de mme longueur.
Un tel arbre satisfait la thorie de lhorloge molculaire: taux de
mutation constant sur toutes les branches. A BC D E 2 4 3 1 1 1 0.5
1.5 1 1 0.5
- Page 20
- Que signifient des donnes ultramtriques? Distances tiquetant
les arbres ultramtriques supposes reflter le temps qui sest coul
depuis la sparation des deux espces. Thorie de lhorloge molculaire
(1960): Pour une protine donne, le taux de mutations acceptes par
intervalle de temps est constant. Donc, si k mutations acceptes
entre les protines A et B, on peut estimer k/2 le nombre de
mutations survenues sur chaque branche depuis lanctre commun de A
et B. Permet dobtenir des donnes ultramtriques.
- Page 21
- Algorithme UPGMA UPGMA: Algorithme de classification ascendante
hirarchique. Procde par regroupement des squences les plus proches.
chaque tape, les deux regroupements les plus proches sont fusionns.
Si D est une distance ultramtrique, alors UPGMA construit larbre
ultramtrique associ.
- Page 22
- Algorithme UPGMA n squences; D i,j : Distance entre les
squences i et j. D ij distance entre deux regroupements C i et C j
: Moyenne des distances des paires de squences entre les deux
regroupements. Si C k = C i U C j et C l est un autre regroupement,
alors:
- Page 23
- Page 24
- Page 25
- Distance/arbre additif T arbre additif pour D si pour toute
paire de nuds (i,j), le poids total du chemin de i j est
D(i,j).
- Page 26
- Distance/arbre additif Problme: Trouver un arbre additif pour D
ou dterminer quun tel arbre nexiste pas. Thorme: Il existe un arbre
additif pour D ssi D est une distance additive (i.e. vrifie la
condition des 4 points). Distance additive: Contrainte moins forte
que la contrainte ultramtrique. Une distance ultramtrique est
additive. Le contraire nest pas vrai. Cependant, les donnes relles
sont rarement additives
- Page 27
- Neighbor-Joining (Saitou et Nei en 1986) Algorithme glouton qui
choisit chaque tape une paire de feuilles voisines. Paire de
feuilles voisines: Deux feuilles de T ayant le mme pre. Un arbre
est dtermin par lensemble des (n-2) paires de voisins quil
contient. 1 2 3 4 5 6 7 (1,2), (6,7),(4,5),
((1,2),3),((4,5),(6,7)), (((4,5),(6,7)), (1,2),3))
- Page 28
- Neighbor-Joining Choisir deux objets i, j garantis dtre voisins
dans un arbre additif. Supprimer i, j de la liste des objets et
rajouter le nud cr k correspondant au pre commun de i et j.
Distance de k une feuille m quelconque: 1 2 3 4 5 6 7 i j k m
D(k,m) = (D(i,m)+ D(j,m) - D(i,j) )1/2
- Page 29
- Neighbor-Joining Comment dterminer, partir de D, deux feuilles
qui sont ncessairement voisines dans un arbre additif de D? Il ne
suffit pas de choisir une paire dobjets dont la distance est
minimal: 12 43 1 1 1 4 4 (1, 2) de distance minimale, mais pas
voisines dans larbre.
- Page 30
- Neighbor-Joining L: Ensemble des feuilles dun arbre additif.
Pour tout (i,j), D (i,j): valeur obtenue en soustrayant de D(i,j)
la distance moyenne de i et j toutes les autres feuilles. D (i,j) =
D(i,j) (r i +r j ) Thorme: Si T est un arbre additif pour la
distance additive D, si (i,j) est une paire de feuille telle que D
(i,j) est minimal parmi toutes les paires de feuilles, alors i et j
sont voisines dans T.
- Page 31
- Page 32
- II. Mthodes de parcimonie Bases sur le principe de maximum de
parcimonie: La meilleure hypothse pour expliquer un processus est
celle qui fait appel au plus petit nombre dvnements. la diffrence
des mthodes de distances, considre chaque site dun alignement
multiple individuellement. Sous-entend lhypothse dindpendance des
sites. Mthode gnrale: Considrer toutes les topologies darbres
possibles sur un ensemble de feuilles; Calculer un poids pour
chaque arbre; Slectionner un arbre de poids minimal.
- Page 33
- Mthodes de parcimonie Pondration dun arbre: Affecter des
squences aux nuds internes de telle sorte minimiser le poids total
de larbre (somme des poids des branches). Exemple: S 1 : AAG S 2 :
AAA S 3 : GGA S 4 : AGA S1S1 S2S2 S3S3 S4S4 S1S1 S3S3 S2S2 S4S4
S1S1 S4S4 S2S2 S3S3 AA G A A A A 1 AA G G A G A 1 G AAA A A A 1
Poids de larbre: 3
- Page 34
- Mthodes de parcimonie Pondration dun arbre: Affecter des
squences aux nuds internes de telle sorte minimiser le poids total
de larbre (somme des distances des branches). Exemple: S 1 : AAG S
2 : AAA S 3 : GGA S 4 : AGA S1S1 S2S2 S3S3 S4S4 S1S1 S3S3 S2S2 S4S4
S1S1 S4S4 S2S2 S3S3 AA G A A A A 1 AA G G A G A 1 G AA A A A A 1
AAG GGAAAA AGA AAG AGA AAA GGA AAA 1 2 11 12 Poids de larbre: 3 4
4
- Page 35
- Parcimonie pondre (Algorithme de Sankoff) On ne compte pas
juste le nombre de substitutions, mais un poids S(a, b) pour la
substitution de a en b. tiqueter les nuds internes de telle sorte a
minimiser le poids total de l'arbre. Par rcurrence: tiquette d'un
nud dduite des tiquettes des nuds fils. S k (a): poids du
sous-arbre de racine k, sous la condition que k est tiquet par
a.
- Page 36
- Parcimonie pondre (Algorithme de Sankoff) k: a i j b a S k (a)
= 0 k: S k (b) = S k (a) = min b (S i (b) + S(a,b))+ min c (S j
(c)+S(a,c) c
- Page 37
- Parcimonie pondre (Algorithme de Sankoff)
- Page 38
- Pour retrouver les nuclotides aux nuds internes, garder des
pointeurs l k (a) et r k (a) pour chaque a et chaque nud k, et
rajouter les deux instructions suivantes dans le bloc de rcurrence:
Poser l k (a) = argmin b (S i (b) + S(a,b)) Poser r k (a) = argmin
b (S j (b) + S(a,b)) Pour retrouver une assignation correcte pour
les nuds internes, choisir un nuclotide la racine qui donne lieu un
poids S 2n-1 (a) minimal, et suivre les pointeurs. Complexit: Pour
un nud donn, il faut calculer 2| | 2 minima. Do, complexit de
lalgorithme en O(n| | 2 ) o n est la taille de l'arbre (nombre de
nuds).
- Page 39
- 1: C 2: T 3: G 4: T5: A6: T 0 000 0 0 2112 T, C ATCG S(a,b) = 1
si a b 2121 T, G T,C 4334 2222 9 11 5345 7 8 A,T,C,G 10 T T T T T
T
- Page 40
- Parcimonie traditionnelle Algorithme de Fitch Minimiser le
nombre de substitutions de caractres. Garder chaque nud une liste
de nuclotides valides . C: poids courant de larbre.
- Page 41
- Parcimonie traditionnelle Algorithme de Fitch Pour retrouver
les nuclotides des nuds internes: Choisir un nuclotide dans R 2n-1
(racine) puis descendre dans l'arbre. Si on a choisit a pour k,
alors, pour le fils i de k, choisir a si possible, si non choisir
un nuclotide au hasard dans R i. Complexit: O(n| |) Observation: Le
poids minimal dun arbre calcul par lalgorithme de Fitch est
indpenant du choix de la racine. Consquence: on na pas besoin de
tester tous les arbres racins possibles.
- Page 42
- 1: C 2: T 3: G 4: T5: A6: T 9 11 7 8 10 C = 0 R 1 = {C}R 2 =
{T} R 3 = {G} R 4 = {T} R 5 = {A}R 6 = {T} R 7 = {C,T} +1 R 8 =
{G,T} +1 R 9 = {G,T,A} +1 R 10 = {T} R 11 = {T} T T T T T
- Page 43
- Parcimonie traditionnelle Algorithme de Fitch Problme de la
parcimonie traditionnelle: Certaines assignations possibles des
nuds internes ne sont jamais considres.
- Page 44
- numration de tous les arbres possibles
- Page 45
- Page 46
- Exploration des topologies Plutt que de considrer toutes les
topologies possibles, on a recours des heuristiques. Mthode gnrale:
Considrer une topologie initiale T, Explorer un voisinage de T:
Tous les arbres qui sont une distance donne de T. Conserver larbre
(ou les arbres) qui a le meilleur score. Diffrentes distances
utilises: Nearest Neighbor Interchange (NNI) Subtree Pruning and
Regrafting (SPR)
- Page 47
- Choix de larbre de dpart Recherche squentielle: Algorithme
glouton; construit larbre en rajoutant une arte chaque tape.
Construire un arbre T non racin partir de trois objets de dpart (2
objets dans le cas dun arbre racin). Pour T contenant r feuilles,
choisir un r+1me objet et le placer de faon optimale dans T. Choix
des taxons rajouter Alatoire; pas idal Approche du maximum du
minimum: Pour chaque taxon, essayer les 3 positionnements possibles
sur larbre initial de 3 feuilles. Garder les valeurs minimales.
Ordonner les taxon par cette procdure: valeurs dcroissantes.
Procdure qui augmente la vitesse dobtension de larbre le plus
parcimonieux.
- Page 48
- 123456 AATTAAT BTTATTT CAATTTT DAATAAA ETTAAAT A B C A B C D A
D C B A C B D A D C B E A D C B E A D C B E A D C B E A D C B E 8 7
9 9 9 9 11 9
- Page 49
- Choix de larbre de dpart Branch-and-bound: Explorer toutes les
topologies possibles. Lorsque le poids de larbre courant dpasse une
certaine borne L S, arrter linsertion de feuilles pour cet arbre. L
S : Poids du meilleur arbre complet obtenu au cours de la recherche
squentielle.
- Page 50
- 123456 AATTAAT BTTATTT CAATTTT DAATAAA ETTAAAT A B C A B C D A
D C B A C B D A D C B E A D C B E A D C B E A D C B E A D C B E 8 7
9 9 9 9 11 9 L S = 9
- Page 51
- 123456 AATTAAT BTTATTT CAATTTT DAATAAA ETTAAAT A B C A B C D A
D C B A C B D 8 7 9 A B C D E A B C D E A B C D E A B C D E A B C D
E 10 8 11 L S = 8
- Page 52
- 123456 AATTAAT BTTATTT CAATTTT DAATAAA ETTAAAT A B C A B C D A
D C B A C B D 8 7 9