Neighbor-Joining et bootstrap

Prérequis

Cette section suppose que vous savez lire un alignement multiple et calculer une distance évolutive corrigée : matrice symétrique, diagonale nulle, distances en substitutions par site. Les enregistrements et les arbres se manipulent avec l'API de Biopython présentée en 1.3 ; les matrices de substitution de 2.5 ne servent pas ici, car Neighbor-Joining travaille sur des distances. Le vocabulaire des arbres — feuille, nœud interne, branche, bipartition, clade — est supposé connu ; le module 5 en donne le cadre.

Introduction

Reconstruire l'histoire évolutive d'un groupe commence souvent par une question très concrète : deux séquences sont-elles plus proches entre elles qu'avec une troisième, et cette proximité reflète-t-elle une divergence récente ou une simple ressemblance fortuite ? Un alignement multiple fournit des colonnes comparables, à partir desquelles on résume chaque paire de séquences par une distance. Cette réduction est commode, mais elle jette l'ordre des sites et la qualité de chaque colonne. Le problème computationnel consiste alors à reconstruire un arbre à partir d'une matrice de distances, en sachant que le nombre d'arbres binaires non enracinés croît comme $(2n-5)!!$ et qu'une recherche exhaustive devient vite impossible.

Neighbor-Joining (NJ), publié par Saitou et Nei en 1987, est une heuristique polynomiale qui construit l'arbre par fusions successives. À chaque étape, elle choisit la paire de taxons qui minimise un critère fondé sur les distances, la réunit en un nœud interne, puis met à jour la matrice. L'algorithme ne suppose pas d'horloge moléculaire et renvoie un arbre non enraciné. Sa rapidité et sa robustesse relative en ont fait un outil de premier défaut, encore utilisé pour produire des arbres guides, des arbres de départ ou des analyses exploratoires sur des milliers de taxons.

Un arbre sans mesure de confiance est une hypothèse fragile. Le bootstrap, introduit par Felsenstein en 1985, évalue la stabilité d'un clade en rééchantillonnant les colonnes de l'alignement. Il ne dit pas si l'arbre est vrai ; il dit si les données, réanalysées avec les mêmes choix, conduisent souvent à la même bipartition. Nous allons construire NJ à la main, l'implémenter, puis lire un support sans confondre fréquence de rééchantillonnage, probabilité et vérité biologique.

Théorie

Des colonnes d'alignement à une matrice de distances

Un alignement multiple de $n$ séquences et $L$ colonnes peut être vu comme une matrice de caractères. Pour deux séquences $i$ et $j$, la distance p est la proportion de colonnes comparables où les caractères diffèrent :

Les colonnes contenant un gap ou un caractère ambigu sont généralement exclues du dénominateur, ce qui change la longueur effective et doit être documenté. La distance p sous-estime les substitutions multiples : deux séquences peuvent différer à un site après plusieurs changements, et un site revenu à l'état initial est invisible. Les corrections de modèle, comme Jukes-Cantor, corrigent partiellement ce biais :

La formule n'est valable que si $p_{ij}$ reste inférieur à $0{,}75$ ; au-delà, le logarithme n'est pas défini et la distance n'a plus de sens. D'autres modèles, présentés en section 5.2, ajoutent des paramètres pour les transitions, les transversions et l'hétérogénéité des sites. Quel que soit le modèle, NJ reçoit une matrice symétrique, de diagonale nulle, à coefficients positifs ou nuls. Les unités sont des substitutions par site ; une matrice en pourcentage ou en nombre de différences brutes produira des longueurs de branches qui ne sont pas des distances évolutives.

Une matrice est additive si un arbre reproduit exactement ses distances ; pour quatre taxons, la condition des quatre points caractérise ce cas : parmi $d_{AB}+d_{CD}$, $d_{AC}+d_{BD}$ et $d_{AD}+d_{BC}$, les deux plus grandes sommes sont égales. Les matrices réelles ne le sont jamais exactement, à cause du bruit, des substitutions multiples et des erreurs d'alignement. NJ reste défini, mais ses longueurs deviennent une approximation et peuvent être négatives.

Le tableau ci-dessus servira d'exemple travaillé. Il est volontairement petit et non additif : la distance A-C vaut 7, alors que le chemin A-B-C en vaudrait 10 et le chemin A-D-C en vaudrait 13. Aucun arbre ne peut donc représenter exactement les six distances ; NJ cherchera un compromis.

Le critère Q

