Introduction à la

phylogénie moléculaire

Céline Brochier ([Link]-armanet@[Link]) 2015-2016

([Link]
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Intérêt d’étudier l’évolution moléculaire et la

phylogénie
 Prépondérante en biologie
 Ecologie

 Evolution

 Microbiologie

 Biologie cellulaire, etc.

 Permet d’aborder des questions très variées

 Histoire évolutive du matériel génétique

 Histoire évolutive des espèces / taxa

 Identification / Classification

 Etudes comparatives: Analyse de l’évolution des caractères

 etc.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Naissance de la phylogénie moléculaire

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Arbres phylogénétiques
 Les arbres sont des graphes A
connexes acycliques F
 Nœuds = unités taxonomiques
(UT)
 Opérationnelles (UTO) = A, B, C,
D, E = feuilles de l’arbre Racine H B
 Hypothétiques (UTH) = F, G, H, I
= nœuds internes
C
 Branches
 internes = succession G
d’organismes reliant deux UTH I
 externes = succession
d’organismes reliant entre UTH
et UTO D
 Topologie (forme) de l’arbre =
Ensemble des branchements de
l’arbre (nœuds + branches)
 Racine = ancêtre commun le plus
récent à tous les UTO E
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Deux branches sœurs peuvent pivoter

librement autour du nœud qui les connecte
D A C A

C B D
B

E E

E A

Cet arbre est différent

C des deux précédents
B

D
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Arbres racinés et arbres non racinés

A
F C

B
Racine H B D
G
C
G F H
I A

E E
La racine permet de suivre chemin Sans racine il n’est pas possible de
évolutif séparant chaque feuille de déterminer les relations de parenté
l’ancêtre commun à tous les UTO entre les UTO

La racine représente l’ancêtre commun le plus récent à tous les UTO

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Il y a autant de racines possibles que de

branches dans un arbre non raciné
1 2 3

3 C
2 4 C D E B A C D E A B A B E D C
B
7
G D 4 5

F H 6
A
A B E C D A B C D E
1
5 6 7

A B E C D C D E A B

Chacune induit une histoire évolutive particulière… mais une seule est vraie
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Enraciner un arbre phylogénétique

 La majorité des méthodes de reconstruction phylogénétique

produisent des arbres non racinés, car elles n’intègrent pas de
dimension temporelle
 L’enracinement se fait donc indépendamment de la méthode choisie
 Deux approches:
 Enracinement au poids moyen

 Enracinement par un groupe extérieur

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Enracinement au poids moyen

 Hypothèse: Toutes les séquences évoluent à la même vitesse (i.e.

hypothèse d’horloge moléculaire)
 La même quantité dévolution s’est produite dans chaque lignée évolutive
depuis leur ancêtre commun à toutes
 Les distances évolutives entre chaque feuille et la racine sont égales
 La racine est placée au point de l’arbre équidistant de toutes les feuilles
D
E
C C
D
E
A
B
1
B A
d
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Exemple d’enracinement au poids moyen

Fig 5.
Phylogenetic tree showing the relationship of BtubA and BtubB relative to
eukaryotic α and β tubulins. Tree presented is parsimony tree rooted at the
midpoint. Circles indicate bootstrap values. Nodes supported at >75% in the
majority of analyses are indicated by the filled circles. Nodes supported at 50–74%
in most analyses are indicated by the open circles. Unsupported nodes (<50%)
have no circle. (Bar = 0.1 substitutions per site.)

(Jenkins et al. (2002) PNAS)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Cas où l’enracinement au poids moyen

pourrait conduire à une erreur

(van de Peer et al. (2000) gene)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Enracinement avec un groupe extérieur

 Pré-requis: inclure dans l’analyse un groupe de séquences homologues aux

séquences analysées mais dont on sait a priori qu’elles sont extérieures
aux séquences analysées
 La racine est défini par le nœud reliant le groupe extérieur aux séquences
étudiées
H
F
G
E
C
D
A
0.1 B
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Exemple d’enracinement avec un groupe

extérieur (taxa)
Autres phyla
bactériens

Thermotogae

Fig. S2
Bayesian phylogenetic trees of SSU rRNA. 75 sequences and 1048
unambiguously aligned nucleic acid positions were used. Numbers at
nodes represent posterior probabilities (PP) inferred by MrBayes and
bootstrap values (BV) inferred by TreeFinder. For clarity only PP > 0.50
and BV > 50% are shown. Scale bars represent the average number of
substitutions per site. Thermotogales sequences retrieved from
mesothermic environments are shaded.

(Ben Hania et al (2011) Syst Appl Micro)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Exemple d’enracinement avec un groupe

extérieur (paralogues)

(Brown and Doolittle et al (1995) PNAS)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Arbres résolus et arbres multifurqués

Arbres résolus
B
A
E E
E
C C
D D
0,1
A A D
B B
0,1 0,1 C

Arbres multifurqués
B
A
E E
E
C C
D D
0,1
A A D
B B
0,1 0,1 C
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Longueurs des branches d’un arbre B

E A
E
C C E

D D

A A 0,1
D
B B
D A 0,1
C
Phylogrammes: la longueur des branches est
proportionnelle à la distance évolutive entre les séquences
(nb substitutions / site)
C B E
Arbres ultramétriques: la
C longueur des branches
représente un % de
E D
divergence (phénogrammes)
Cladogrammes: la longueur des branches A ou le temps
est arbitraire et ne reflète pas la distance (chronogrammes)
évolutive séparant les séquences 0,1 B
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Apparentement et similarité

E
H2 C
D
H3 A
0,1
H1 B

B est plus apparenté à A qu’à C, D ou E

B est apparenté de manière égale à C et D
B est plus apparenté à C ou D qu’à E
C est plus apparenté à D qu’à A, B ou E
C est plus apparenté A ou B qu’à E
E est aussi apparenté à A, B, C ou D
A, B, C, D et E sont apparentés de manière égale à leur ancêtre commun
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Apparentement et similarité
… mais C est plus similaire à A qu’à D
E
H2 C
D
H3 A
0,1
H1 B
d C  D  d C  H 2  d D  H 2  d C  A  d C  H 2  d H 2  H 3  d H 3  H 1  d H 1 A

B est plus apparentés à A qu’à C, D ou E

B est apparenté de manière égale à C et D
B est plus apparenté à C ou D qu’à E
C est plus apparenté à D qu’à A, B ou E
C est plus apparenté A ou B qu’à E
E est aussi apparenté à A, B, C ou D
A, B, C, D et E sont apparenté de manière égale à leur ancêtre commun
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Notion d’ancêtre commun et de parenté

1) Premier ancêtre commun

2) Dernier ancêtre commun

3) Ancêtre commun exclusif

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Divergence ≠ diversification d’un groupe

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Ancestral ≠ dérivé / Ancien ≠ récent

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Groupes mono-, para-, polyphylétiques

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Format Newick
 Les UTO sont séparés par des
«,» C
 La ligne est terminée par un
