Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

Immagina di cercare di risolvere un enorme, antico mistero di famiglia. Hai un mucchio di vecchie lettere scritte a mano (il DNA) di migliaia di persone e vuoi disegnare un albero genealogico per vedere chi è imparentato con chi. Gli scienziati fanno questo continuamente per tracciare come i virus o i batteri si diffondono durante un focolaio. Ma ecco la parte complicata: non esiste un solo modo per disegnare l'albero. A seconda del trucco matematico che usi per connettere i punti, potresti ottenere un'immagine leggermente diversa della storia familiare. A volte, un albero dice "Il cugino A è vicino al cugino B", mentre un altro dice "In realtà, sono estranei distanti".

Per capire quale albero sia migliore, o quanto siano diversi due alberi tra loro, gli scienziati hanno bisogno di un modo per misurare la "distanza" tra loro. Immagina di confrontare due diverse mappe della stessa città. Una mappa potrebbe mostrare una strada che l'altra tralascia. Nel mondo della biologia, il modo più accurato per misurare questa differenza è chiamato distanza "Subtree Prune and Regraft" (SPR). È come chiedere: "Quante volte devo tagliare un ramo da un albero e incollarlo in un altro punto per farlo apparire esattamente come l'altro?" Questo metodo è incredibilmente preciso perché conta i veri movimenti biologici, come gli scambi genetici, che sono avvenuti nel tempo. Tuttavia, c'è un problema: fare questa matematica è così difficile e lento che per un albero con migliaia di foglie (che rappresentano migliaia di batteri), richiederebbe a un supercomputer anni per completare il calcolo. È come cercare di contare ogni singolo granello di sabbia su una spiaggia per misurare la dimensione della spiaggia; è possibile in teoria, ma praticamente impossibile.

È qui che la storia diventa interessante. I ricercatori in questo articolo si sono posti una domanda semplice: "Possiamo insegnare a un computer a indovinare questa distanza velocemente, senza fare la matematica impossibile?" Hanno costruito un tipo speciale di intelligenza artificiale chiamato Graph Neural Network (GNN). Puoi pensare a questa IA come a uno studente super intelligente che ha studiato migliaia di coppie di alberi e ha imparato a scorgere i modelli di come differiscono tra loro. Invece di fare il lavoro pesante e lento di tagliare e incollare i rami, l'IA osserva la forma degli alberi e fa un tentativo molto veloce. Il documento mostra che questa IA può imparare a prevedere la distanza tra gli alberi con una precisione sorprendente, ma rivela anche che l'IA ha un punto debole specifico: fatica quando vede alberi molto più grandi di quelli che ha studiato a scuola.

Il Grande Esperimento: Insegnare all'IA a Confrontare gli Alberi

Il team dietro questo studio, guidato da Renata Martins Castanheira e dai suoi colleghi, si è posto l'obiettivo di costruire un sistema che potesse confrontare questi alberi genealogici biologici in tempi quasi istantanei. Il loro obiettivo era creare uno strumento che potesse gestire i massicci dataset utilizzati nella moderna tracciabilità delle malattie, dove gli scienziati potrebbero esaminare fino a 9.500 diversi campioni batterici contemporaneamente.

Per prima cosa, dovevano costruire un campo di addestramento. Hanno raccolto dati genetici da quattro diversi tipi di batteri: Clostridium, Salmonella, Vibrio e Streptococcus pneumoniae. Hanno suddiviso questi dati in gruppi di diverse dimensioni, che vanno da piccoli gruppi di 90 isolati a gruppi massicci fino a 9.500. Utilizzando metodi informatici standard, hanno generato 864 diversi alberi genealogici da questi dati. Per rendere l'addestramento interessante, non hanno usato gli alberi così come sono; hanno rimescolato leggermente i dati per creare dei "gemelli" con forme leggermente diverse. Questo ha dato loro 388 coppie di alberi da confrontare.

Ecco la parte geniale: avevano bisogno di un "insegnante" per dire all'IA qual era la risposta corretta. Poiché la matematica perfetta ed esatta (la distanza "rooted SPR") è troppo lenta da calcolare per alberi grandi, hanno usato un metodo più veloce e leggermente meno perfetto chiamato "euristica" (una scorciatozza intelligente) per generare le risposte da cui l'IA potesse imparare. Prima di fidarsi di questa scorciatoia, l'hanno testata su alberi piccoli dove potevano eseguire la matematica perfetta. Hanno scoperto che la scorciatoia era quasi perfettamente allineata con la risposta reale, con una correlazione di 0,98 a 0,99. Non era perfetta — tendeva a indovinare numeri che erano un po' troppo bassi (circa il 65% o il 71% del valore reale) — ma la classifica era puntuale. Se l'Albero A era più diverso dall'Albero B di quanto l'Albero C fosse dall'Albero D, la scorciatoia lo sapeva. Questo la rendeva un "surrogato" perfetto per l'insegnante dell'IA.

