Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

당신이 거대한 고대의 가족 미스터리를 풀려고 노력하고 있다고 상상해 보세요. 당신은 수천 명의 사람으로부터 온 오래된 손편지(DNA) 더미를 가지고 있으며, 누가 누구와 친척인지 알아보기 위해 가계도를 그리고 싶어 합니다. 과학자들은 질병 발생 중에 바이러스나 박테리아가 어떻게 퍼지는지 추적하기 위해 항상 이와 같은 일을 합니다. 하지만 까다로운 점은, 나무를 그리는 방법이 단 한 가지가 아니라는 것입니다. 점들을 연결하는 데 어떤 수학적 기법을 사용하느냐에 따라 가족사의 모습이 조금씩 달라질 수 있습니다. 때로는 어떤 나무는 "사촌 A가 사촌 B와 가깝다"라고 말하지만, 다른 나무는 "사실, 그들은 먼 타인이다"라고 말하기도 합니다.

어떤 나무가 더 나은지, 혹은 두 나무가 서로 얼마나 다른지 파악하기 위해, 과학자들은 그 사이의 '거리'를 측정하는 방법이 필요합니다. 이것은 마치 같은 도시의 서로 다른 두 지도를 비교하는 것과 같습니다. 한 지도는 다른 지도가 놓친 도로를 보여줄 수도 있습니다. 생물학의 세계에서 두 나무 사이의 차이를 측정하는 가장 정확한 방법은 '서브트리 가지치기 및 재부착(Subtree Prune and Regraft, SPR)' 거리라고 불립니다. 이것은 마치 "한 나무의 가지를 하나 잘라내어 다른 곳에 붙여서 다른 나무와 똑같이 만들려면 몇 번이나 반복해야 하는가?"라고 묻는 것과 같습니다. 이 방법은 시간이 흐름에 따라 일어난 유전적 교환과 같은 실제 생물학적 움직임을 계산하기 때문에 매우 정밀합니다. 하지만 문제가 있습니다. 이 수학적 계산은 너무 어렵고 느려서, 수천 개의 잎(수천 마리의 박테리아를 나타냄)을 가진 나무의 경우 슈퍼컴퓨터로도 몇 년이 걸릴 수 있습니다. 이는 해변의 크기를 측정하기 위해 모래알 하나하나를 세는 것과 같습니다. 이론적으로는 가능하지만, 실제로는 불가능한 일입니다.

여기서 이야기는 흥미진진해집니다. 연구진은 다음과 같은 단순한 질문을 던졌습니다: "우리가 불가능한 수학 계산을 하지 않고도, 컴퓨터에게 이 거리를 빠르게 추측하도록 가르칠 수 있을까?" 그들은 그래프 신경망(Graph Neural Network, GNN)이라는 특별한 종류의 인공지능을 구축했습니다. GNN을 당신이 패턴을 학습하는 아주 똑똑한 학생이라고 생각해보세요. 이 학생은 수천 쌍의 나무를 공부하여 그들이 얼마나 다른지 그 패턴을 파악하는 법을 배웠습니다. 나무의 형태를 직접 자르고 붙이는 무겁고 느린 작업 대신, AI는 나무의 모양을 보고 거리를 매우 빠르게 추측합니다. 논문은 이 AI가 나무 사이의 거리를 놀라운 정확도로 예측할 수 있음을 보여주지만, 동시에 AI의 구체적인 약점도 밝혀냈습니다. 바로 학교에서 공부했던 것보다 훨씬 더 큰 나무를 보았을 때 어려움을 겪는다는 점입니다.

거대한 실험: 나무를 비교하도록 AI를 가르치기

레나타 마르틴스 카스타네이라(Renata Martins Castanheira)와 동료들이 이끄는 이 팀은 생물학적 가계도를 거의 즉각적인 시간에 비교할 수 있는 시스템을 구축하고자 했습니다. 그들의 목표는 과학자들이 한 번에 최대 9,500개의 서로 다른 박테리아 샘 샘플을 조사할 수 있는 현대 질병 추적의 거대한 데이터셋을 처리할 수 있는 도구를 만드는 것이었습니다.