Notons $d_{ij}$ la distance entre les taxons $i$ et $j$, et $r_i$ la somme des distances du taxon $i$ à tous les autres :

Le critère Q de Neighbor-Joining associe à chaque paire la valeur

La paire qui minimise Q est fusionnée. L'intuition est la suivante : $d_{ij}$ mesure la proximité de la paire, tandis que $r_i$ et $r_j$ mesurent son éloignement au reste du jeu. Soustraire les deux sommes pénalise les taxons qui sont loin de tout le monde et favorise une paire à la fois proche entre elle et éloignée des autres, ce qui est la signature d'une paire sœur, ou cherry. Pour une matrice exactement additive, la paire qui minimise Q est toujours une vraie paire sœur ; c'est le résultat qui justifie la méthode.

Le facteur $(n-2)$ dépend du nombre de taxons actifs : seules les paires d'une même étape sont comparables. Le signe de Q n'a pas d'interprétation biologique. Lorsque plusieurs paires atteignent le minimum, le choix est arbitraire pour la topologie non enracinée : à quatre taxons, les deux paires complémentaires ont toujours le même Q. Un départage par ordre des indices rend l'algorithme reproductible.

Fusion et longueurs de branches

Une fois la paire $(i,j)$ choisie, on crée un nœud interne $u$ et on estime les deux longueurs de branches :

Le premier terme, la moitié de la distance de la paire, serait suffisant si les deux taxons évoluaient à la même vitesse. Le second terme corrige l'asymétrie : si $i$ est globalement plus éloigné que $j$ du reste, sa branche terminale est allongée et celle de $j$ raccourcie. C'est ce qui permet à NJ de fonctionner sans horloge moléculaire. La somme $\delta_i + \delta_j$ reste égale à $d_{ij}$, ce qui est une vérification utile.

La matrice est ensuite mise à jour. Pour chaque taxon $k$ encore actif, la distance au nouveau nœud $u$ devient

Cette formule remplace la paire par son ancêtre : la distance de $k$ à $u$ est la moyenne des distances de $k$ à $i$ et à $j$, diminuée de la moitié de la distance interne. On retire $i$ et $j$ des taxons actifs, on ajoute $u$, et l'on recommence avec $n-1$ taxons. Le processus s'arrête lorsqu'il reste deux nœuds : on les relie par une branche dont chaque moitié vaut $d/2$, ce qui place la racine sur cette dernière arête.

Il y a $n-3$ fusions et chaque étape examine $O(n^2)$ paires : la complexité est $O(n^3)$ en temps et $O(n^2)$ en mémoire. Un jeu de 1 000 taxons reste accessible ; 100 000 ne l'est pas, car la matrice contiendrait dix milliards de cases. NJ est déterministe une fois le départage fixé, contrairement aux recherches stochastiques.

Exemple travaillé à la main

Reprenons la matrice du tableau. Les sommes valent $r_A = 18$, $r_B = 16$, $r_C = 19$ et $r_D = 19$. Calculons les six valeurs de Q :

Le minimum est atteint par A-B et par C-D. Ces deux paires sont complémentaires et définissent la même bipartition : couper l'arbre entre les deux paires donne le même partage des taxons. Choisissons A-B par ordre lexicographique. Les longueurs sont :

Mettons à jour la matrice. Pour C, on obtient $d_{UC} = (7+8-2)/2 = 6{,}5$ ; pour D, $d_{UD} = (9+6-2)/2 = 6{,}5$. Il reste trois nœuds actifs, U, C et D, avec les distances $d_{UC}=6{,}5$, $d_{UD}=6{,}5$ et $d_{CD}=4$. À trois taxons, les trois valeurs de Q sont nécessairement égales : le calcul donne $r_U = 13$, $r_C = 10{,}5$, $r_D = 10{,}5$, donc $Q = -17$ pour les trois paires. L'ordre des indices choisit C-D. Alors :

La distance entre le nœud C-D et U vaut $(6{,}5+6{,}5-4)/2 = 4{,}5$. Il reste deux nœuds : on les relie par deux demi-branches de $2{,}25$. L'arbre s'écrit :

((A:1.5,B:0.5):2.25,(C:2,D:2):2.25);

La longueur totale est $1{,}5+0{,}5+2+2+2{,}25+2{,}25 = 10{,}5$. Le chemin A-C vaut $8$, alors que la matrice donnait 7 : NJ a réparti le conflit sur les branches. Un arbre NJ est donc une synthèse approximative d'une matrice, pas une preuve qu'elle est arborescente.

