Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

Stellen Sie sich vor, Sie versuchen, ein riesiges, uraltes Familiengeheimnis zu lösen. Sie haben einen Haufen alter, handgeschriebener Briefe (die DNA) von tausenden Menschen und möchten einen Stammbaum zeichnen, um zu sehen, wer mit wem verwandt ist. Wissenschaftler machen das ständig, um die Ausbreitung von Viren oder Bakterien während eines Ausbruchs zu verfolgen. Aber hier ist der knifflige Teil: Es gibt nicht nur einen Weg, den Baum zu zeichnen. Je nachdem, welchen mathematischen Trick man verwendet, um die Punkte zu verbinden, erhält man vielleicht ein etwas anderes Bild der Familiengeschichte. Manchmal sagt ein Baum: „Cousin A ist eng mit Cousin B verwandt“, während ein anderer Baum sagt: „Eigentlich sind sie entfernte Fremde.“

Um herauszufinden, welcher Baum besser ist oder wie unterschiedlich zwei Bäume voneinander sind, benötigen Wissenschaftler eine Möglichkeit, den „Abstand“ zwischen ihnen zu messen. Stellen Sie sich das wie den Vergleich zweier verschiedener Stadtpläne vor. Ein Plan zeigt vielleicht eine Straße, die der andere übersieht. In der Welt der Biologie ist die genaueste Methode, diesen Unterschied zu messen, die sogenannte „Subtree Prune and Regraft“ (SPR)-Distanz. Es ist so, als würde man fragen: „Wie oft muss ich einen Ast abschneiden und an einer anderen Stelle wieder ankleben, damit er exakt wie der andere Baum aussieht?“ Diese Methode ist unglaublich präzise, weil sie die tatsächlichen biologischen Bewegungen zählt, wie etwa genetische Austauschprozesse, die im Laufe der Zeit stattgefunden haben. Es gibt jedoch einen Haken: Diese Mathematik zu betreiben ist so schwer und langsam, dass es für einen Baum mit tausenden Blättern (die tausende Bakterien repräsentieren) eine Supercomputer Jahre dauern würde, um die Berechnung abzuschließen. Es ist, als würde man versuchen, jedes einzelne Sandkorn an einem Strand zu zählen, um die Größe des Strandes zu messen; es ist theoretisch möglich, aber praktisch unmöglich.

Hier wird die Geschichte spannend. Die Forscher in dieser Arbeit stellten eine einfache Frage: „Können wir einen Computer lehren, diesen Abstand schnell zu erraten, ohne die unmögliche Mathematik zu betreiben?“ Sie entwickelten eine spezielle Art von künstlicher Intelligenz, ein Graph Neural Network (GNN). Sie können sich dieses KI-System als einen superintelligenten Schüler vorstellen, der tausende von Baumpaaren studiert hat und gelernt hat, die Muster darin zu erkennen, wie sie sich voneinanderschieden. Anstatt die schwere, mühsame Arbeit des Abschneidens und Aufklebens von Ästen zu leisten, betrachtet die KI die Form der Bäume und macht eine sehr schnelle Schätzung. Die Studie zeigt, dass diese KI lernen kann, die Distanz zwischen Bäumen mit überraschender Genauigkeit vorherzusagen, offenbart aber auch eine spezifische Schwäche: Sie hat Schwierigkeiten, wenn sie mit Bäumen konfrontiert wird, die viel größer sind als die, die sie in der Schule studiert hat.

Das große Experiment: Eine KI beim Vergleich von Bäumen lehren

Das Team hinter dieser Studie, unter der Leitung von Renata Martins Castanheira und ihren Kollegen, wollte ein System entwickeln, das in der Lage ist, diese biologischen Stammbäume in nahezu Echtzeit zu vergleichen. Ihr Ziel war es, ein Werkzeug zu schaffen, das die massiven Datensätze der modernen Krankheitsverfolgung bewältigen kann, bei denen Wissenschaftler gleichzeitig bis zu 9.500 verschiedene bakterielle Proben untersuchen könnten.

Zuerst mussten sie einen Trainingsplatz aufbauen. Sie sammelten genetische Daten von vier verschiedenen Bakterientypen: Clostridium, Salmonella, Vibrio und Streptococcus pneumoniae. Sie schnitten diese Daten in Gruppen unterschiedlicher Größe, die von kleinen Gruppen von 90 Isolaten bis hin zu massiven Gruppen von bis zu 9.500 Isolaten reichten. Mit Standardcomputermethoden erzeugten sie 864 verschiedene Stammbäume aus diesen Daten. Um das Training interessant zu gestalten, nutzten sie die Bäume nicht einfach so, wie sie waren; sie veränderten die Daten leicht, um „Zwillinge“ mit leicht unterschiedlichen Formen zu erschaffen. Dies gab ihnen 388 Paare von Bäumen zum Vergleichen.

Der clevere Teil war: Sie brauchten einen „Lehrer“, der der KI die richtige Antwort sagte. Da die perfekte, exakte Mathematik (die „rooted SPR“-Distanz) für große Bäume zu langsam zu berechnen ist, verwendeten sie eine schnellere, etwas weniger perfekte Methode namens „Heuristik“ (eine intelligente Abkürzung), um die Antworten zu generieren, von denen die KI lernen sollte. Bevor sie diesem Shortcut vertrauten, testeten sie ihn an kleinen Bäumen, bei denen sie die perfekte Mathematik anwenden konnten. Sie fanden heraus, dass die Abkürzung fast perfekt mit der echten Antwort übereinstimmte, mit einer Korrelation von 0,98 bis 0,99. Sie war nicht perfekt – sie neigte dazu, Zahlen zu schätzen, die etwas zu niedrig waren (etwa 65 % bis 71 % des wahren Wertes) – aber die Rangfolge stimmte exakt. Wenn Baum A sich stärker von Baum B unterschied als Baum C von Baum D, dann wusste auch die Heuristik das. Dies machte sie zu einem perfekten „Surrogat-Lehrer“ für die KI.

