Chapitre 7 • Algorithmes pour la phylogénie moléculaire
86
7.2.1 Méthode d’évolution minimale
Pour une topologie d’arbre donnée à n feuilles, et pour des longueurs des branches
de cet arbre données, on peut mesurer l’écart entre les distances induites par
l’arbre et les distances d
n
mesurées entre les séquences par :
Il est possible de calculer informatiquement les longueurs optimales des branches,
celles qui minimisent l’écart .
La méthode d’évolution minimale consiste à transposer au contexte des distances
évolutives le principe de parcimonie selon lequel l’arbre préféré est celui qui
requière le nombre minimal d’événements évolutifs. La notion utilisée en parcimonie de coût total d’un arbre correspond ici à la notion de somme des longueurs des
branches d’un arbre, puisque chaque longueur de branche représente la quantité
d’évolution qui s’est produite entre ses extrémités. Ainsi, la méthode d’évolution
minimale consiste en ces opérations :
• pour chaque topologie d’arbre,
calculer les longueurs de branches optimales ;
calculer la longueur de l’arbre égale à la somme des longueurs de ses branches ;
• retourner l’arbre de longueur minimale (et ses longueurs de branches optimales).
7.2.2 Méthode Neighbor-Joining
La méthode d’évolution minimale effectue des calculs pour toutes les topologies
d’arbre possibles, ce qui interdit, on l’a vu, de traiter des arbres avec un grand
nombre de feuilles en un temps raisonna
hbor-Joining propose
ble. La méthode Neig
une approximation très efficace de la méthode d’évolution minimale, suffisamment
sobre en calculs pour permettre d’analyser des centaines de séquences. L’idée
centrale est de ne considérer que certaines topologies d’arbres très particulières, et
de leur appliquer la méthode d’évolution minimale.
Saitou et Nei, les auteurs de cette méthode, ont découvert comment calculer très
efficacement la somme des longueurs optimales des branches des arbres de la forme
présentée à la figure 7.7. L’algorithme Neighbor-Joining se déroule ainsi :
1. Travailler avec les distances
séquences.
d mesurées entre les n
2. Pour toute paire i,j, considérer la topologie de la figure 7.7 et calculer S ij la
somme des longueurs optimales de ses branches.
3. Retenir la paire pour laquelle S
i,j
ij est minimale. Grouper les feuilles i et j dans l’arbre.
4. On obtient alors –1 objets : la paire ( ) et les
n
i,j
n–2 autres séquences. Calculer de
nouvelles distances entre eux: d((i,j),k ) = (d(i,k) + d(j,k))/2.
5. Retourner à l’étape 2 tant qu’il y a quatre objets ou plus.
Cet algorithme construit donc progressivement un arbre de distance par agglomérations successives de paires de feuilles en partant d’un arbre complètement irrésolu,
comme illustré par la figure 7.8.
d x y
x y
–
2
1 x y
n
=
86
7.2.1 Méthode d’évolution minimale
Pour une topologie d’arbre donnée à n feuilles, et pour des longueurs des branches
de cet arbre données, on peut mesurer l’écart entre les distances induites par
l’arbre et les distances d
n
mesurées entre les séquences par :
Il est possible de calculer informatiquement les longueurs optimales des branches,
celles qui minimisent l’écart .
La méthode d’évolution minimale consiste à transposer au contexte des distances
évolutives le principe de parcimonie selon lequel l’arbre préféré est celui qui
requière le nombre minimal d’événements évolutifs. La notion utilisée en parcimonie de coût total d’un arbre correspond ici à la notion de somme des longueurs des
branches d’un arbre, puisque chaque longueur de branche représente la quantité
d’évolution qui s’est produite entre ses extrémités. Ainsi, la méthode d’évolution
minimale consiste en ces opérations :
• pour chaque topologie d’arbre,
calculer les longueurs de branches optimales ;
calculer la longueur de l’arbre égale à la somme des longueurs de ses branches ;
• retourner l’arbre de longueur minimale (et ses longueurs de branches optimales).
7.2.2 Méthode Neighbor-Joining
La méthode d’évolution minimale effectue des calculs pour toutes les topologies
d’arbre possibles, ce qui interdit, on l’a vu, de traiter des arbres avec un grand
nombre de feuilles en un temps raisonna
hbor-Joining propose
ble. La méthode Neig
une approximation très efficace de la méthode d’évolution minimale, suffisamment
sobre en calculs pour permettre d’analyser des centaines de séquences. L’idée
centrale est de ne considérer que certaines topologies d’arbres très particulières, et
de leur appliquer la méthode d’évolution minimale.
Saitou et Nei, les auteurs de cette méthode, ont découvert comment calculer très
efficacement la somme des longueurs optimales des branches des arbres de la forme
présentée à la figure 7.7. L’algorithme Neighbor-Joining se déroule ainsi :
1. Travailler avec les distances
séquences.
d mesurées entre les n
2. Pour toute paire i,j, considérer la topologie de la figure 7.7 et calculer S ij la
somme des longueurs optimales de ses branches.
3. Retenir la paire pour laquelle S
i,j
ij est minimale. Grouper les feuilles i et j dans l’arbre.
4. On obtient alors –1 objets : la paire ( ) et les
n
i,j
n–2 autres séquences. Calculer de
nouvelles distances entre eux: d((i,j),k ) = (d(i,k) + d(j,k))/2.
5. Retourner à l’étape 2 tant qu’il y a quatre objets ou plus.
Cet algorithme construit donc progressivement un arbre de distance par agglomérations successives de paires de feuilles en partant d’un arbre complètement irrésolu,
comme illustré par la figure 7.8.
d x y
x y
–
2
1 x y
n
=