Parcimonie
Généralités•Principe• Orientation de l’arbre• Caractères
Procédure• Algorithme exact• Algorithme branch and bound• Algorithme heuristique
Analyse des résultats• Retour aux caractères• Arbre consensus• Saturation robustesse• Congruence
Phénétique, évolutionnisme, cladisme
Similitudes
Homoplasies
Homologiespartagées
Convergences
Réversions
Symplésiomorphies
Synapomorphies
Phénétique Évolutionnisme Cladisme
HomologieA B C
u 0 1 0
v 0 0 1
w 1 0 0
x 1 0 0
y 1 1 0
z 1 0 0
0
0
1
Apomorphies partagées
1
3
2
Homologies partagées
A et C
B et C
A et B
A CBu
vw
xy
z
A CBu
vw
xy
z
Phylogénie cladistePhylogénie évolutive
Parcimonie 1A B C
X 0 1 1
y 0 0 1
A B C
x
y
2 pas
A B C
x
y
x
3 pas
Parcimonie 2A B C D
U 0 0 1 1
V 0 0 1 1
W 0 0 1 1
X 1 1 0 0
Y 1 0 0 1
Z 0 0 1 0
A B C D
uv
wx
y
z y
A D B C
v v
u u
w w
z
xx
y
10 pas 7 pas
Arbre raciné ou non
E
ABC
DE
Arbre non raciné 7 arbres racinés
ou
A
BCDE
1
A
BC
DE
7
A
BCDE
4
A
BCDE
2
A
B
C
DE
6
AB
CD
E
5
A
BCDE
3
AB
C
D1
7
6
5
3
2
4
Raciner un arbre•Critères ontogéniques
problème posé par la néoténie
•Critère extra groupe
•Critères chorologiquescritère secondaire insuffisant seul
•Critères paléontologiques- absence de certains groupes- la parenté ne doit pas être trop éloignée
Extra-groupe 1X
ext-gA B C
P P P P’ P’
Q Q Q’ Q’ Q’
X A B C
P’
Q’
P
Q
X A B C
P’
Q’
P
Q
2 pas :il y a ambiguïté
Extra-groupe 2X Y A B C
Q Q Q Q’ Q’ Q’
X Y A B C
Q
Q’
1 pas
X Y A B C
Q
Q’
Q
2 pas
Extra-groupe 3X Y A B C
R R’ R R R R’
X Y A B C
R’
R
R’
X Y A B C
R
R
R’2 pas dans chaque cas, on ne peut trancher
Extra-groupe 4X Y Z A B C
R R’ R R R R R’
X Y Z A B C
R’
RRR
3 pas
X Y Z A B C
R
R’R’
2 pas
Extra-groupe 5
Y Z A B C X
R’
R
1 pas
X C A B Y Z
R’
R
1 pasLe choix des groupes externes est un à-priori. Si l’on conteste cette qualité on peut trouver un arbre
plus court
X Y Z A B C
R R’ R R R R R’
Caractère (1) c
t1 2 3
A 0 1 1
B 0 0 1
C 0 0 0
D 0 0 0
A
B
C
DT2
A
D
B
C T3
A B
CD T1info2 pas2 pas1 pasC3
non info
1 pas1 pas1 pasC2
constant
0 pas0 pas0 pasC1
typeT3T2T1
Caractère (2)
Binaire0 , 1
À états multiples0 , 1 , 2 , 3
Réversible01
Irréversible01
Irréversible0123
Additifs0 3 coûte 3pas01 coûte 1pas02 coûte 2 pas
Non additifs0 3 coûte 1pas01et 02 aussi
Réversible0123
Ou0 1
2 3
Caractère (3)
A G C T11 5
5
5
5
vers
deA C G T
A 0 5 1 5
C 5 0 5 1
G 1 5 0 5
T 5 1 5 0Graphe des états d’un caractère et matrice correspondante. Les transversions sont comptées 5 fois plus que les transitions.
Modèles de Wagner, Camin-Sokal, Dollo
c
t 1 2 3 4 5 6 7 8 9
A 0 1 0 0 0 0 0 0 1
B 1 0 1 1 1 0 0 0 0
C 1 0 0 1 1 1 1 1 0
D 1 1 1 1 1 1 1 1 1
E 0 0 0 1 1 1 1 1 1
X 0 0 0 0 0 0 0 0 0
EA B C DX
1 4 5
6 7 8
3 2 3
2 9
9
1
A B C D EX
4 5
6 7 8
3 1
1 2 3
2 9
9
1
EA B D CX
1 3 4 5
6 7 8
9 2
2 9
1
2 3
9
13 pas (Wagner)
14 pas (Camin-Sokal)
15 pas (Dollo)
apomorphieconvergencee
réversion
Une espèce éteinte: le quagga
Positions informatives
Gène Cytochrome OxydaseNADH
Déshydrogénase
position 4 10 67 103 28 58 71
Quagga A C T T C C T
Z.pl. A C T T C C T
Z.mt. A T C T T C C
Cheval G T C C C T C
Vache G T C C T T A
Méthode exhaustive (1)Avec 3 espèces un seul arbre est possible.
Le branchement pour la troisième espèce peut se faire sur n'importe laquelle des branches 1, 2 ou 3.
Zèbre plCTT
QuaggaCTT
Zèbre mtTCC
12
3
ChevalTCC
Zèbre plCTT
QuaggaCTT
Zèbre mtTCC
12
3
6 pas
6 pasCheval
TCC
Zèbre plCTT
QuaggaCTT
Zèbre mtTCC
12
3
Zèbre plCTT
QuaggaCTT
Zèbre mtTCC
12
3Cheval
TCC
3 pas
C'est l'arbre le plus court. On continue cependant sur les 3 arbres.
Méthode exhaustive (2)Zèbre pl
CTT
QuaggaCTT
Zèbre mtTCC
12
3Cheval
TCC
3 pas4
5
On peut ajouter une nouvelle espèce de 5 façons différentes.
14 pasVache
TCAGCTT
Zèbre plCTTATCC
QuaggaCTTATCC
Zèbre mtTCCATTC
ChevalTCCGCCT
123
6
457
CTTATCC
TCCATCC
14 pasCTTATCC1234567
11 pas
6
456TCCATCC
345
TCCATTT
11 pas45TCCATCT
TCCATCT
3456
9 pas457TCCATTC
3
1236
TCCGCTT6
VacheTCAGCTT
VacheTCAGCTT
VacheTCAGCTT
VacheTCAGCTT
CTTATCC
Zèbre plCTTATCC
Zèbre mtTCCATTC
ChevalTCCGCCT
QuaggaCTTATCC
CTTATCC
123
Zèbre plCTTATCC
Zèbre mtTCCATTC
ChevalTCCGCCT
QuaggaCTTATCC
TCCATCC123
6
457
Zèbre plCTTATCC
Zèbre mtTCCATTC
ChevalTCCGCCT
QuaggaCTTATCC
CTTATCC
123
Zèbre plCTTATCC
Zèbre mtTCCATTC
ChevalTCCGCCT
QuaggaCTTATCC
67
71234567
Méthode exhaustive(3)
Après avoir évalué tous les arbres on choisit le ou les plus courts
Branch and Bound
1 Évaluation de la longueur d’un
arbre au hasard.
2 L’exploration d’un chemin
s’arrête dès que cette longueur est
dépassée
Nombre d’Arbres Possibles
10 2 027 025 34 459 425
20 2,21643*1020
8 200 794 532 637 891 559 375
soit plus de 8*1021
N Tn non raciné
Tn raciné
x-2 nœudsx-3 segments internesx segments externesNombre d’arbres non
racinés
n Tn= (2k-5) k=3 Nombre d’arbres racinés n Tn= (2k-3) k=3
12
3
1 2
34
1
2
34
5
Algorithme de Wagner1
C
T 1 2 3 4 5
A 1 0 0 0 0
B 0 1 0 1 0
C 0 0 0 1 1
D 0 1 1 0 0
Distances 2 à 2
1 On connecte C et D (distance la pus grande)
D01100
C00011
Y00000
A10000
(Farris 1970 : methods for computing Wagner trees.Syst. Zool., 18:374-85)
2 Puis on ajoute A (ou B) au nœud YAY=1/2(AC+AD-CD)=1/2(3+3-4)=1
BY=1/2(BC+BD-CD)=1/2(2+2-4)=0
3 C’est donc A que l’on ajoute en premier.
Règle d’agglomération: les taxons les plus éloignés sont connectés
AB=3AC=3AD=3
BC=2BD=2
CD=4
Algorithme de Wagner2
Donc B est mis en Y’’
Y’’00000
B01010
D01100
C 00011
Y00000
A10000
D01100
C00011
Y00000
A10000
Y’
B
Y’’’
B
Y’’
B
Il reste à placer B sur un des 3 segments YA, YC ou YD.S’il est sur DY Y’B=1/2(BD+YB-YD) or YB=1/2(AB+CB-AC) et YD=1/2(CD+AD-AC) DoncY’B=1/2(BD+1/2(BA+BC)-1/2(CD+AD))= 1/2(2+1/2(3+2)-1/2(4+3)=0,5
S’il est sur AY Y’’B=1/2(BA+1/2(BC+BD)-1/2(CA+DA))=1S’il est sur CY Y’’’B=1/2(BC+1/2(BA+BD)-1/2(AC+DC))=0,5 BY’ = 0,5 BY’’ = 1 BY’’’ = 0,5
Algorithme de Wagner 3
Le résultat donne un des arbres qui n’est pas le plus court parmi les 3 arbres possibles. On peut à partir de là par branch swapping (ici NNI suffit) obtenir l’un des plus courts.
00010
D01100
A10000
C00011
B0101000000
01000
6 pas
7 pas
6 pas
D01100
A10000
C00011
B01010
00000
D01100
A10000 C
00011
B01010
00000
00000
Branch swapping:réarrangement local(NNI)
x y
zw
x w
zy
y x
zw
a e
fb
dc
a e
fb
cd
a e
fb
c d
Exemple 1
Exemple 2
Nearest-Neighbor Interchange
Branch swapping:réarrangement global(SPR) d
e
f
c
a ba
b
e
fc
d
a
b
e
f
d
c
a e
fb
dc
coupure
Subtree Pruning Regrafting
Branch swapping:réarrangement global(TBR)
a e
fb
dc
coupure
a
b
c
e
f
d
2 sous arbres à reconnecterde toutes les façons possibles
a
bc
e
f
da
bc
e
d
f
Tree Bisection-Reconnection
Exploration du paysage des arbres avec une heuristique
Matrice C
T1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
A 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
B 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0
C 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1
D 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
E 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0
ancêtre
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Non informatifs Informatifs Homoplasiques
DELayed TRANsformations
E
D
8 9
7
4 5 6
1
2 3
C19 20
10 11 12 13
B
A17
18
Il y a convergence sur les branches de
A et C pour les caractères 14 15 et 16
Dans cet exemple, l’option MINF donnerait le même résultat.
homoplasie
14 15 16
14 15 16
14 15 16
14 15 16
ACCelerated TRANsformation
réversion
C
E
D
8 9
7
4 5 6
1
2 3
19 20
10 11 12 13
B
A17
1814 15 16
La réversion est préférée à la convergence
pour rendre compte de l’homoplasie, elle concerne
3 caractères: 14, 15 et 16
14 15 16
Exclusion et pondération 1 1 1 1 1 11 2 3 4 5 6 7 8 9 0 1 2 3 4A G G C T G C A A T C G T GA G A C T T C C A T C G T GA C A C T G C C A * * T C G A C G C T G C G A T C G T G A C G C T T C G A T C G T GA G G C T G C A A T C G T G
La pondération différente entre transitions et transversions entraîne des valeurs différentes affectées
aux différents changements d’états du caractère 8. Il n’existe plus une valeur unique affectée à ce caractère.
Exclusion et pondération 2 1 1 1 1 11 2 3 4 5 6 7 8 9 0 1 2 3 4A G G C T G C A A G C C A GA G A C T T C C A G T C T GA C C C T G C C A G G G T G A C G C T G C G A G C G A G A C T C T T C G A G A G T GA G A C T G C A A G T C T G
Régions inversées répétées
Matrice de coût
BEGIN ASSUMPTIONS;USERTYPE tv STEPMATRIX=4 A C G U[A] . 1 0 1[C] 1 . 1 0[G] 0 1 . 1[U] 1 0 1 .;
Variabilité des nucléotides en fonction de leur position dans le codon
dans le gène rbcL
position 1 position 2 position 3toutes les positions
nombre total de sites
416 413 409 1238
sites variables
81 44 347 472
sites information
nels52 20 293 365
Saturation
0
10
20
30
40
50
0 10 20 30 40
transitions
tra
ns
ve
rsio
ns
Saturation: principe
424027
324116
28206
1684
D
C
B
A
DCBA Ve
Si
Comparaison de la vitesse d’évolution en transitions et en transversions pour la position
3 des codons du gène rbcL
transversions
tran
siti
ons
Comparaison de la vitesse d’évolution en transitions et en transversions pour les
positions 1 et 2 des codons du gène rbcL
0
0,5
1
1,5
2
2,5
3
3,5
4
4,5
0 2 4 6
transversions
tran
siti
ons
Saturation
Taxon A AGGT
Taxon B ACCT
Ancêtre commun
ACGT
CG GC
Taxon A AGGT
Taxon B ACCT
Ancêtre commun
ACGT
CTGA
ACTG
Pas de saturation: le nombre de changements observés est égal au nombre réel.
Saturation: le nombre de changements observés est inférieur au nombre réel.
CI, RI et RC
m
g
s
m=Lg minimum de l’arbre
s=Lg réelle de l’arbre
g=Lg maximum de l’arbre
mg
sgRI
s
mCI
s
m
mg
sg
mgsg
sm
RC
1
Variation de l’indice de consistance en fonction du nombre de taxa
Formule empirique NT: nb de taxaCI= 0,90-0,022NT+0,000213(NT)2
Sanderson, Donoghue (1989)Patterns of variation in levels in levels of homoplasy. Evolution 43 pp1781-95
Nb. Tax. CI
15 0,6179
16 0,6025
17 0,5876
18 0,5730
19 0,5589
20 0,5452
21 0,5319
22 0,5191
23 0,5067
24 0,4947
25 0,4831
26 0,4720
27 0,4613
Nb. Tax. CI
28 0,4510
29 0,4411
30 0,4317
31 0,4227
32 0,4140
33 ,0,4060
34 0,3980
35 0,3910
36 0,3840
37 0,3776
38 0,3716
39 0,3660
40 0,3608
Consensus strict et semi strict
FEDC
B
AArbre 1 Arbre 2
CBA
D
FE
F
EDC
AB
F
ED
C
A
B
Consensus strict Consensus semi strict
C
A
B
FED
F
ED
CB
A
Consensus majoritaire
Consensus d’AdamsA B C D E F G H I
Arbre 1 Arbre 3
A B D E C F G H I
Arbre 2
A D C B E F G H I
Consensus d’Adams
A C B D E F G H I
Consensus majoritaire
A C B D E F G H I
Indice de Bremer
A
B
C
D
E
F
G
Consensus des arbres de Lg=20 pas
A
B
C
D
E
F
G
Consensus des arbres de Lg21 pas
D=1
Congruence : principe
Le premier jeu de données donne des arbres
parcimonieux de Lg=x
Le second jeu de données donne des arbres
parcimonieux de Lg=y
La concaténation des 2 jeux de données donne
des arbres parcimonieux de Lg=z
Un test statistique permet de dire si la différence entre x+y et
z est significative ou non
Congruence : test ILDJeu 1
>1 AAAA>2 AGGA>3 AGAG>4 AAGG
Jeu 2>1 ggag>2 agga>3 gagg>4 aaaa
Jeux 1+2>1 AAAAggag>2 AGGAagga>3 AGAGgagg>4 AAGGaaaa
D=(lgx+lgy)-lgz
100 tirages au hasard
100 jeux simulésSimulation n
>1 AggAAggg>2 GagGGaaa>3 GgaGAggg>4 AaaAGaaa
Simulation n du jeu 1>1 AggA>2 GagG>3 GgaG>4 AaaA
Simulation n du jeu 2>1 Aggg>2 Gaaa>3 Aggg>4 Gaaa
Estimations de z
Estimations de x Estimations de y
On détermine la distribution des valeurs de D.
si pb Dobs5% Incongruence
D est-il significatif?
Comparaison des deux méthodes de calcul d’arbre
Vitesse moyenne. Sur de grosses machines on peut en plusieurs jours traiter des données jusqu'à 500 taxa
Rapide, même avec un grand nombre de taxa
Retour aux caractères pour éventuellement réévaluer ceux qui donnent des aberrations
Pas de retour aux caractères pour pouvoir les reconsidérer
Il y a un test de robustesse des noeuds (mesure de l’homoplasie dans l’arbre par le calcul du rapport de la longueur minimale de l’arbre à sa longueur réelle.
Pas de test de robustesse de l’arbre unique (excepté le bootstrap)
La méthode peut retourner plusieurs arbres également parcimonieux
Un seul arbre retourné par le programme
Examen des caractères les uns après les autres
Calcul d’une distance globale
Méthodes de parcimonieMéthodes de distance