Als Nächstes bauten sie die KI. Sie verwendeten eine spezifische Art von neuronalem Netzwerk, ein Siamese Graph Isomorphism Network (GIN). Stellen Sie sich zwei identische Zwillinge vor (der „Siamese“-Teil), die beide auf einen Baum schauen. Die KI zerlegt jeden Baum in einen Graphen, bei dem jeder Knoten (Verzweigungspunkt oder Blatt) einen kleinen Ausweis mit Informationen besitzt wie „Ich bin ein Blatt“, „Ich bin weit von der Wurzel entfernt“ oder „Ich gehöre zu dieser Spezies“. Die KI verarbeitet diese Bäume und sucht nach Mustern in der Anordnung der Äste. Schließlich nimmt sie die „Gedanken“ aus beiden Bäumen, kombiniert sie und gibt eine einzige Zahl aus: die vorhergesagte Distanz zwischen ihnen.

Was sie herausfanden

Die Ergebnisse waren eine Mischung aus großem Erfolg und klaren Einschränkungen, abhängig von der jeweiligen Situation.

Wenn die KI in ihrer Komfortzone blieb:
Als die Forscher die KI an Bäumen testeten, die in Größe und Typ den Modellen ähnlich waren, die sie studiert hatte (das „In-Distribution“-Szenario), zeigte sie eine glänzende Leistung. Sie konnte etwa 87 % bis 90 % der Unterschiede zwischen den Bäumen erklären. Einfach ausgedrückt: Wenn man die KI nach der Distanz zwischen zwei Bäumen fragte, die sie bereits „gesehen“ hatte, lag sie meistens richtig. Sie war etwa viermal besser als die bloße Schätzung der durchschnittlichen Distanz für jedes Paar. Dies deutet darauf hin, dass die KI tatsächlich die Regeln gelernt hat, wie die Formen der Bäume miteinander zusammenhängen.

Wenn die KI neue Freunde traf:
Das Team fragte sich dann: „Kann diese KI eine neue Art von Bakterien verstehen, die sie noch nie gesehen hat?“ Sie trainierten die KI auf zwei Arten von Bakterien und testeten sie an zwei völlig anderen. Die KI versagte nicht völlig, aber sie wurde deutlich schlechter. Ihre Genauigkeit sank und erklärte nur noch etwa 37 % der Varianz. Dies zeigt uns, dass die KI zwar einige allgemeine Regeln über Baumformen gelernt hat, sich aber auch an den spezifischen „Geschmack“ der Bakterien gewöhnt hat, die sie studiert hat. Es ist wie ein Schüler, der in Mathematik großartig ist, aber verwirrt ist, wenn der Lehrer von Algebra zu Geometie wechselt.

Wenn die KI auf Riesen traf:
Die wichtigste Erkenntnis war jedoch, was passierte, als die KI mit Bäumen konfrontiert wurde, die viel größer waren als die in ihrem Trainingsdatensatz. Die Forscher trainierten die KI auf kleine und mittlere Bäume und baten sie dann, die Distanz für die massiven Bäume mit bis zu 9.500 Isolaten zu schätzen. Das Ergebnis? Die KI brach zusammen. Ihre Genauigkeit sank nicht nur, sie wurde sogar schlechter als die bloße Schätzung der Durchschnittsdistanz. Das Modell konnte schlichtweg nicht „extrapolieren“ oder begreifen, wie es mit Größen umgehen soll, die es noch nie gesehen hatte. Es ist, als würde man ein Kind lehren, bis 100 zu zählen, und es dann bitten, bis zu einer Million zu zählen; es weiß nicht, wie es die Logik auf größere Maßstäbe übertragen soll.

Das Fazit

Diese Arbeit behauptet nicht, das Problem des Vergleichs von phylogenetischen Bäumen für immer gelöst zu haben. Stattdessen bietet sie ein leistungsstarkes neues Werkzeug, das für Bäume einer bestimmten Größe und eines bestimmten Typs, die es bereits kennt, hervorragend funktioniert. Die Autoren zeigen, dass wir eine KI trainieren können, um diese komplexen biologischen Distanzen in einem Bruchteil einer Sekunde zu annähern, was ein riesiger Schritt nach vorn für die Verfolgung von Epidemien ist.

Dennoch sind sie sich der Grenzen sehr bewusst. Die KI ist kein Zauberstab, der bei jedem Baum jedweder Größe funktioniert. Sie hat Probleme mit neuen Spezies und versagt völlig, wenn die Bäume zu groß werden. Die Autoren schlagen vor, dass zukünftige Arbeiten die KI mit noch größeren Bäumen trainieren müssen und ihr vielleicht beibringen müssen, besser mit Größenunterschieden umzugehen. Sie weisen auch darauf hin, dass die KI derzeit nur die Anzahl der Bewegungen vorhersagt, die nötig sind, um einen Baum in einen anderen zu verwandeln. Ein zukünftiges Ziel wäre es, die KI dazu zu bringen, exakt anzuzeigen, welche Äste bewegt werden müssen, um Wissenschaftlern eine Roadmap der Veränderungen anstelle eines bloßen Distanzwertes zu geben.

Kurz gesagt: Die Arbeit beweist, dass Graph Neural Networks exzellente „schnelle Schätzer“ für Baumdistanzen sein können, vorausgesetzt, die Bäume sind nicht zu seltsam oder zu riesig. Es ist ein vielversprechender Anfang, aber die KI muss noch viel nachreifen, bevor sie die größten Herausforderungen auf diesem Gebiet bewältigen kann.