«;» B
 Les UTO descendant d’un L3
L7 D
même nœud sont indiquées L2
par des ( ) L4
 ( (A , B) , E , ( C , D ) ) ; L6
 Les longueurs des branches L1
sont précédées par « : » A
 ( (A:L1 , B:L2):L6 , E:L5 , (C:L3 ,
L5
D:L4):L7 ) ;
 Des labels (e.g. BV, PP)
peuvent être associés à
chaque nœud E
 ( (A:L1 , B:L2) BV1 :L6 , E:L5 ,
(C:L3 , D:L4) BV2 :L7 ) ;
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

2 feuilles  1 topologie
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

A C B

2 feuilles  1 topologie
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

A C B
A C B

2 feuilles  1 topologie
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

A C B C A B
A C B

2 feuilles  1 topologie
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

Ajout du taxon D
=> 5 possibilités
A C B C A B
A C B

2 feuilles  1 topologie
3 feuilles  3 topologies
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

Ajout du taxon D
=> 5 possibilités
A C B C A B
A C B

2 feuilles  1 topologie
3 feuilles  3 topologies
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

Ajout du taxon D
=> 5 possibilités
A C B C A B
A C B

A DC B
A C B D

A C D B
A DC B A C D B

2 feuilles  1 topologie
3 feuilles  3 topologies
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres racinés ?

A B

Ajout du taxon C => 3 possibilités

Ajout du taxon D
=> 5 possibilités
A C B C A B
A C B

A DC B
A C B D

A C D B
A DC B A C D B

2 feuilles  1 topologie 4 feuilles  15 topologies

3 feuilles  3 topologies
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Combien d’arbres?
• Nb UTO  Arbres racinés
2 1
3 3
4 15
5 105
6 ( 2 n  3 )! 945
7 n2 10 395
2 ( n  2 )!
8 135 135
9 2 027 025
10 34 459 425

20 ~ 8.2 x 1021

30 ~ 2.75 x 1076

NNR = (2n-5)! / [2n-3 x (n-3)] !

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Application
• Nb UTO  Arbres racinés  Arbres non racinés
2 1 1
3 3 1
4 15 3
5 105
15
6 ( 2 n  3 )! 945 ( 2 n  5 )! 105
7 n2 10 395 n3
2 ( n  2 )! 2 ( n  3 )! 945
8 135 135
9 2 027 025 10 395
10 34 459 425 135 135
2 027 025
20 ~ 8.2 x 1021 ~2.2 x 1020

30 ~ 2.75 x 1076 ~2.8 x 1074

