Parcimonie Généralités Principe Orientation de larbre Caractères Procédure Algorithme exact...

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