Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

Imaginez que vous essayez de résoudre un mystère familial ancien et colossal. Vous avez une pile de vieilles lettres manuscrites (l'ADN) provenant de milliers de personnes, et vous voulez dessiner un arbre généalogique pour voir qui est apparenté à qui. Les scientifiques font cela tout le temps pour suivre la propagation des virus ou des bactéries lors d'une épidémie. Mais voici la partie délicate : il n'y a pas qu'une seule façon de dessiner l'arbre. Selon la technique mathématique utilisée pour relier les points, vous pourriez obtenir une image légèrement différente de l'histoire familiale. Parfois, un arbre dit « Le cousin A est proche du cousin B », tandis qu'un autre dit « En fait, ce sont des cousins éloignés, presque des étrangers ».

Pour déterminer quel arbre est le meilleur, ou comment deux arbres diffèrent l'un de l'autre, les scientifiques ont besoin d'un moyen de mesurer la « distance » entre eux. Imaginez que vous compariez deux cartes différentes d'une même ville. Une carte peut montrer une route qu'une autre oublie. Dans le monde de la biologie, la façon la plus précise de mesurer cette différence s'appelle la distance « Subtree Prune and Regraft » (SPR - Élagage et Recollement de Sous-arbres). C'est comme demander : « Combien de fois dois-je couper une branche d'un arbre et la recoller à un autre endroit pour qu'il ressemble exactement à l'autre ? » Cette méthode est incroyablement précise car elle compte les mouvements biologiques réels, comme les échanges génétiques, qui se sont produits au fil du temps. Cependant, il y a un piège : faire ce calcul est si difficile et lent que pour un arbre avec des milliers de feuilles (représentant des milliers de bactéries), il faudrait à un supercalculateur des années pour terminer le calcul. C'est comme essayer de compter chaque grain de sable sur une plage pour mesurer la taille de la plage ; c'est théoriquement possible, mais pratiquement impossible.

C'est là que l'histoire devient passionnante. Les chercheurs de cet article se sont posé une question simple : « Pouvons-nous apprendre à un ordinateur à deviner cette distance rapidement, sans faire les mathématiques impossibles ? » Ils ont construit un type spécial d'intelligence artificielle appelé Réseau de Neurones sur Graphe (GNN - Graph Neural Network). Vous pouvez considérer cette IA comme un étudiant super intelligent qui a étudié des milliers de paires d'arbres et a appris à repérer les motifs de leurs différences. Au lieu de faire le travail lourd et lent de couper et coller des branches, l'IA observe la forme des arbres et fait une estimation très rapide. Le papier montre que cette IA peut prédire la distance entre les arbres avec une précision surprenante, mais il révèle aussi qu'elle a une faiblesse spécifique : elle a du mal lorsqu'elle voit des arbres beaucoup plus grands que ceux qu'elle a étudiés à l'école.

La Grande Expérience : Enseigner à l'IA à Comparer des Arbres

L'équipe derrière cette étude, dirigée par Renata Martins Castanheira et ses collègues, s'est donné pour mission de construire un système capable de comparer ces arbres généalogiques biologiques en un temps quasi instantané. Leur objectif était de créer un outil capable de gérer les ensembles de données massifs utilisés dans le suivi moderne des maladies, où les scientifiques peuvent examiner jusqu'à 9 500 échantillons bactériens différents à la fois.

D'abord, ils ont dû construire un terrain d'entraînement. Ils ont rassemblé des données génétiques provenant de quatre types différents de bactéries : Clostridium, Salmonella, Vibrio et Streptococcus pneumoniae. Ils ont découpé ces données en groupes de tailles différentes, allant de petits groupes de 90 isolats à des groupes massifs allant jusqu'à 9 500. En utilisant des méthodes informatiques standards, ils ont généré 864 arbres généalogiques différents à partir de ces données. Pour rendre l'entraînement intéressant, ils n'ont pas seulement utilisé les arbres tels quels ; ils ont légèrement mélangé les données pour créer des « jumeaux » aux formes légèrement différentes. Cela leur a permis d'obtenir 388 paires d'arbres à comparer.

Voici la partie ingénieuse : ils avaient besoin d'un « enseignant » pour dire à l'IA quelle était la bonne réponse. Puisque la mathématique parfaite et exacte (la distance « rooted SPR ») est trop lente à calculer pour les grands arbres, ils ont utilisé une méthode un peu moins parfaite mais plus rapide appelée « heuristique » (un raccourci intelligent) pour générer les réponses servant à l'apprentissage de l'IA. Avant de faire confiance à ce raccourci, ils l'ont testé sur de petits arbres où ils pouvaient effectuer le calcul parfait. Ils ont constaté que le raccourci était presque parfaitement aligné avec la vraie réponse, avec une corrélation de 0,98 à 0,99. Ce n'était pas parfait — il avait tendance à donner des chiffres un peu trop bas (environ 65 % à 71 % de la valeur réelle) — mais le classement était exact. Si l'arbre A était plus différent de l'arbre B que l'arbre C ne l'était de l'arbre D, le raccourci le savait. Cela en faisait un « substitut » parfait pour l'enseignant de l'IA.

Ensuite, ils ont construit l'IA. Ils ont utilisé un type spécifique de réseau de neurones appelé Réseau d'Isomorphisme de Graphe Siamois (GIN - Siamese Graph Isomorphism Network). Imaginez deux jumeaux identiques (la partie « Siamois ») qui regardent tous deux un arbre. L'IA décompose chaque arbre en un graphe, où chaque nœud (point de ramification ou feuille) possède une petite fiche d'identité avec des informations telles que « Je suis une feuille », « Je suis loin de la racine » ou « J'appartiens à cette espèce ». L'IA traite ensuite ces arbres, cherchant des motifs dans la façon dont les branches sont disposées. Enfin, elle prend les « pensées » de ces deux arbres, les combine et recrache un seul nombre : la distance prédite entre eux.

Ce Qu'Ils Ont Découvert

Les résultats étaient un mélange de grand succès et de limites claires, selon la situation.

Quand l'IA restait dans sa zone de confort :
Lorsque les chercheurs ont testé l'IA sur des arbres de taille et de type similaires à ceux qu'elle avait étudiés (le scénario « in-distribution »), elle s'est comportée brillamment. Elle pouvait expliquer environ 87 % à 90 % des différences entre les arbres. En termes simples, si vous demandiez à l'IA de deviner la distance entre deux arbres qu'elle avait déjà vus, elle avait raison la plupart du temps. Elle était environ quatre fois meilleure que si elle se contentait de deviner la distance moyenne pour chaque paire. Cela suggère que l'IA a réellement appris les règles de la relation entre les formes d'arbres.

Quand l'IA rencontrait de nouveaux amis :
L'équipe a ensuite demandé : « Cette IA peut-elle comprendre un nouveau type de bactérie qu'elle n'a jamais vu ? » Ils ont entraîné l'IA sur deux espèces et l'ont testée sur deux autres espèces complètement différentes. L'IA n'a pas totalement échoué, mais ses performances se sont nettement dégradées. Sa précision a chuté, n'expliquant plus que 37 % de la variance. Cela nous indique que si l'IA a appris certaines règles générales sur les formes d'arbres, elle s'est aussi habituée à la « saveur » spécifique des bactéries qu'elle a étudiées. C'est comme un élève qui est excellent en mathématiques mais qui se perd lorsque le professeur passe de l'algèbre à la géométrie.

Quand l'IA faisait face à des géants :
La découverte la plus importante, cependant, fut ce qui est arrivé lorsque l'IA a été confrontée à des arbres beaucoup plus grands que ceux de son ensemble d'entraînement. Les chercheurs ont entraîné l'IA sur des arbres petits et moyens, puis lui ont demandé de deviner la distance pour les arbres massifs comprenant jusqu'à 9 500 isolats. Le résultat ? L'IA s'est effondrée. Sa précision n'a pas seulement chuté ; elle est devenue pire que si elle s'était contentée de deviner la moyenne. Le modèle n'a tout simplement pas pu « extrapoler » ou comprendre comment gérer des tailles qu'il n'avait jamais rencontrées auparavant. C'est comme apprendre à un enfant à compter jusqu'à 100, puis lui demander de compter jusqu'à un million ; il ne sait pas comment appliquer la logique à une plus grande échelle.

La Conclusion

Cet article ne prétend pas avoir résolu définitivement le problème de la comparaison des arbres phylogénétiques. Au lieu de cela, il propose un nouvel outil puissant qui fonctionne extrêmement bien pour des arbres de taille et de type déjà connus. Les auteurs montrent que nous pouvons entraîner une IA à approximer ces distances biologiques complexes en une fraction de seconde, ce qui est une étape majeure pour le suivi des épidémies.

Cependant, ils sont très clairs sur les limites. L'IA n'est pas une baguette magique qui fonctionne sur n'importe quel arbre de n'importe quelle taille. Elle éprouve des difficultés avec les nouvelles espèces et échoue complètement lorsque les arbres deviennent trop grands. Les auteurs suggèrent que, pour corriger cela, les travaux futurs devront nourrir l'IA avec des arbres encore plus grands pendant l'entraînement et peut-être lui apprendre à mieux gérer les différences de taille. Ils soulignent également qu'actuellement, l'IA ne devine que le nombre de mouvements nécessaires pour changer un arbre en un autre. Un objectif futur serait de permettre à l'IA d'indiquer exactement quelles branches doivent être déplacées, offrant ainsi aux scientifiques une feuille de route des changements plutôt qu'un simple score de distance.

En résumé, l'article prouve que les réseaux de neurones sur graphes peuvent être d'excellents « devineurs rapides » pour les distances d'arbres, à condition que les arbres ne soient pas trop étranges ou trop gigantesques. C'est un début prometteur, mais l'IA a encore beaucoup de chemin à parcourir avant de pouvoir relever les plus grands défis du domaine.