NRracinés
nb d’arbres non = (2n-3)!
pour/ [2nn-2UTO
x (n-2)]
= nb! d’arbres
NNRracinés
= (2n-5)!
pour
n-3 x (n-3)] !
/ [2n-1 UTO
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Estimation de la robustesse des arbres :

Bootstrap
 Un problème majeur en phylogénie est d’estimer la force des
regroupements observés
 Idée = estimer la variabilité de l’arbre (ou d’une partie de l’arbre)
 Étude de la robustesse des arbres
 Si un arbre est robuste i.e. fortement soutenu par les données
alors sa variabilité sera faible, et les regroupements observés
devraient être retrouvés même si on perturbe un peu les
données
 Si un arbre est peu robuste alors il aura une grande variabilité, et
les regroupements observés seront très instables en cas de
perturbation des données
 Estimation de la force avec laquelle les données (i.e.
l’alignement) soutiennent les regroupements observés
 Association d’un estimateur de la robustesse à chaque branche
de l’arbre
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le Jacknife – Wu 1986 Felsenstein 1985

 On réalise X tirages sans remise de n/2 sites au sein du jeu de données

initial
 Construction d’un nouvel alignement contenant le même nombre de
séquences et la moitié des sites de l’alignement initial
 Certains sites seront totalement absents du nouvel alignement

 pondération des sites par la valeur 0 ou 1

 D’un tirage à l’autre les combinaisons de sites absents seront différentes et
les combinaisons de sites présents seront différentes
 Chaque tirage (i.e. combinaison de sites) est unique, car la pondération des
sites change à chaque tirage

 Pour chaque tirage on calcule la phylogénie correspondante par la même

méthode
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le Jacknife Estimation
de l’arbre
seq1
seq2
Alignement seq3
initial …
seqN
1 2 3 4 5 6 7 8 9 10 111213141516 17181920

Jacknife seq1
sample #1 seq2
seq3
…
seqN
2 5 7 9 121315 171820

Jacknife seq1
sample #X seq2
seq3
…
seqN
4 5 9 1012131416 1719
La robustesse de chaque branche de l’arbre initial peut être estimée par le nombre
de fois où cette même branche est retrouvée dans les réplicats de Jacknife
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le Bootstrap

 Contrairement au Jacknife, la procédure de bootstrap s’appuie sur

des alignements ré-échantillonnés de même taille que l’alignement
initial
 On réalise X tirages avec remise de n sites parmi les n sites
contenus dans l’alignement initial
 Certains sites seront présents plusieurs fois dans le nouvel alignement
 Certains sites seront absents du nouvel alignement
 Pondération des caractères variant entre 0 et n
 D’un tirage à l’autre les sites absents ou présents plus d’une fois
seront différents
 Chaque tirage (i.e. combinaison de sites) est unique car la
pondération des sites est aléatoire d’un tirage à l’autre

 Pour chaque tirage on calcule la phylogénie correspondante par la

même méthode
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le Bootstrap Estimation
seq1 de l’arbre
seq2
JDD seq3
initial …
seqN
1 2 3 4 5 6 7 8 9 10 111213141516 17181920

Bootstrap seq1
sample #1 seq2
seq3
…
seqN
5 8 8 8 9 101012 13 1315

Bootstrap seq1
sample #X seq2
seq3
…
seqN
1 1 2 4 7 7 1111 11 11 12
La robustesse de chaque branche de l’arbre initial peut être estimée par le nombre
de fois où cette même branche est retrouvée dans les réplicats de Bootstrap
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Interprétation du Jacknife et du Bootstrap

 Une valeur de bootstrap de 100%  un nœud vrai

 ROBUSTESSE  VERACITE !

 Une BV de 100%  un nœud ROBUSTE

GROUPE
Homme Rhino
EXTERIEUR

Dauphin CETACES Baleine

98

Cerf RUMINANTS Cerf

99 Cochon SUIFORMES Pécari

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Cause de l’incongruence/problèmes
rencontrés en phylogénie moléculaire

 Problèmes d’échantillonnages
 Séquences trop courtes => effets stochastiques
 Échantillonnage taxonomique trop réduit
 Problèmes liés à la divergence des séquences
 Séquences pas assez variables
 Séquences trop divergentes => saturation
 Séquences présentant des taux d’évolution hétérogènes
(Attraction des longues branches)

=> Facteurs non exclusifs !

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Pour vous entrainer

 [Link]
 Rubrique enseignement

 « Tree Thinking Challenge »

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Caractères et états de caractères

 Caractère = caractéristique observable d’un organisme

(quantitative ou qualitative)

 État de caractère = forme particulière d’un caractère dans une

UTO particulière (variable continue ou discrète)

Exemple
Caractère Taille Pos. 68 CYTB
État de caractères 1,68 cm Alanine
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Arbres vrais et arbres inférés

 La succession des événements de spéciation, de duplications et de

transferts qui a conduit aux séquences étudiées est unique !

 Parmi tous les arbres possibles un seul représente la véritable

histoire évolutive = ARBRE VRAI

 Le (ou les) arbre(s) obtenu(s) à partir d’un gène particulier et une

méthode de reconstruction est appelé ARBRE INFERE
 Hypothèse sur la manière dont s’est faite l’évolution

L’ARBRE INFERE ARBRE VRAI

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Reconstruire un arbre
 Inférer une phylogénie  procédure d’estimation de la véritable
histoire évolutive à partir de données incomplètes

 Spécification de critères permettant de sélectionner un ou plusieurs

arbres parmi l’ensemble des arbres possibles
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Reconstruire un arbre
 Inférer une phylogénie  procédure d’estimation de la véritable
histoire évolutive à partir de données incomplètes
Meilleur arbre
(maximum global)

 Spécification de critères permettant de sélectionner un ou plusieurs

arbres parmi l’ensemble des arbres possibles
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Méthodes
 Méthodes de distances
 Recherche l’arbre qui représente au mieux les distances évolutives
entre paires de séquences
 Requière l’estimation des distances évolutives entre paires de
séquences, sachant un modèle d’évolution
 UPGMA, NJ, minimum d’évolution, moindres carrés…

 Méthodes cladistiques
 Recherche l’arbre impliquant le moins de changements évolutifs
permettant d’expliquer les données
 Considèrent les sites individuellement
 Maximum de parcimonie

 Méthodes statistiques
 Recherche l’arbre ayant la plus forte vraisemblance sous le modèle
d’évolution considéré
 Considèrent les sites individuellement
 Maximum de vraisemblance, Méthodes bayésiennes
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Données utilisées en phylogénie moléculaire

 Point de départ = alignement de séquences homologues

 Arrivée = arbre décrivant les liens évolutifs entre les séquences de
l’alignement
neuroglobin
58
cytoglobin
53 myoglobin
98 beta
delta
100 epsilon
80 gammaA
100 gammaG
mu
52
zeta
76 theta
109 / 230 positions
conservées pour l’analyse 79 alpha2
100 alpha1 0.1

(Alignement des 13 globines humaines réalisé avec clustalW ([Link]

arbre construit avec Seaview (BioNJ, 100 réplicats de bootstrap))
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Alignements et gaps
 Chaque colonne de l’alignement représente une position (ou site)
composée de résidus homologues, cad dérivant d’un même site ancêtre
 La qualité des alignements est essentielle
 Les régions où l’alignement est ambigu doivent être retirées
(automatiquement ou manuellement) avant l’analyse phylogénique
 La plupart des méthodes de reconstruction ne prend en compte que les
substitutions et non les événements d’insertions/délétions
 Les sites contenant des gaps sont ignorés

230 218

(ClustalW) (Muscle)
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Méthodes de distances
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Méthodes de distances - Principe général

 Plusieurs méthodes (UMGMA, NJ, ME, etc.)
 Deux grandes étapes
 Construction de la matrice de distances

 Reconstruction d’un arbre phylogénique dont les (di,j) sont les + proches
possibles des (di,j)  minimise Q n n

Alignement de séquences
Q    (d i, j  di, j)
i 1 j
homologues

S2 S4 S5
Modèle d’évo. l4
S1 l2
S1 S 2 S3 S 4 S5 S3 l5
l1
S1  d 1, 2 d 1, 3 d 1, 4 d 1, 5 l3 l6
S 2 d 2 ,1  d 2 ,3 d 2,4 d 2 ,5
l8
S3 d 3 ,1 d 3,2  d 3,4 d 3,5
l7
S 4 d 4 ,1 d 4,2 d 4 ,3  d 4 ,5 Méthode de dist.
S5 d 5 ,1 d 5,2 d 5 ,3 d 5,4 
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2

Un estimateur simple: La divergence

observée (p-distance)
 Estimateur le + simple

n
 p


 p = p-distance
 n = nb de sub. obs.

  = nb de résidus comparés

 Variance p (1  p )
Var ( p ) 

 Soit 2 séquences ayant des * * ** * *
compositions homogènes Nb sub. obs. = 3  p = 3/14 = 0.214
 0  p  0 . 75 (ADN) Nb sub. réel. = 12 /14  d = 0.857

 0  p  0 . 95 (Protéines) La p-distance  d quand la saturation mutationnelle

est faible, cad quand les subs. multiples sont rares

(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Modèles d’évolution couramment

utilisés en phylogénie moléculaire
Modèle de Jukes et Cantor (1 paramètre)
3  4 
d  ln  1  p 
4  3 
A G A G

T C T C

Modèle de Kimura (2 paramètres)

1 1
d  ln 1  2 r  v   ln( 1  2 v )
2 4
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

UPGMA - Application
Matrice de distances extraite de Sarich 1969

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0 32 48 51 50 48 98 148

Ours 32 0 26 34 29 33 84 136

Racoon 48 26 0 42 44 44 92 152

Belette 51 34 42 0 44 38 86 142

Phoque 50 29 44 44 0 24 89 142

Otarie 48 33 44 38 24 0 90 142

Chat 98 84 92 86 89 90 0 148

Singe 148 136 152 142 142 142 148 0

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

UPGMA (Unweighted pair-group method

with arithmetic means)
 Algorithme itératif de clustering: création à chaque étape d’un
nouveau cluster regroupant deux clusters proches (Sokal et
Michener, 1958)
 L'arbre est construit "de bas en haut" : on part des feuilles et à
chaque étape on rajoute un nœud au-dessus des précédents
 Condition d’application
 Hypothèse d’horloge moléculaire  constance des taux
d’évolution le long des lignées
 Caractéristiques des arbres obtenus
 Ils sont racinés

 Les longueurs des branches allant de la racine à n’importe quelle

feuille sont égales
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

UPGMA - Algorithme

1. Trouver les deux UTO i et j pour lesquels la distance dij est la

plus petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij =
ni + nj (ni et nj  nombre d’UTO dans les groupes i et j)
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij). Attribuer aux branches Li
et Lj connectant i à (ij) et j à (ij) la longueur dij /2
4. Calculer la distance entre le nouveau groupe (ij) et tous les
autres groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk / (ni
+ nj)
5. Éliminer les colonnes et les lignes correspondant aux groupes
i et j et ajouter celles correspondant au nouveau groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon
retourner en 1.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

UPGMA - Application
Matrice de distances extraite de Sarich 1969

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0 32 48 51 50 48 98 148

Ours 32 0 26 34 29 33 84 136

Racoon 48 26 0 42 44 44 92 152

Belette 51 34 42 0 44 38 86 142

Phoque 50 29 44 44 0 24 89 142

Otarie 48 33 44 38 24 0 90 142

Chat 98 84 92 86 89 90 0 148

Singe 148 136 152 142 142 142 148 0

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

1. Trouver les deux UTO i et j pour lesquels la distance dij est la plus
petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij = ni +
nj (ni et nj  nombre d’UTO dans les groupes i et j)
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij). Attribuer aux branches Li et Lj
connectant i à (ij) et j à (ij) la longueur dij /2
4. Calculer la distance entre le nouveau groupe (ij) et tous les autres
groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk / (ni + nj)
5. Éliminer les colonnes et les lignes correspondant aux groupes i et j
et ajouter celles correspondant au nouveau groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon retourner
en 1.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0 32 48 51 50 48 98 148

Ours 32 0 26 34 29 33 84 136

Racoon 48 26 0 42 44 44 92 152

Belette 51 34 42 0 44 38 86 142

Phoque 50 29 44 44 0 24 89 142

Otarie 48 33 44 38 24 0 90 142

Chat 98 84 92 86 89 90 0 148

Singe 148 136 152 142 142 142 148 0

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

1. Trouver les deux UTO i et j pour lesquels la distance dij est la plus
petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij = ni +
nj (ni et nj  nombre d’UTO dans les groupes i et j) nij = ni + nj
 nij = 1 + 1 = 2
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij). Attribuer aux branches Li et Lj
connectant i à (ij) et j à (ij) la longueur dij /2
4. Calculer la distance entre le nouveau groupe (ij) et tous les autres
groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk / (ni + nj)
5. Éliminer les colonnes et les lignes correspondant aux groupes i et
j et ajouter celles correspondant au nouveau groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon retourner
en 1.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

