L'algorithme "Neighbor Joining" (NJ)

Saitou & Nei, 1986

Les problèmes résolus par la méthode NJ:

• UPGMA ne fonctionne pas lorsque les vitesses d'évolution varient d'une branche à l'autre. Prenons par exemple la matrice suivante:

  	A	B	C	D	E
  B	5
  C	4	7
  D	7	10	7
  E	6	9	6	5
  F	8	11	8	9	8

  
  UPGMA placerait A avec C plutot qu'avec B. Or, B est plus proche de A que de toute autre séquence. Explication: comme il a évolué rapidement, B se trouve plus éloigné de A que C de A. Pourtant, c'est l'arbre suivant qui devrait être produit:
  
• NJ regroupe les espèces en fonction de leur distance avec l'ensemble des autres espèces, et non pas de leur distance entre elles. Ce faisant, NJ minimise aussi la longueur totale des branches.
• Dans l'arbre UPGMA, les distances ne sont pas additives. Avec NJ, dij est proportionnel à la longueur totale des branches connectant i et j.

Algorithme

Etape 1: On appelle OTU (Operational Taxonomic Unit) une feuille ou un noeud de l'arbre. Au début, les OTU sont les espèces. On calcule la divergence nette r(i) de chaque OTU avec toutes les autres

r(A) =  5+4+7+6+8=30
r(B) = 42
r(C) = 32
r(D) = 38
r(E) = 34
r(F) = 44

Etape 2: On calcule une nouvelle matrice de distance qui va donner pour chaque paire d'OTU la distance moyenne de cette paire avec tous les autres OTUs. Formule:

M(ij)=d(ij) - [r(i) + r(j)]/(N-2) soit pour la paire A,B:

M(AB)=d(AB) -[(r(A) + r(B)]/(N-2) = -13

On crée maintenant un arbre en étoile:

      A
F    |    B
  \  |  /
   \ | /
    \|/
    /|\
   / | \
  /  |  \
E    |    C
      D

Etape 3: On choisit comme voisins les 2 OTU pour lesquels Mij est le plus petit. Ce sont A et B; ou D et E. Prenons A et B et créons un nouveau noeud appelé U. On calcule ensuite les longueurs des branches entre le noeud interne U et les OTU A et B.

d(AU) =d(AB) / 2 + [r(A)-r(B)] / 2(N-2) = 1 
d(BU) =d(AB) -d(AU) = 4

Puis les distance entre U et tous les autres noeud terminaux:

d(CU) = d(AC) + d(BC) - d(AB) / 2 = 3 
d(DU) = d(AD) + d(BD) - d(AB) / 2 = 6 
d(EU) = d(AE) + d(BE) - d(AB) / 2 = 5 
d(FU) = d(AF) + d(BF) - d(AB) / 2 = 7

Ce qui crée la matrice:

Il en résulte l'arbre:

                            C
                         D  |  
                          \ |     A
                           \|___/ 1
                           /|   \
                          / |    \ 4
                         E  |     \
                            F      \
                                     B

N= N-1 = 5
Puis on reprend à l'Etape 1