Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

Imagine que você está tentando resolver um mistério familiar antigo e massivo. Você tem uma pilha de cartas antigas, escritas à mão (o DNA), de milhares de pessoas, e quer desenhar uma árvore genealógica para ver quem é parente de quem. Cientistas fazem isso o tempo todo para rastrear como vírus ou bactérias se espalham durante um surto. Mas aqui está a parte complicada: não existe apenas uma maneira de desenhar a árvore. Dependendo do truque matemático que você usar para conectar os pontos, pode obter uma imagem ligeiramente diferente da história familiar. Às vezes, uma árvore diz "o Primo A é próximo do Primo B", enquanto outra árvore diz "na verdade, eles são estranhos distantes".

Para descobrir qual árvore é melhor, ou quão diferentes duas árvores são uma da outra, os cientistas precisam de uma forma de medir a "distância" entre elas. Pense nisso como comparar dois mapas diferentes da mesma cidade. Um mapa pode mostrar uma estrada que o outro omite. No mundo da biologia, a maneira mais precisa de medir essa diferença é chamada de distância de "Subtree Prune and Regraft" (SPR). É como perguntar: "Quantas vezes eu tenho que cortar um galho de uma árvore e colá-lo em um lugar diferente para que ela fique exatamente igual à outra?" Este método é incrivelmente preciso porque conta os movimentos biológicos reais, como trocas genéticas, que ocorreram ao longo do tempo. No entanto, há um porém: fazer essa matemática é tão difícil e lenta que, para uma árvore com milhares de folhas (representando milhares de bactérias), levaria um supercomputador anos para terminar o cálculo. É como tentar contar cada grão de areia em uma praia para medir o tamanho da praia; é possível em teoria, mas praticamente impossível.

É aqui que a história fica emocionante. Os pesquisadores deste artigo fizeram uma pergunta simples: "Podemos ensinar um computador a adivinhar essa distância rapidamente, sem fazer a matemática impossível?" Eles construíram um tipo especial de inteligência artificial chamado Redes Neurais de Grafos (GNN). Você pode pensar nesta IA como um aluno superinteligente que estudou milhares de pares de árvores e aprendeu a identificar os padrões de como elas diferem entre si. Em vez de fazer o trabalho pesado e lento de cortar e colar galhos, a IA observa a forma das árvores e faz um palpite muito rápido. O artigo mostra que esta IA consegue aprender a prever a distância entre árvores com uma precisão surpreendente, mas também revela que a IA tem uma fraqueza específica: ela tem dificuldade quando vê árvores muito maiores do que as que estudou na escola.

O Grande Experimento: Ensinando a IA a Comparar Árvores

A equipe por trás deste estudo, liderada por Renata Martins Castanheira e seus colegas, propôs-se a construir um sistema que pudesse comparar essas árvores genealógicas biológicas em tempo quase instantâneo. O objetivo era criar uma ferramenta que pudesse lidar com os enormes conjuntos de dados usados no rastreamento de doenças moderno, onde os cientistas podem estar analisando até 9.500 amostras bacterianas de uma só vez.

Primeiro, eles tiveram que construir um campo de treinamento. Eles reuniram dados genéticos de quatro tipos diferentes de bactérias: Clostridium, Salmonella, Vibrio e Streptococcus pneumoniae. Eles fatiaram esses dados em grupos de diferentes tamanhos, variando de pequenos grupos de 90 isolados até grupos massivos de até 9.500. Usando métodos computacionais padrão, eles geraram 864 árvores genealógicas diferentes a partir desses dados. Para tornar o treinamento interessante, eles não usaram as árvores como estavam; eles embaralharam os dados ligeiramente para criar "gêmeos" com formas um pouco diferentes. Isso lhes deu 388 pares de árvores para comparar.

Aqui está a parte inteligente: eles precisavam de um "professor" para dizer à IA qual era a resposta correta. Como a matemática perfeita e exata (a distância "rooted SPR") é lenta demais para calcular para árvores grandes, eles usaram um método um pouco menos perfeito chamado "heurística" (um atalho inteligente) para gerar as respostas para a IA aprender. Antes de confiar nesse atalho, eles o testaram em árvores pequenas, onde podiam realizar a matemática perfeita. Eles descobriram que o atalho estava quase perfeitamente alinhado com a resposta real, com uma correlação de 0,98 a 0,99. Não era perfeito — tendia a adivinhar números um pouco abaixo do valor real (cerca de 65% a 71% do valor verdadeiro) — mas a classificação estava correta. Se a Árvore A era mais diferente da Árvore B do que a Árvore C era da Árvore D, o atalho sabia disso. Isso o tornou um "substituto" perfeito para o professor da IA.