먼저, 그들은 훈련장을 만들어야 했습니다. 그들은 네 가지 다른 유형의 박테리아(Clostridium, Salmonella, Vibrio, Streptococcus pneumoniae)로부터 유전 데이터를 수집했습니다. 이 데이터를 90개의 분리주부터 최대 9,500개의 거대한 그룹에 이르기까지 다양한 크기의 그룹으로 나누었습니다. 표준적인 컴퓨터 방법을 사용하여, 이 데이터로부터 864개의 서로 다른 가계도를 생성했습니다. 훈련을 흥미롭게 만들기 위해, 그들은 데이터를 있는 그대로 사용하지 않고, 데이터를 약간 섞어서 형태가 조금씩 다른 '쌍둥이'를 만들어냈습니다. 이를 통해 비교할 수 있는 388쌍의 나무를 얻었습니다.

여기에는 영리한 부분이 있습니다. AI에게 정답이 무엇인지 알려줄 '선생님'이 필요했습니다. 완벽하고 정확한 수학(루티드 SPR 거리)은 큰 나무에 대해 계산하기에 너무 느리기 때문에, 그들은 AI가 학습할 수 있도록 정답을 생성하기 위해 '휴리스틱(heuristic, 스마트한 지름길)'이라 불리는 더 빠르고 약간은 덜 완벽한 방법을 사용했습니다. 이 지름길을 신뢰하기 전에, 그들은 완벽한 수학을 수행할 수 있는 작은 나무들에서 이 방법을 테스트했습니다. 그 결과, 이 지름길은 실제 정답과 거의 완벽하게 일치했습니다(상관관계 0.98 ~ 0.99). 완벽하지는 않았습니다. 실제 값의 약 65%에서 71% 정도로 다소 낮게 예측하는 경향이 있었지만, 순위는 정확했습니다. 만약 나무 A가 나무 B보다 나무 C가 나무 D보다 더 다르다면, 이 지름길은 그 사실을 알고 있었습니다. 이 덕분에 이 지름길은 AI를 위한 완벽한 '대리(surrogate)' 선생님이 될 수 있었습니다.

다음으로, 그들은 AI를 구축했습니다. 그들은 시암 그래프 아이소모피즘 네트워크(Siamese Graph Isomorphism Network, GIN)라는 특정 유형의 신경망을 사용했습니다. 두 명의 똑같은 쌍둥이(시암 부분)가 각각 나무를 보고 있다고 상상해 보세요. AI는 각 나무를 그래프로 분해하며, 여기서 모든 노드(가지점 또는 잎)는 "나는 잎이다", "나는 뿌리에서 멀다", 또는 "나는 이 종에 속한다"와 같은 정보가 담긴 작은 ID 카드를 가집니다. AI는 이 나무들을 처리하며 가지가 배치된 방식의 패턴을 찾습니다. 마지막으로, AI는 두 나무로부터 얻은 '생각'을 결합하여 두 나무 사이의 예측된 거리를 나타내는 하나의 숫자를 내놓습니다.

그들이 발견한 것

결과는 상황에 따라 큰 성공과 명확한 한계가 섞여 있었습니다.

AI가 자신의 안락한 구역에 머물 때:
연구진이 AI를 학습했던 것과 크기 및 유형이 유사한 나무들로 테스트했을 때(in-distribution 시나리오), AI는 눈부신 성과를 보였습니다. AI는 나무 사이의 차이를 약 87%에서 90%까지 설명할 수 있었습니다. 간단히 말해, AI에게 이전에 본 적 있는 두 나무 사이의 거리를 맞히라고 하면 대부분의 경우 정답을 맞혔습니다. 이는 모든 쌍에 대해 평균 거리를 추측하는 것보다 약 4배 더 뛰어난 성능이었습니다. 이는 AI가 나무 모양이 서로 어떻게 연관되는지에 대한 규칙을 진정으로 학습했음을 시사합니다.