Successivamente, hanno costruito l'IA. Hanno utilizzato un tipo specifico di rete neurale chiamato Siamese Graph Isomorphism Network (GIN). Immagina due gemelli identici (la parte "Siamese") che guardano entrambi un albero. L'IA scompone ogni albero in un grafo, dove ogni nodo (punto di ramificazione o foglia) ha una piccola tessera d'identità con informazioni come "Sono una foglia", "Sono lontano dalla radice" o "appartengo a questa specie". L'IA elabora quindi questi alberi, cercando pattern nel modo in cui i rami sono disposti. Infine, prende i "pensieri" da entrambi gli alberi, li combina e sputa fuori un singolo numero: la distanza predetta tra di essi.

Cosa Hanno Scoperto

I risultati sono stati un misto di grande successo e chiare limitazioni, a seconda della situazione.

Quando l'IA rimaneva nella sua zona di comfort:
Quando i ricercatori hanno testato l'IA su alberi di dimensioni e tipo simili a quelli che aveva studiato (lo scenario "in-distribution"), l'IA si è comportata brillantemente. Poteva spiegare circa l'87% - 90% delle differenze tra gli alberi. In termini semplici, se chiedevi all'IA di indovinare la distanza tra due alberi che aveva già visto, ci riusciva la maggior parte delle volte. Era circa quattro volte migliore rispetto al semplice indovinare la distanza media per ogni coppia. Ciò suggerisce che l'IA ha realmente imparato le regole di come le forme degli alberi si relazionano tra loro.

Quando l'IA incontrava nuovi amici:
Il team ha poi chiesto: "Questa IA può capire un nuovo tipo di batterio che non ha mai visto?" Hanno addestrato l'IA su due specie e l'hanno testata su due specie completamente diverse. L'IA non è fallita del tutto, ma è peggiorata molto. La sua precisione è scesa, spiegando solo il 37% della varianza. Questo ci dice che, sebbene l'IA abbia imparato alcune regole generali sulle forme degli alberi, si è anche abituata al "gusto" specifico dei batteri che ha studiato. È come uno studente che è bravissimo in matematica ma si confonde quando l'insegnante passa dall'algebra alla geometria.

Quando l'IA affrontava i giganti:
La scoperta più importante, tuttavia, è stata ciò che è accaduto quando l'IA ha affrontato alberi molto più grandi di quelli presenti nel suo set di addestramento. I ricercatori hanno addestrato l'IA su alberi piccoli e medi e poi le hanno chiesto di indovinare la distanza per i massicci alberi con fino a 9.500 isolati. Il risultato? L'IA è crollata. La sua precisione non è solo scesa; è diventata peggiore del semplice indovinare la media. Il modello semplicemente non è riuscito a "estrapolare" o a capire come gestire dimensioni che non aveva mai visto prima. È come insegnare a un bambino a contare fino a 100 e poi chiedergli di contare fino a un milione; non sa come scalare la logica.

La Conclusione

Questo articolo non pretende di aver risolto il problema del confronto tra alberi filogenetici per sempre. Inveve, offre un nuovo strumento potente che funziona incredibilmente bene per alberi di una dimensione e un tipo che ha già visto. Gli autori dimostrano che possiamo addestrare un'IA per approssimare queste complesse distanze biologiche in una frazione di secondo, il che è un grande passo avanti per il monitoraggio delle epidemie.

Tuttano, sono molto chiari riguardo ai confini. L'IA non è una bacchetta magica che funziona su qualsiasi albero di qualsiasi dimensione. Fatica con nuove specie e fallisce completamente quando gli alberi diventano troppo grandi. Gli autori suggeriscono che, per risolvere questo problema, il lavoro futuro dovrà nutrire l'IA con alberi ancora più grandi durante l'addestramento e forse insegnarle a gestire meglio le differenze di dimensione. Indicano anche che, al momento, l'IA indovina solo il numero di movimenti necessari per cambiare un albero in un altro. Un obiettivo futuro sarebbe quello di far sì che l'IA indichi esattamente quali rami devono essere spostati, fornendo agli scienziati una tabella di marcia dei cambiamenti piuttosto che un semplice punteggio di distanza.

In breve, il documento dimosta che le Graph Neural Networks possono essere eccellenti "indovini veloci" per le distanze tra gli alberi, a patto che gli alberi non siano troppo strani o troppo grandi. È un inizio promettente, ma l'IA deve ancora crescere molto prima di poter affrontare le sfide più grandi del settore.