© Dunod – Toute reproduction non autorisée est un délit.
87
7.2 • Méthodes de distances
Voyons maintenant comment les longueurs des branches terminales et internes de
l’arbre sont calculées. Avec les notations de l’arbre de la figure 7.7, considérons les
quantités :
La méthode Neighbor-Joining affecte la valeur :
·
à la longueur de la branche terminale i  X
L
. Pourquoi cette formule pour iX ? Assimilons dans l’arbre de la figure 7.7 toutes les feuilles k x à une seule feuille k, pour
obtenir un arbre à trois feuilles, i, j et k, et un nœud interne, X. Alors d i (respectivement d j ) peut être vue comme la distance entre i (respectivement ) et
j
k. Il est facile
(puisqu’on a un arbre à trois branches seulement) de vérifier que cette valeur de L iX
minimise (et même annule) la somme des carrés des différences entre distances
mesurées sur les séquences (d i , d j et d(i,j)) et distances induites par l’arbre (L iX + L Xk ,
L jX + L Xk et L iX + L jX , respectivement).
La méthode Neighbor-Joining crée une branche interne quand elle groupe deux
objets dont l’un au moins est un groupe construit auparavant (figure 7.9). Ceci se
produit en bas de l’exemple de la figure 7.8, quand la feuille 2 est groupée avec
(6,4). La méthode attribue la longueur
à la branche interne
(figure 7.9). Ici, L
X  Y
(ij)Y est calculée avec la formule
donnant la longueur des branches terminales.
Figure 7.7 – Formes d’arbres traitées par la méthode Neighbor-Joining.
Dans ces arbres, toutes les feuilles (k 1 ,…) sauf deux (i et ) convergent en un
j
même nœud, tandis que les feuilles i et j convergent d’abord au nœud X avant de
rejoindre le nœud central.
d u
1
n 2
–
----------- -
d u k



k i
 k j



avec u i
= ou u j
= .
=
L iX
d i j

  d i d j
–
+
2
----------------------------------=
L XY
L ij
  Y
d i j

 
2
------------- -
–
=