Arbre non enraciné, enracinement et limites

NJ produit un arbre non enraciné. La dernière fusion place une racine sur une arête, mais cette position est un artefact de l'algorithme : elle ne correspond pas à un ancêtre commun universel. Pour interpréter l'arbre, il faut choisir un enracinement explicite, par exemple avec un groupe externe (outgroup) dont on sait qu'il diverge avant le groupe étudié, ou avec une hypothèse d'horloge moléculaire et une méthode de midpoint rooting. Changer la racine ne change pas les bipartitions non enracinées, mais change la lecture des clades et l'ordre des événements. Un arbre NJ présenté sans racine ni justification de l'enracinement est donc incomplet.

La principale limite de NJ est l'absence de modèle explicite au niveau des sites. Les distances ont peut-être été corrigées par un modèle, mais NJ ne calcule pas de vraisemblance : il ne distingue pas une substitution conservatrice d'une substitution radicale, il ne modélise pas l'hétérogénéité des taux entre sites et il ne traite pas les gaps comme un processus évolutif. Il résume l'alignement en $O(n^2)$ nombres, ce qui est sa force et sa faiblesse. Deux alignements très différents peuvent produire la même matrice, et donc le même arbre.

La qualité de la matrice est déterminante. Des distances mal corrigées, un alignement douteux, des régions variables saturées ou des compositions biaisées déforment les proximités. NJ est particulièrement sensible à l'attraction des longues branches (long-branch attraction) : deux lignées qui évoluent vite peuvent accumuler des ressemblances par convergence et se regrouper à tort. Ce phénomène ne disparaît pas avec un bootstrap, car il affecte tous les réplicats de la même manière. Enfin, NJ ne fournit aucune mesure de support par lui-même ; le bootstrap et les comparaisons de topologies sont des diagnostics ajoutés, pas des garanties.

Pour des divergences faibles à moyennes, NJ reste un bon outil exploratoire et un point de comparaison. Lorsque la position exacte d'une branche compte, confrontez-le à une analyse par maximum de vraisemblance ou par inférence bayésienne, avec un modèle justifié et des diagnostics de convergence.

Bootstrap : rééchantillonner les colonnes

Le bootstrap de Felsenstein traite les colonnes de l'alignement comme des observations indépendantes. Pour chaque réplicat, on tire $L$ colonnes avec remise parmi les $L$ colonnes originales, puis on recalcule entièrement la matrice de distances et l'arbre. Certaines colonnes sont absentes du réplicat, d'autres apparaissent plusieurs fois. Le réplicat a la même longueur que l'alignement, mais sa composition change : c'est un pseudo-échantillon qui simule la variabilité d'échantillonnage des sites.

Pour une bipartition interne $s$, le support bootstrap est la proportion de réplicats dont l'arbre contient $s$ :

Le nombre de réplicats $B$ contrôle la précision du pourcentage. Avec $B=100$, l'erreur type d'une proportion voisine de 50 % est d'environ 5 points ; avec $B=1\,000$, elle descend à environ 1,6 point. La convention courante est de 1 000 réplicats pour une analyse publiable, 100 pour une exploration, et 10 000 lorsque l'on veut distinguer finement des supports proches de 90 %. Il faut fixer la graine du générateur aléatoire et rapporter $B$, sinon le résultat n'est pas reproductible. Un support calculé sur 20 réplicats ne se lit pas comme un support calculé sur 1 000.

Un support de 95 % signifie que 95 % des réplicats contiennent la bipartition. Ce n'est pas la probabilité que le clade soit vrai, ni une p-value, ni une mesure de la qualité de l'alignement. Un clade peut avoir 100 % de support et être faux si le modèle, l'alignement ou l'échantillonnage des taxons est biaisé. Inversement, un clade réel peut avoir un support faible si la branche interne est courte, si l'alignement est trop court ou si les sites portent des signaux contradictoires. Le support mesure la stabilité sous un schéma de rééchantillonnage précis, pas la vérité.

Il faut aussi distinguer le bootstrap du posterior bayésien. Une probabilité postérieure est calculée à partir d'un modèle, d'une vraisemblance et d'une loi a priori, et résume la distribution des arbres conditionnellement aux données. Le bootstrap rééchantillonne les colonnes et ne fait intervenir ni prior ni vraisemblance de site. Les deux nombres peuvent être proches, mais ils ne mesurent pas la même chose et ne se comparent pas directement : un posterior de 0,95 et un support bootstrap de 95 % ne sont pas interchangeables. La confusion est fréquente dans les articles et dans les rapports automatiques.