1. Trouver les deux UTO i et j pour lesquels la distance dij est

la plus petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij
= ni + nj (ni et nj  nombre d’UTO dans les groupes i et j)
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij).
Attribuer aux branches Li et Lj connectant i à (ij) et j à (ij) la
longueur dij /2 soit Li = 24/2 = 12 et Lj = 24/2 =12
4. Calculer la distance entre le nouveau groupe (ij) et tous les
autres groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk /
(ni + nj)
5. Éliminer les colonnes et les lignes correspondant aux

Phoque
groupes i et j et ajouter celles correspondant au nouveau

Otarie
groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon
retourner en 1.
12 12

(ij)
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

1. Trouver les deux UTO i et j pour lesquels la distance dij est la plus
petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij = ni +
nj (ni et nj  nombre d’UTO dans les groupes i et j)
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij). Attribuer aux branches Li et Lj
connectant i à (ij) et j à (ij) la longueur dij /2
4. Calculer la distance entre le nouveau groupe (ij) et tous les autres
groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk / (ni + nj) dphoque-
otarie,chien = nphoque x dphoque,chien / (nphoque + notarie) + notarie x dotarie,chien /
(nphoque + notarie) = (50 + 48)/2 = 49
5. Éliminer les colonnes et les lignes correspondant aux groupes i et j
et ajouter celles correspondant au nouveau groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon retourner
en 1.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Phoque Otarie Chat Singe

Otarie
Chien 0 32 48 51 50 48 98 148

Ours 32 0 26 34 29 33 84 136

Racoon 48 26 0 42 44 44 92 152

Belette 51 34 42 0 44 38 86 142

Phoque 0
Otarie
Phoque 50 29 44 44 0 24 89 142

Otarie 48 33 44 38 24 0 90 142

Chat 98 84 92 86 89 90 0 148

Singe 148 136 152 142 142 142 148 0

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Phoque Otarie Chat Singe

Otarie
Chien 0 32 48 51 (50+48)/2 50 48 98 148
= 49
Ours 32 0 26 34 (29+33)/2 29 33 84 136
= 31
Racoon 48 26 0 42 (44+44)/2 44 44 92 152
= 44
Belette 51 34 42 0 (44+38)/2 44 38 86 142
= 41
Phoque (50+48)/2 (29+33)/2 (44+44)/2 (44+38)/2 0 (89+90)/2 (142+142
Otarie = 49 = 31 = 44 = 41 = 89.5 )/2 = 142

Phoque 50 29 44 44 0 24 89 142

Otarie 48 33 44 38 24 0 90 142

Chat 98 84 92 86 (89+90)/2 89 90 0 148

= 89.5
Singe 148 136 152 142 (142+142 142 142 148 0
)/2 = 142
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

1. Trouver les deux UTO i et j pour lesquels la distance dij est la

plus petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij =
ni + nj (ni et nj  nombre d’UTO dans les groupes i et j)
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij). Attribuer aux branches Li
et Lj connectant i à (ij) et j à (ij) la longueur dij /2
4. Calculer la distance entre le nouveau groupe (ij) et tous les
autres groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk / (ni
+ nj)
5. Éliminer les colonnes et les lignes correspondant aux groupes
i et j et ajouter celles correspondant au nouveau groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon
retourner en 1.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Chat Singe

Otarie
Chien 0 32 48 51 49 98 148

Ours 32 0 26 34 31 84 136

Racoon 48 26 0 42 44 92 152

Belette 51 34 42 0 41 86 142

Phoque 49 31 44 41 0 89.5 142

Otarie
Chat 98 84 92 86 89.5 0 148

Singe 148 136 152 142 142 148 0

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

1. Trouver les deux UTO i et j pour lesquels la distance dij est la

plus petite
2. Créer le nouveau groupe (ij) contenant nij membres avec nij =
ni + nj (ni et nj  nombre d’UTO dans les groupes i et j)
3. Connecter i et j dans l’arbre à un nouveau nœud (ij) qui
correspond au nouveau groupe (ij). Attribuer aux branches Li
et Lj connectant i à (ij) et j à (ij) la longueur dij /2
4. Calculer la distance entre le nouveau groupe (ij) et tous les
autres groupes en utilisant dij,k = ni x dik / (ni + nj) + nj x djk / (ni
+ nj)
5. Éliminer les colonnes et les lignes correspondant aux groupes
i et j et ajouter celles correspondant au nouveau groupe (ij)
6. Si il reste un seul élément dans la matrice, arrêter, sinon
retourner en 1.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Phoque
Racoon

Racoon

Phoque
Otarie

Otarie
Ours

Ours
13 13 12 12 13 13 12 12
5,75 6,75

Deuxième agglomération Troisième agglomération

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Racoon

Phoque

Belette
Otarie
Ours

13 13 12 12 19,75
5,75 6,75
1

Quatrième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Phoque
Racoon

Belette
Otarie

Chien
Ours

13 13 12 12 19,75 22,9
6,75
5,75
1 3,15

Cinquième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Racoon

Phoque

Belette
Otarie