Em seguida, eles construíram a IA. Eles usaram um tipo específico de rede neural chamada Rede de Isomorfismo de Grafo Siamesa (GIN). Imagine dois gêmeos idênticos (a parte "Siamesa") que estão olhando para uma árvore. A IA decompõe cada árvore em um grafo, onde cada nó (ponto de ramificação ou folha) tem um pequeno cartão de identificação com informações como "Eu sou uma folha", "Estou longe da raiz" ou "Eu pertenço a esta espécie". A IA então processa essas árvores, procurando padrões na forma como os galhos estão organizados. Por fim, ela pega os "pensamentos" de ambas as árvores, combina-os e cospe um único número: a distância prevista entre elas.

O Que Eles Descobriram

Os resultados foram uma mistura de grande sucesso e limitações claras, dependendo da situação.

Quando a IA permaneceu em sua zona de conforto:
Quando os pesquisadores testaram a IA em árvores de tamanho e tipo semelhantes aos que ela estudou (o cenário "dentro da distribuição"), ela teve um desempenho brilhante. Ela conseguiu explicar cerca de 87% a 90% das diferenças entre as árvores. Em termos simples, se você pedisse à IA para adivinhar a distância entre duas árvores que ela já tinha visto antes, ela estaria certa na maioria das vezes. Ela foi cerca de quatro vezes melhor do que apenas adivinhar a distância média para cada par. Isso sugere que a IA realmente aprendeu as regras de como as formas das árvores se relacionam entre si.

Quando a IA conheceu novos amigos:
A equipe então perguntou: "Esta IA consegue entender um novo tipo de bactéria que ela nunca viu?" Eles treinaram a IA em duas espécies e a testaram em duas completamente diferentes. A IA não falhou totalmente, mas seu desempenho piorou consideravelmente. Sua precisão caiu, explicando apenas cerca de 37% da variância. Isso nos diz que, embora a IA tenha aprendido algumas regras gerais sobre as formas das árvores, ela também se acostumou com o "sabor" específico das bactérias que estudou. É como um aluno que é ótimo em matemática, mas fica confuso quando o professor muda de álgebra para geometria.

Quando a IA enfrentou gigantes:
A descoberta mais importante, no entanto, foi o que aconteceu quando a IA enfrentou árvores muito maiores do que as de seu conjunto de treinamento. Os pesquisadores treinaram a IA com árvores pequenas e médias e depois pediram que ela adivinhasse a distância para as árvores massivas com até 9.500 isolados. O resultado? A IA colapsou. Sua precisão não apenas caiu; tornou-se pior do que apenas adivinhar a média. O modelo simplesmente não conseguiu "extrapolar" ou entender como lidar com tamanhos que nunca tinha visto antes. É como ensinar uma criança a contar até 100 e depois pedir que ela conte até um milhão; ela não sabe como escalar a lógica.

A Conclusão

Este artigo não afirma ter resolvido o problema de comparar árvores filogenéticas para sempre. Em vez disso, oferece uma nova ferramenta poderosa que funciona incrivelmente bem para árvores de um tamanho e tipo que ela já viu. Os autores mostram que podemos treinar uma IA para aproximar essas complexas distâncias biológicas em uma fração de segundo, o que é um grande passo à frente para o rastreamento de epidemias.

No entanto, eles são muito claros sobre os limites. A IA não é uma varinha mágica que funciona em qualquer árvore de qualquer tamanho. Ela tem dificuldades com novas espécies e falha completamente quando as árvores ficam grandes demais. Os autores sugerem que, para corrigir isso, o trabalho futuro precisa alimentar a IA com árvores ainda maiores durante o treinamento e talvez ensiná-la a lidar melhor com as diferenças de tamanho. Eles também apontam que, no momento, a IA apenas adivinha o número de movimentos necessários para mudar uma árvore para outra. Um objetivo futuro seria fazer com que a IA apontasse exatamente quais galhos precisam ser movidos, dando aos cientistas um roteiro das mudanças, em vez de apenas uma pontuação de distância.

Em suma, o artigo prova que as Redes Neurais de Grafos podem ser excelentes "adivinhadores rápidos" para distâncias de árvores, desde que as árvores não sejam muito estranhas ou muito grandes. É um começo promissor, mas a IA ainda tem muito o que crescer antes de poder lidar com os maiores desafios da área.