Enfin, le consensus résume un ensemble d'arbres. Le consensus strict ne conserve que les bipartitions présentes partout ; le consensus majoritaire (majority-rule) garde celles présentes dans plus de 50 % des arbres ; le consensus étendu ajoute les bipartitions compatibles. On annote les supports sur le consensus ou sur l'arbre de meilleur score. Les seuils 50, 70 et 95 sont des conventions, pas des frontières naturelles : un support de 70 % dépend de la longueur de l'alignement, du nombre de taxons et du modèle.

Implémentation

Le code suivant est autonome et n'utilise que la bibliothèque standard. Il a été exécuté avec Python 3.13.5 le 2026-11-01. Il implémente le critère Q, la construction NJ, la sérialisation Newick, le comptage des bipartitions et un petit bootstrap par colonnes. Les matrices sont des listes de listes ; les arbres sont des dictionnaires imbriqués avec les clés name, length et children.

Aucune sortie. Exécutez le code pour voir le résultat.

La sortie obtenue est :

Q(A,B) = -30.0
Q(A,C) = -23.0
Q(A,D) = -19.0
Q(B,C) = -19.0
Q(B,D) = -23.0
Q(C,D) = -30.0
NJ : ((A:1.5,B:0.5):2.25,(C:2,D:2):2.25);
Longueur : 10.5
Support ('A', 'B') : 80.0 %
Support ('A', 'C') : 20.0 %

Trois points méritent attention. D'abord, la fonction nj_tree ne valide pas la matrice : dans un vrai projet, il faut vérifier la taille, la symétrie, la diagonale nulle et la positivité avant de lancer l'algorithme, sinon une matrice asymétrique produit des longueurs absurdes sans erreur. Ensuite, le choix de la paire minimale est déterministe grâce à l'ordre de la liste pairs ; si l'on parcourt les paires dans un autre ordre, l'arbre non enraciné reste le même mais la racine et l'ordre des clades peuvent changer. Enfin, to_newick supprime les zéros finals mais ne corrige pas les longueurs négatives : une matrice non additive peut produire une branche négative, qu'il faut signaler plutôt que masquer.

Le petit bootstrap utilise un alignement synthétique de 10 colonnes. Les séquences A et B ne diffèrent qu'aux colonnes 5 à 8, et C et D aux mêmes colonnes ; six colonnes soutiennent la bipartition A-B, quatre soutiennent A-C. Avec la graine 7 et 20 réplicats, le support de A-B vaut 80 % et celui de A-C 20 %. Ce résultat n'est pas une propriété de l'alignement : il dépend du tirage. Changer la graine déplace les pourcentages de quelques points, ce qui illustre la variabilité d'un bootstrap à petit nombre de réplicats.

Étude de cas

Nous utilisons le fichier datasets/phylogeny/demo.nwk, un arbre synthétique fourni avec le cours. Il contient quatre taxons et deux valeurs de support déjà écrites dans le Newick : 95 pour la paire taxon_A/taxon_B, 80 pour la paire taxon_C/taxon_D. La question est double : NJ retrouve-t-il la topologie de cet arbre à partir des distances de trajet, et que signifient exactement les nombres 95 et 80 ?

On lit l'arbre avec Biopython, on calcule la matrice des distances de trajet entre feuilles, on lance NJ, puis on compare le Newick obtenu et les supports stockés. Ces distances sont celles de l'arbre lui-même : NJ devrait donc retrouver exactement la topologie non enracinée, ce qui fournit un test de cohérence.

from Bio import Phylo
 
TREE_FILE = "datasets/phylogeny/demo.nwk"
tree = Phylo.read(TREE_FILE, "newick")
names = [terminal.name for terminal in tree.get_terminals()]
matrix = [[round(tree.distance(a, b), 3) for b in names] for a in names]
 
print("Taxons :", names)
for row in matrix:
    print(row)
 
for clade in tree.get_nonterminals():
    if clade.confidence is not None:
        leaves = [terminal.name for terminal in clade.get_terminals()]
        print("Support", leaves, ":", clade.confidence)
 
joined = nj_tree(names, matrix)
print("NJ :", to_newick(joined))
print("Longueur :", round(total_length(joined), 3))

La sortie vérifiée localement le 2026-11-01 sur cet exemple synthétique est :