Chien
Ours

Chat
13 13 12 12 19,75 22,9
5,75 6,75
1 3,15 44,9166
22,0166

Sixième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Racoon

Phoque

Belette
Otarie

Chien

Singe
Ours

Chat
13 13 12 12

44,9166
19,75 22,9
5,75 6,75
1 3,15
22,0166 72,1428

27,22619
Septième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Conclusions sur l’UPGMA

 Avantages de l’algorithme:
 Rapidité & simplicité

 Critiques:
 Hypothèse de l’égalité des taux d’évolution entre les lignées.

 Résultats faux si les distances de la matrice n’obéissent pas au critère

d’horloge moléculaire
 N’est presque plus utilisée
 Peut être réaliste si on étudie des espèces très proches

A B C D
A D A 0 17 21 28
B 17 0 12 19 B C D A
B C
C 21 12 0 15 6 6 8,5 11
13 4 4 11
2 2 2,5
D 28 19 15 0 2,5
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le neighbor-joining (NJ)
 Développé par Saitou et Nei (1987) est une approximation de l’algorithme
pour trouver l’arbre le plus court (minimum évolution)
 Avantages
 Rapidité => permet de travailler avec un très grand nombre de taxons
(plusieurs centaines)
 Bonne approximation de la méthode du minimum d’évolution

 Retrouve l’arbre vrai si la matrice de distances est un reflet exact d’un

arbre
 Conditions d’application
 Les taux d’évolution ne sont pas les mêmes dans toutes les lignées

 Caractéristiques des arbres obtenus

 Ils sont non racinés
 Principe:
 A chaque étape, rechercher le couple d’UTO qui minimise la longueur
totale de l’arbre
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le neighbor-joining – Principe
 Point de départ = topologie en étoile
 Étape 1 : Pour toutes les paires i,j possibles, calculer Si,j la longueur de
l’arbre obtenu
 Étape 2 : Retenir la paire i,j générant la plus petite valeur Si,j ; grouper i et j
dans l’arbre
 Étape 3 : Calculer les nouvelles distances d entre le groupe nouvellement

formé et les séquences restantes

 Étape 4 : Retourner à l’étape 1 si il reste plus de 4 séquences/groupes à
assembler
2 3 2 3
L2B L2A
L3B L3B
L1B L1A LAB
1 B 4 1 A B 4
L4B L4B
L6B L6B
L5B L5B

6 5 6 5
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le neighbor-joining – Algorithme simplifié