AI가 새로운 친구들을 만났을 때:
팀은 "이 AI가 한 번도 본 적 없는 새로운 유형의 박테리아를 이해할 수 있을까?"라고 물었습니다. 그들은 두 종의 박테리아로 AI를 훈련시킨 뒤, 완전히 다른 두 종으로 테스트했습니다. AI는 완전히 실패하지는 않았지만, 성능이 훨씬 떨어졌습니다. 변동성을 약 37%만 설명할 수 있었습니다. 이는 AI가 나무 모양에 대한 일반적인 규칙은 배웠지만, 자신이 공부한 박테리아 특유의 '풍미'에도 익숙해져 있었다는 것을 의미합니다. 이는 마치 수학은 잘하지만 선생님이 대수학에서 기하학으로 과목을 바꾸면 혼란스러워하는 학생과 같습니다.

AI가 거인들을 마주했을 때:
그러나 가장 중요한 발견은 AI가 훈련 세트보다 훨씬 큰 나무들을 마주했을 때 일어난 일이었습니다. 연구진은 작고 중간 크기의 나무들로 AI를 훈련시킨 뒤, 최대 9,500개의 분리주를 가진 거대한 나무들에 대한 거리를 예측하도록 했습니다. 결과는 어떠했을까요? AI는 무너졌습니다. 정확도가 단순히 떨어진 것이 아니라, 평균값을 추측하는 것보다도 못하게 되었습니다. 모델은 규모를 키워 적용하는 법, 즉 '외삽(extrapolate)'하는 법을 전혀 알지 못했습니다. 이는 아이에게 100까지 세는 법을 가르친 뒤 백만까지 세어보라고 요구하는 것과 같습니다. 아이는 규모를 키워 논리를 적용하는 법을 모르는 것입니다.

요약

이 논문은 나무를 비교하는 문제를 영원히 해결했다고 주장하는 것이 아닙니다. 대신, 이미 본 적 있는 크기와 유형의 나무에 대해서는 놀라울 정도로 잘 작동하는 강력한 새로운 도구를 제안합니다. 저자들은 우리가 이미 본 적 있는 크기와 유형의 나무에 대해 AI를 사용하여 복잡한 생물학적 거리를 순식간에 근사할 수 있음을 보여주며, 이는 전염병 추적에 있어 큰 진전입니다.

하지만 저자들은 그 한계를 매우 명확히 밝히고 있습니다. 이 AI는 어떤 크기의 어떤 나무라도 다룰 수 있는 마법 지팡이가 아닙니다. 새로운 종에 대해서는 어려움을 겪고, 나무가 너무 커지면 완전히 실패합니다. 저자들은 이를 해결하기 위해 향후 연구에서 더 큰 나무들을 AI에게 학습시키고, 크기 차이를 더 잘 다룰 수 있도록 가르쳐야 한다고 제안합니다. 또한, 현재의 AI는 단지 한 나무를 다른 나무로 바꾸는 데 필요한 '움직임의 횟수'만을 추측할 뿐이라는 점도 지적했습니다. 향후 목표는 AI가 단순히 거리 점수를 주는 것을 넘어, 정확히 '어떤 가지'를 옮겨야 하는지 짚어주어 과학자들에게 변화의 로드맵을 제공하는 것입니다.

요약하자면, 이 논문은 그래프 신경망이 나무가 너무 이상하거나 너무 크지만 않다면 나무 간의 거리를 예측하는 훌륭한 '빠른 추측가'가 될 수 있음을 증명합니다. 이는 유망한 시작이지만, 이 분야의 가장 큰 도전 과제들을 다루기 위해서는 AI가 아직 성장해야 할 부분이 많다는 것을 보여줍니다.