Taxons : ['taxon_A', 'taxon_B', 'taxon_C', 'taxon_D']
[0.0, 0.3, 0.95, 1.05]
[0.3, 0.0, 1.05, 1.15]
[0.95, 1.05, 0.0, 0.4]
[1.05, 1.15, 0.4, 0.0]
Support ['taxon_A', 'taxon_B'] : 95
Support ['taxon_C', 'taxon_D'] : 80
NJ : ((taxon_A:0.1,taxon_B:0.2):0.35,(taxon_C:0.15,taxon_D:0.25):0.35);
Longueur : 1.4

La matrice de trajet vaut 0,3 entre A et B, 0,4 entre C et D, 0,95 entre A et C, 1,05 entre A et D et B et C, et 1,15 entre B et D. NJ retrouve la bipartition A-B contre C-D et les longueurs terminales 0,1, 0,2, 0,15 et 0,25. La branche interne, découpée en 0,3 et 0,4 par la racine d'origine, devient deux demi-branches de 0,35 : la racine de NJ est placée sur la dernière arête. La longueur totale reste 1,4 et les distances de trajet sont identiques. C'est le comportement attendu pour une matrice additive : la topologie et les longueurs non enracinées sont retrouvées, seule la racine change.

Les valeurs 95 et 80 ne sont pas calculées par NJ. Elles sont lues dans le fichier, sur les nœuds internes, et proviennent d'une analyse antérieure dont le fichier ne documente ni le nombre de réplicats, ni la méthode, ni la graine. Dans un rapport réel, il faudrait joindre ces métadonnées. Si elles viennent d'un bootstrap standard de 1 000 réplicats, 95 signifie que la bipartition A-B apparaît dans 95 % des arbres reconstruits ; 80 est un support plus faible, compatible avec une branche interne courte ou un signal contradictoire. Si elles viennent d'UFBoot, la lecture est différente. Dans tous les cas, un arbre unique avec des nombres ne permet pas de vérifier le calcul : il faut les réplicats ou, au minimum, la commande et le journal de l'analyse.

Erreurs fréquentes

Quiz

Exercices

python -m pytest exercises/module-5/5.3-neighbor-joining-bootstrap -q

python -m pytest exercises/module-5/5.3-neighbor-joining-bootstrap -q

python -m pytest exercises/module-5/5.3-neighbor-joining-bootstrap/projet -q

Résumé

• NJ construit un arbre non enraciné par fusions successives à partir d'une matrice de distances, en minimisant le critère $Q(i,j) = (n-2)d_{ij} - r_i - r_j$.
• Les longueurs se déduisent de la distance de la paire et de $r_i - r_j$ ; la matrice est mise à jour après chaque fusion, pour une complexité $O(n^3)$ en temps et $O(n^2)$ en mémoire.
• La méthode est déterministe si l'on fixe le départage des ex æquo.
• NJ n'utilise pas de modèle explicite au niveau des sites et reste sensible aux erreurs de distance, aux alignements douteux et à l'attraction des longues branches.
• Le bootstrap rééchantillonne les colonnes avec remise, reconstruit l'arbre pour chaque réplicat et comptabilise les bipartitions.
• Un support de 95 % est une fréquence de réplicats, pas une probabilité de vérité ni un posterior bayésien.
• Le nombre de réplicats, la graine, la méthode et la version du logiciel font partie du résultat ; un consensus majoritaire résume les bipartitions fréquentes.
• Un arbre NJ doit être enraciné explicitement et accompagné de ses diagnostics, jamais présenté comme une vérité biologique.

Références

• Saitou, N. et Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution, 4(4), 406–425.
• Felsenstein, J. (1985). Confidence limits on phylogenies: an approach using the bootstrap. Evolution, 39(4), 783–791.
• Jukes, T. H. et Cantor, C. R. (1969). Evolution of protein molecules. In Mammalian Protein Metabolism, Academic Press, 21–132.
• Minh, B. Q. et al. (2020). IQ-TREE 2: new models and efficient methods for phylogenetic inference in the genomic era. Molecular Biology and Evolution, 37(5), 1530–1534.
• Cock, P. J. A. et al. (2009). Biopython: freely available Python tools for computational molecular biology and bioinformatics. Bioinformatics, 25(11), 1422–1423.
• Biopython. Tutorial and Cookbook, chapitre Phylogenetics, et documentation de Bio.Phylo. https://biopython.org/docs/1.88/Tutorial/index.html et https://biopython.org/docs/1.88/api/Bio.Phylo.html
• IQ-TREE. Documentation: Ultrafast Bootstrap. http://www.iqtree.org/doc/