(Studier et Keppler 1988)
(1) Pour chaque feuille i calculer ui = Ri / (m-2) = mk=1 dik / (m-2)
(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau nœud
A et Lj la longueur de la branche reliant j au nouveau nœud A comme étant
 Li = dij/2 + (ui-uj)/2
 Lj = dij/2 + (uj-ui)/2
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille comme
 d(ij),k = (dik + djk – dij ) /2
(5) Éliminer les colonnes et les lignes correspondant aux groupes i et j et ajouter
celles correspondant au nouveau groupe (ij)
(6) Si il reste un seul élément dans la matrice connecter les deux derniers nœuds,
sinon retourner en 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Le neighbor-joining – Application

(1) Pour chaque feuille i calculer ui = Ri / (m-2) = mk=1 dik /(m-2)

(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau nœud
A et Lj la longueur de la branche reliant j au nouveau nœud A comme étant
 Li = dij/2 + (ui-uj)/2
 Lj = dij/2 + (uj-ui)/2
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille comme
 d(ij),k = (dik + djk – dij ) /2
(5) Éliminer les colonnes et les lignes correspondant aux groupes i et j et ajouter
celles correspondant au nouveau groupe (ij)
(6) Si il reste un seul élément dans la matrice connecter les deux derniers nœuds,
sinon retourner en 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0

Ours 32 0

Racoon 48 26 0

Belette 51 34 42 0

Phoque 50 29 44 44 0

Otarie 48 33 44 38 24 0

Chat 98 84 92 86 89 90 0

Singe 148 136 152 142 142 142 148 0

ui 79,167 62,333 74,667 72,833 70,333 69,833 114,5 168,333

ui = mk=1:ki dik / (m-2)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

(1) Pour chaque feuille i calculer ui = Ri / (m-2) = mk=1 dik / (m-2)

(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau
nœud A et Lj la longueur de la branche reliant j au nouveau nœud A comme
étant
 Li = dij/2 + (ui-uj)/2
 Lj = dij/2 + (uj-ui)/2
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille
comme
 d(ij),k = (dik + djk – dij ) /2
(5) Éliminer les colonnes et les lignes correspondant aux groupes i et j et
ajouter celles correspondant au nouveau groupe (ij)
(6) Si il reste un seul élément dans la matrice connecter les deux derniers
nœuds, sinon retourner en 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0 -109,5 -105,834 -101 -99,5 -101 -95.667 -99,5

Ours 32 0 -111 -101,166 -103,666 -99,166 -92,833 -94,666

Racoon 48 26 0 -105,5 -101 -100,5 -97,167 -91

Belette 51 34 42 0 -99,166 -104,666 -101,333 -99,166

Phoque 50 29 44 44 0 -116,166 -95.833 -96,666

Otarie 48 33 44 38 24 0 -94,333 -96,166

Chat 98 84 92 86 89 90 0 -134,833

Singe 148 136 152 142 142 142 148 0

ui 79,167 62,333 74,667 72,833 70,333 69,833 114,5 168,333

Dij – ui – uj exemple Ours/Chien : 32-79,167-62,333 = -109,5

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

(1) Pour chaque feuille i calculer ui = Ri / (m-2) = nk=1 dik mk=1 dik / (m-2)
(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau nœud
A et Lj la longueur de la branche reliant j au nouveau nœud A comme étant
 Li = dij/2 + (ui-uj)/2 = 148/2 + (114,5 – 168,3333)/2 = 47,0835
 Lj = dij/2 + (uj-ui)/2 = 148/2 + (168,3333 – 114,5)/2 = 100,9165
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille comme
 d(ij),k = (dik + djk – dij ) /2

100,9165

A
47,0835
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

(1) Pour chaque feuille i calculer ui = Ri / (m-2) = nk=1 dik /mk=1 dik / (m-2)
(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau nœud
A et Lj la longueur de la branche reliant j au nouveau nœud A comme étant
 Li = dij/2 + (ui-uj)/2
 Lj = dij/2 + (uj-ui)/2
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille comme
 d(ij),k = (dik + djk – dij ) /2
(5) Éliminer les colonnes et les lignes correspondant aux groupes i et j et ajouter
celles correspondant au nouveau groupe (ij)
(6) Si il reste un seul élément dans la matrice connecter les deux derniers
nœuds, sinon retourner en 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0

Ours 32 0

Racoon 48 26 0

Belette 51 34 42 0

Phoque 50 29 44 44 0

Otarie 48 33 44 38 24 0

Chat (98+148- (84+136- (92+152- (86+142- (89+142- (90+142-

148)/2 = 148)/2= 148)/2= 148)/2= 148)/2= 148)/2=42
Singe
49 36 48 40 41,5
Chat 98 84 92 86 89 90 0

Singe 148 136 152 142 142 142 148 0

D(ij),k = (Dik + Djk – Dij ) /2

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

(1) Pour chaque feuille i calculer ui = Ri / (m-2) = mk=1 dik

(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau nœud
A et Lj la longueur de la branche reliant j au nouveau nœud A comme étant
 Li = dij/2 + (ui-uj)/2
 Lj = dij/2 + (uj-ui)/2
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille comme
 d(ij),k = (dik + djk – dij ) /2
(5) Éliminer les colonnes et les lignes correspondant aux groupes i et j et ajouter
celles correspondant au nouveau groupe (ij)
(6) Si il reste un seul élément dans la matrice connecter les deux derniers nœuds,
sinon retourner en 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Otarie Chat Singe

Chien 0

Ours 32 0

Racoon 48 26 0

Belette 51 34 42 0

Phoque 50 29 44 44 0

Otarie 48 33 44 38 24 0

Chat 49 36 48 40 41,5 42
Singe
Chat 98 84 92 86 89 90 0

Singe 148 136 152 142 142 142 148 0

Supprimer les colonnes du chat et du singe

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Chien Ours Racoon Belette Phoque Otarie Chat

Singe
Chien 0

Ours 32 0

Racoon 48 26 0

Belette 51 34 42 0

Phoque 50 29 44 44 0

Otarie 48 33 44 38 24 0

Chat 49 36 48 40 41,5 42 0
Singe
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

(1) Pour chaque feuille i calculer ui = Ri / (m-2) = mk=1 dik

(2) Choisir et i et j pour lesquels dij – ui – uj est la plus petite
(3) Joindre i et j. Calculer Li la longueur de la branche reliant i au nouveau nœud
A et Lj la longueur de la branche reliant j au nouveau nœud A comme étant
 Li = dij/2 + (ui-uj)/2
 Lj = dij/2 + (uj-ui)/2
(4) Calculer la distance entre le nouveau nœud A et chaque autre feuille comme
 d(ij),k = (dik + djk – dij ) /2
(5) Éliminer les colonnes et les lignes correspondant aux groupes i et j et ajouter
celles correspondant au nouveau groupe (ij)
(6) Si il reste un seul élément dans la matrice connecter les deux derniers
nœuds, sinon retourner en 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

100,9165

47,0835

100,9165

12,35 11,65 47,0835

Deuxième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

100,9165

12,35 11,65 47,0835

6,875 100,9165

19,125
12,35 11,65 47,0835

Troisième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

6,875 100,9165

19,125
12,35 11,65 47,0835

6,875
1,75
19,125 100,9165

25,25
12,35 11,65 47,0835

Quatrième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

6,875
1,75
19,125 100,9165

25,25
12,35 11,65 47,0835

6,875
1,75
19,125
3,5
25,25 100,9165

12,35
47,0835
11,65 7,8125

Cinquième agglomération
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

6,875
1,75
19,125
3,5
25,25 100,9165

12,35
47,0835
11,65 7,8125

6,875
1,75
19,125
3,4375
19,5625
25,25
Sixième 100,9165
12,35
agglomération 20,44
7,8125
11,65 47,0835
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Comparaison UPGMA - NJ
12 11,65
5,75 Otarie Otarie 7,8125
12 Phoque
12,35
Phoque
1 1,5625
25,25
UPGMA 13 Chien NJ
Racoon
3,15 13 19,125
Ours Racoon 3,4375
6,75 20,44
22,0166 6,875 1,75
19,75 Ours
Belette

27,226190 22,9 Chien 19,5625

Belette

44,9166 47,0835
Chat Chat 100,9165

72,1428
Singe Singe
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Maximum de Parcimonie
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

La parcimonie

 Fondement: rasoir d’Occam

 « Les multiples ne doivent pas être utilisés sans nécessité. »

(pluralitas non est ponenda sine necessitate) ou sous une forme

plus moderne « les hypothèses les plus simples sont les plus
vraisemblables »
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Le critère de parcimonie
 Soit un caractère relevé dans 4 espèces {A,B,C,D} (dont on connaît
la phylogénie) et présentant les états de caractères x , x , y , y 

 Quelle histoire a pu conduire à cet état final?

B A C D
x  x  y y

x 
y
y
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Le critère de parcimonie
 Soit un caractère relevé dans 4 espèces {A,B,C,D} (dont on connaît
la phylogénie) et présentant les états de caractères x , x , y , y 
Substitution y => x
 Quelle histoire a pu conduire à cet état final? Substitution x => y

B A C D
x  x  y y

x 
y
y
NC = 1

Similarité par
ascendance commune
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Le critère de parcimonie
 Soit un caractère relevé dans 4 espèces {A,B,C,D} (dont on connaît
la phylogénie) et présentant les états de caractères x , x , y , y 
Substitution y => x
 Quelle histoire a pu conduire à cet état final? Substitution x => y

B A C D B A C D B A C D
x  x  y y x  x  y y x  x  y y

x  y x 
y y x 
y y y
NC = 1 NC = 2 NC = 2

Similarité par Similarité par Similarité par

ascendance commune convergence réversion
Les scénarios homoplasiques demandent plus de changements évolutifs. L’emploi du critère de
parcimonie en phylogénie moléculaire n’est justifié que si les convergences et les réversions sont rares.
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Maximum de parcimonie - Généralités

 Identifier la topologie T qui implique le plus petit nombre de

changements évolutifs suffisant pour rendre compte des
différences observées entre les séquences étudiées.
 L’arbre le plus parcimonieux  plus court chemin conduisant
aux états de caractères observés

 Caractéristique des arbres obtenus

 Solutions multiples => plusieurs arbres impliquant un même
nombre minimal de changements peuvent être obtenus
 Ne possèdent pas de longueur de branche

 Arbres non racinés

 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Le maximum de parcimonie

 Principe: rechercher parmi l’espace des arbres définissant les liens

entre n séquences la topologie qui minimise le nombre de
changements évolutifs
 Quelle est la topologie qui implique le moins de changements d’état
de caractères pour rendre compte des différences observées entre
les UTO étudiées
 Procédure:
 1) pour une topologie T fixée et pour un site donné de l’alignement,
calculer (NC) le nombre de changements évolutifs nécessaires pour
expliquer les états de caractères observés
 2) calculer (NC) pour chaque site de l’alignement => L , la longueur de
l’arbre
 3) calculer L pour toutes les topologies T possibles => retenir l’arbre
le plus parcimonieux (cad l’arbre le plus court)
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Parcimonie: Etape 1

 Pour une topologie T fixée et pour un site

donné de l’alignement, calculer (NC) le
nombre de changements évolutifs
nécessaires pour expliquer les états de
caractères observés
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Algorithme de Fitch: calcul du nombre

minimal de changements évolutifs
 Soit une topologie T fixée et racinée de manière arbitraire, soit V
l’ensemble de ses nœuds
 Pour tout p  V on définit:

 C p , le nombre minimal de changements dans le sous-arbre dont

p est la racine
 S p , l’état de p , cad l’ensemble des résidus en p compatibles
avec C p changements évolutifs dans le sous-arbre raciné par p .
 Soit q et r les deux nœuds fils de p
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Algorithme de Fitch: Application

Initialisation du calcul récursif aux
feuilles de l’arbre
-P = {x} = résidu présent à cette feuille
-Cp = 0

La racine est placée de manière

arbitraire et n’a aucune influence
sur le nombre de changements
évolutifs inférés

Les états de caractères inférés

aux nœuds ne représentent pas
des caractères ancestraux, ni tous
les états de caractères possibles !

NC = 4
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Des scénarios multiples

Il existe plusieurs scénarios

impliquant NC = 4
changements évolutifs

{T} {A}
T->A {A}
{T}

A->T
{T} {A}
A->G

T->C {T} T->G {T} T->A T->C {T} G->T

1 2 3 4 5 6 1 2 3 4 5 6
{C} {T} {G} {T} {A} {A} {C} {T} {G} {T} {A} {A}
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Parcimonie: Etapes 2 et 3

 Etape 2:
 Calculer NC pour chaque site de l’alignement
 Sommer tous les valeurs de NC pour l’ensemble des sites
 Calculer L , la longueur totale de l’arbre
 Etape 3:
 Répéter l’étape 2 pour chaque topologie T composant
l’espace des arbres possibles à n feuilles
 Retenir l’arbre de longueur L minimale  arbre le plus
parcimonieux
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Tous les sites ne sont pas équivalents

 Tous les sites ne contiennent pas une information

permettant de discriminer les topologies
 Les sites constants (1 seul état de caractère)
 Ne sont pas informatifs
 Sites variables (au moins 2 états de caractères)
 Informatifs: présentent au moins deux états de caractères
chacun partagés par au moins deux séquences
 Non informatifs: tous les autres
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Tous les sites ne sont pas équivalents

 Soit A, B, C et D quatre séquences

d’ADN homologues alignées
 Il existe 3 topologies non racinées
possibles
 Il existe 4 états de caractères
{A,T,C,G}
 Il existe 44 = 256 motifs différents
observables à une position
 Seuls 36 sont informatifs, et sont
tous du type {x,x,y,y}, {x,y,x,y} ou
{x,y,y,x} (avec x ≠ y et x,y E
{A,T,C,G})
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Parcimonie: Récapitulatif & propriétés

 Produit des arbres non racinés

 Le positionnement des changements dans un arbre n’est pas unique
 ne permet pas d’inférer des longueurs de branches de manière unique
 Plusieurs arbres équiparcimonieux peuvent être trouvés
 Inférence de consensus
 Le nombre d’arbre croissant de manière rapide avec le nombre de
séquences, seul un sous-ensemble des topologies est testé pour identifier
l’arbre le plus parcimonieux
 Utilisation d’heuristiques pour explorer l’espace des arbres de manière rationnelle
 Aucune certitude d’identifier l’arbre le plus parcimonieux à la fin de l’analyse
 Absence de critères pour discriminer le(les) arbre(s) le(s) plus parcimonieux
des arbres légèrement moins parcimonieux
 ex. est-ce qu’un arbre comptant 2504 pas est significativement meilleur que les
20 arbres comptant 2506 pas ?
 La parcimonie classique (algorithme de Fitch) considère toutes les
substitutions comme équivalentes
 Parcimonie pondérée (algorithme de Sankoff) permet de pondérer les types de
changements

Pour approfondir ces notions: Concepts et méthodes en phylogénie moléculaire (2010) Perrière &
Brochier-Armanet (Springer)
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Consensus d’arbres

F E D C B A F E D C B A F E D C B A

D E F C B A
F E D C B A F E D C B A

Strict Maj. 50% Maj. 80%

(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)

 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Explorer l’espace des topologies

 n < 12: Exploration exhaustive

 n < 20: branch-and-bound
 n > 20: heuristiques

 Utilisé pour la parcimonie, mais aussi les moindres carrés, le

maximum de vraisemblance, etc.

 Topologie de départ?
 Topologie aléatoire
 Meilleure topologie issue d’une recherche séquentielle
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Recherche séquentielle

 Arbre à 3 feuilles
 Choix du 4ième taxon à ajouter
 ordre des taxa dans

l’alignement
 aléatoirement

 maximum du minimum

(taxon qui induit un Lmax

minimal)

L max  9
(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)
 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Branch-and-bound

L max  8

Examen de 10/15
topologies
L max  9 possibles
=> Gain de 1/3

(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)

 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Nearest Neighbor Interchange (NNI)

 Examen des topolgies se

situant à une distance
topologique d T  2 de l’arbre
de départ
 2 ( n  3 ) arbres situés à une Complexité en O(n)
distance topologie d T  2
C B A
A D A D C D

B E C E B E
C D E
A D A C A D

B E B E B C

(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)

 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Subtree pruning and regrafting (SPR)

1 2

E A D E B C

F B F A
A 1 D E
G C G D
2
B F 3 4
4 A
C 3 G E C B E
Zone Zone D
F A F
résiduelle élaguée B
G D G C

Si coupure au niveau d’une branche interne: (2n - 8) arbres voisins

Si coupure au niveau d’une branche externe: (2n - 6) arbres voisins
Un arbre non raciné compte: (n – 3) branches internes et n branches externes
nx ( 2 n  6 )  ( n  3 )( 2 n  8 )
 Nombre de voisins explorables:
 4 ( n  3 )( n  2 ) Complexité en O(n2)

(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)

 Evolution moléculaire et phylogénie (Céline Brochier-Armanet 2015-2016)

Tree Bisection and Reconnection (TBR)

B D C D A E B E
1 2 3 4
A E B E B D A D

C F A F C F C F

C E A F B F C F
5 6 7 8
B D B D A D A D

A F C E C E B E

( 2 n  3 )( n  3 )² Réarrangements maximum possibles

A D

B E

C F
Complexité en O(n3)

(Perrière & Brochier-Armanet, (2010) Concepts et méthodes en phylogénie moléculaire, Springer)

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Star decomposition

([Link]
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Maximum de vraisemblance
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Généralité

 Introduit par Edwards et Cavalli-Sforza (1964) pour l’étude de données

de type fréquences de gènes
 Appliquée à la phylogénie moléculaire par Neyman (1971)
 Élargissement par Kashyap et Subas (1974) et Felsenstein (1981)
 IDEE DE BASE
 Étant donné un modèle d’évolution, on peut estimer une
phylogénie avec des méthodes statistiques comme le maximum
de vraisemblance

 PROPRIETES des estimations par Maximum de vraisemblance

 Bonne consistance  convergent vers la valeur correcte du
paramètre
 Bonne efficience  variance faible autour de la vraie valeur du
paramètre
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Principe général

 Basé sur des lois de probabilité conditionnelles

 La vraisemblance de l’hypothèse H connaissant les données D est
définie par:

 L  P(D H )  probabilité d’observer les données D sous

l’hypothèse H

  L  P ( H D ) : probabilité de l’hypothèse H sachant les

données

 Si on dispose de n observations indépendantes

L  P(D H )  P(D H )  P(D H )  ...  P ( D

(1 ) (2) (3) (n)
 H)
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Un exemple simple

 Estimation de la probabilité p d’obtenir face d’une pièce lancée 11

fois
 Hypothèses :
 Indépendance des lancés

 Tous les lancés on la même probabilité p (inconnue) d’obtenir

face

 Données : L  P ( D p )
 Résultats observés : FFPPFPFFPPP

 Définition de la fonction de vraisemblance

 Soit
L  P ( D p )  p  p  (1  p )  (1  p )  p  (1  p )  p  p  (1  p )  (1  p )  (1  p )

 p  (1  p )
5 6
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Un exemple simple
 On cherche ensuite quelle est la valeur de p (parmi toutes les
valeurs possibles) qui maximise la probabilité d’obtenir les données
D, cad les résultats des lancers observés
L  P ( D p )  p  p  (1  p )  (1  p )  p  (1  p )  p  p  (1  p )  (1  p )  (1  p )

 p  (1  p )
5 6 L =f(p)
L
L

0,454
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1
p
p
La vraisemblance est maximale pour p = 0,454
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Application aux phylogénies moléculaires

 HYPOTHESES
 Le processus de substitution suit un modèle probabiliste dont
l’expression mathématique est connue a priori, mais dont les
paramètres ne sont pas connus (modèle connu mais
paramètres inconnus => calcul des probabilité de passage
d’un état i à un état j le long d’une branche de longueur t)
 Les sites évoluent indépendamment les uns des autres
 Les probabilités de substitution ne changent pas au cours du
temps
 Tous les sites obéissent au même processus de substitution
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Définition de la vraisemblance
 Données
 Séquences d’ADN lignées (n sites)
 Modèle d’évolution M (JK, K2P, HKY…)

 Hypothèses
 Paramètres du modèle  , topologie T , longueurs de
branches 
La vraisemblance est
calculée de manière
 Décomposition de la vraisemblance indépendante à
 L  P(D H )  P(D H ) chaque site
L  P(D H )  P(D H )  ...  P ( D
(1 ) (2) (n)
H)
n

L   i 1 P ( D
(i)
H) 
  i 1
n
P ( D (i)
T , , ) 
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Application

Sites

Séquences 1 2 3 4 5 6 7 8 n

A A A G A G T T C N

B A G C C G T T C N

C A G A T A T C C N

D A G A G A T C C N
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Application
 Modèle d’évolution M
 Topologie ((A,B),(C,D)), Longueurs de branches
 Y et Z = nœuds internes pour lesquels 4 états de caractères
sont possibles (A,T,C,G)
 Question = Quelle est la probabilité que l’arbre aie généré les
données de la matrice suivant le modèle M ?

Sites
Séq. 1 2 3 4 5 6 7 8 n A l1 C
A A A G A G T T C N l5
l5 l3
B A G C C G T T C N
Y Z
C A G A T A T C C N l4 D
D A G A G A T C C N
B l2
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Application
 Question = Quelle est la probabilité que l’arbre ait généré les
données de la matrice suivant le modèle M ?

 Évolution indépendante des sites => On calcule indépendamment

la vraisemblance L à chacun des sites

 On combine les vraisemblances à la fin de l’analyse

Sites
Séq. 1 2 3 4 5 6 7 8 n A l1 C
A A A G A G T T C N l5
l5 l3
B A G C C G T T C N
Y Z
C A G A T A T C C N l4 D
D A G A G A T C C N
B l2
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Exemple = calcul de la vraisemblance au

site 5
 La probabilité d’observer ces états de caractères à ce site
dépendent des états de caractères qui étaient présents en Y et Z,
càd aux nœuds ancestraux
 Les états de caractères ancestraux sont inconnus, mais… à l’aide
d’un modèle d’évolution il est possible de déterminer la probabilité
d’observer l’état un état de caractère au bout d’une branche de
longueur l
 On calcule la probabilité d’observer les états de caractères à
chaque site, pour tous les états possibles observables en Y et Z
Sites
G A C A
Séq. 1 2 3 4 5 6 7 8 n l1
A A A G A G T T C N l5
l5 l3
B A G C C G T T C N
Y Z
C A G A T A T C C N l4 D
D A G A G A T C C N
G B l2 A
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Exemple = calcul de la vraisemblance au

site 5
G A C A
l1
l5
l5 l3
A A
G B l2 l4 D A

 Probabilité de ce scénario

P ( scenario )  P (Y  A )  P ( Z  A Y , l 5 )  P ( A  G Y , l1 )  P ( B  G Y , l 2 ) 

P (C  A Z , l3 )  P ( D  A Z , l 4 )

=> On évalue tous les scénarios possibles

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Vraisemblance de chacun des scénarios

A A T A C A G A

A T T T C T G T

A C T C C C G C

A G T G C G G G

L(5) = somme de la probabilité de chaque scénario

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Calcul de la vraisemblance d’un arbre

 L(5) = somme des probabilités individuelles de chaque scénario

 Vraisemblance de l’arbre

L  L L  ...  L
(1 ) (2) (n)

L  
(i)
L
i 1

L  ln L  ln L  ...  ln L
(1 ) (2) (n)

L  
(i)
ln L
i 1
 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Maximisation de la vraisemblance
(1) On considère une topologie T , un site et un ensemble de
longueurs de branches l

(2) On calcule la vraisemblance des paramètres = probabilité

d’observer les états de caractères au site en fonction des
paramètres (T ,  , l )

(3) On fait le calcul pour tous les caractères

(4) On calcule les longueurs de branches l et les paramètres 

du modèle qui maximisent la vraisemblance

(5) On calcule la vraisemblance pour toutes les topologies possibles

(6) On retient la topologie qui a la plus grande grande vraisemblance

 Introduction à la phylogénie (Céline Brochier-Armanet 2015-2016)

Propriétés du maximum de vraisemblance

 C’est une des méthodes les plus justifiées d’un point de vue théorique

 Les simulations montrent que cette méthode est supérieure aux autres dans
beaucoup de cas. En particulier elle est moins sensible aux artefacts
d’attraction des longues branches

 Coûteuse en temps de calcul

 Impossible d’évaluer tous les arbres  utilisation d’heuristiques  n’est

plus certain d’obtenir l’arbre le plus vraisemblable

 Des tests statistiques dérivés du maximum de vraisemblance permettent

d’évaluer si des topologies ayant une vraisemblance moins bonne que la
topologie la plus vraisemblable sont significativement différentes