Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

あなたは、巨大で古くから続く家族の謎を解こうとしているところだと想像してください。あなたは、何千人もの人々から書かれた古い手書きの手紙（これがDNAです）の山を持っており、誰が誰と親戚であるかを知るために家系図を描こうとしています。科学者たちも、アウトブレイク（感染症の発生）の最中にウイルスや細菌がどのように広がるかを追跡するために、常にこのようなことを行っています。しかし、ここにはトリッキーな点があります。ドットを結びつけるための数学的なトリックの使い方によって、家系図を描く方法は一つではありません。どの方法を使うかによって、描かれる家族の歴史の絵は少しずつ変わってしまいます。ある樹形図は「従兄弟Aは従兄弟Bに近い」と言いますが、別の樹形図は「実は、彼らは遠い他人同士だ」と言うかもしれません。

どの樹形図がより優れているか、あるいは二つの樹形図がどの程度異なっているかを判断するために、科学者たちはその「距離」を測定する方法を必要としています。これは、同じ街の異なる二つの地図を比較することに似ています。一つの地図にはある道が描かれていても、もう一つの地図ではその道が抜けているかもしれません。生物学の世界において、これらの違いを測定する最も正確な方法は、「サブツリー・プルン・アンド・リグラフト（枝の切り取りと再結合：SPR）」距離と呼ばれます。これは、一つの樹形図の枝を一本切り取って、別の場所に貼り付け直して、もう一方の樹形図と全く同じにするために、何度その操作を行う必要があるかを数えるようなものです。この手法は、時間の経過とともに起こった遺伝的な入れ替わりといった実際の生物学的な動きをカウントするため、非常に精密です。しかし、落とし穴があります。この計算を行うのは非常に難しく、時間がかかるため、数千の葉（数千の細菌を表す）を持つ樹形図の場合、スーパーコンピュータを使っても計算が終わるまでに何年もかかってしまいます。それは、ビーチの大きさを測るために、砂の一粒一粒を数えようとするようなものです。理論的には可能ですが、実用的には不可能です。

ここで物語はエキサイティングになります。研究者たちは、シンプルな問いを投げかけました。「この距離を、不可能に近い数学的計算を行うことなく、素早く推測するようにコンピュータに教えることはできるだろうか？」彼らは、グラフニューラルネットワーク（GNN）と呼ばれる特別な種類の人工知能を構築しました。GNNを、数千組の樹形図のペアを学習し、それらがどのように異なっているかのパターンを見つけ出す、非常に賢い学生だと考えてください。枝を切り取って貼り付けるという重労働を行う代わりに、このAIは樹形図の形状を見て、距離を非常に素早く推測します。この論文は、このAIが樹形図の間の距離を驚くべき精度で予測できることを示していますが、同時に、AIには特定の弱点があることも明らかにしています。それは、学校で学習した時よりもはるかに大きな樹形図に直面した時に苦戦するという点です。

大規模な実験：樹形図を比較するためのAI教育

レナータ・マルティンス・カスタニェイラ氏率いるチームは、現代の疾患追跡で使用される大規模なデータセット（最大9,500個の異なる細菌サンプルを同時に扱う場合もある）を扱えるツールを作成することを目標に、生物学的な家系図を瞬時に比較できるシステムを構築することに乗り出しました。

まず、彼らはトレーニングの場を作る必要がありました。彼らは、クロストリジウム（Clostridium）、サルモネラ（Salmonella）、ビブリオ（Vibrio）、およびストレプトコッカス・ニューモニエ（Streptococcus pneumoniae）という4種類の異なる細菌の遺伝データを集めました。このデータを、90個の分離株から最大9,500個の膨大なグループまで、さまざまなサイズに分割しました。標準的なコンピュータ手法を用いて、このデータから864個の異なる家系図を生成しました。トレーニングを面白くするために、彼らはデータをそのまま使うのではなく、データをわずかにシャッフルして、形状が少し異なる「双子」を作成しました。これにより、比較するための388組の樹形図のペアが得られました。

ここが巧妙な点です。AIに正解を教えるための「教師」が必要でした。完璧で正確な数学（ルート付きSPR距離）は、大きな樹形図に対しては計算が遅すぎるため、彼らはAIが学習するための答えを生成するために、より高速で、わずかに不完全な方法である「ヒューリスティック（賢いショートカット）」を使用しました。このショートカットを信頼する前に、彼らは完璧な数学ができる小さな樹形図でテストを行いました。その結果、ショートカットは実際の答えとほぼ完全に一致していることがわかりました（相関係数は0.98から0.99）。それは完璧ではありませんでした。真の値の約65%から71%程度の値を推測する傾向がありましたが、ランキング（順序付け）は正確でした。もし樹形図Aが樹形図Bよりも樹形図Cが樹形図Dよりも異なっているならば、ショートカットはその通りに判断できました。これは、AIにとって完璧な「代理」教師となりました。

次に、彼らはAIを構築しました。彼らは、サイアミーズ・グラフ・アイソモルフィズム・ネットワーク（Siamese Graph Isomorphism Network: GIN）と呼ばれる特定の種類のニューラルネットワークを使用しました。二人の同一の双子（「サイアミーズ」の部分）が、共に一つの樹形図を見ている様子を想像してください。AIは、各ノード（分岐点や葉）が「私は葉である」「根から遠い」「この種に属している」といった情報を持つIDカードを持っているような、グラフとして各樹形図を分解します。AIはこれらの樹形図を処理し、枝がどのように配置されているかのパターンを探ります。最後に、両方の樹形図からの「思考」を取り込み、結合し、予測される距離を示す単一の数値を吐き出します。

得られた知見

結果は、状況に応じて素晴らしい成功と明確な限界が混在したものでした。

AIがコンフォートゾーンにいるとき：
研究者が、学習した時と同じサイズや種類の樹形図に対してAIをテストしたとき（「イン・ディストリビューション」のシナリオ）、AIは目覚ましい成果を上げました。AIは樹形図間の差異の約87%から90%を説明することができました。簡単に言えば、以前見たことのある二つの樹形図の間の距離を推測するようAIに求めた場合、そのほとんどが正解でした。AIは、すべてのペアに対して平均的な距離を推測するよりも約4倍優れた性能を示しました。これは、AIが樹形図の形状が互いにどのように関連しているかというルールを、真に学習したことを示唆しています。

AIが新しい友人に会ったとき：
チームは、「このAIは、一度も見聞きしたことのない新しい種類の細菌を理解できるだろうか？」と問いかけました。彼らは2種類の細菌でAIを訓練し、全く異なる2種類の細菌でテストを行いました。AIは完全に失敗したわけではありませんが、精度は大幅に低下しました。説明できる分散は約37%に留まりました。これは、AIが樹形図の形状に関する一般的なルールを学習してはいるものの、学習した細菌特有の「風味」にも慣れてしまっていることを意味します。それは、数学が得意な学生が、先生から代数学から幾何学へと授業を変えられた時に混乱してしまうようなものです。

AIが巨人に直面したとき：
しかし、最も重要な発見は、AIが学習セットよりもはるかに大きな樹形図に直面したときに何が起きたかです。研究者は、小規模および中規模の樹形図でAIを訓練し、その後、最大9,500の分離株を持つ巨大な樹形図の距離を推測させました。結果はどうだったでしょうか？AIは崩壊しました。精度は単に低下しただけでなく、平均値を推測するよりも悪くなりました。モデルは、見たことがないサイズを扱うための「外挿（エクストラポレーション）」、つまり論理をスケールアップさせる方法を見つけることができなかったのです。それは、子供に100まで数えることを教えた後に、100万まで数えるように求めるようなものです。彼らは、どうやって規模を拡大するかという論理を知りません。

まとめ

この論文は、樹形図の比較に関する問題を永遠に解決したと主張しているわけではありません。その代わりに、既知のサイズや種類の樹形図に対して非常にうまく機能する、強力な新しいツールを提供しています。著者たちは、AIに巨大な樹形図を学習させることで、疫病の追跡において極めて重要なステップとなる、複雑な生物学的距離を数分の一の速さで近似できることを示しました。

しかし、彼らは境界についても非常に明確に述べています。このAIは、あらゆるサイズのあらゆる樹形図に使える魔法の杖ではありません。新しい種には苦戦し、樹形図が大きすぎると完全に失敗します。著者たちは、これを解決するためには、将来的な研究において、より大きな樹形図をAIに学習させ、サイズの違いをより適切に扱えるようにする必要があると示唆しています。また、現在のAIは、ある樹形図を別の樹形図に変えるために必要な「移動の回数」を推測しているだけであることも指摘しています。将来の目標は、AIが「どの枝」を動かすべきかを正確に指し示せるようにし、単なる距離スコアではなく、変化のロードマップを科学者に提供することです。

要約すると、この論文は、グラフニューラルネットワークが、樹形図が奇妙すぎたり巨大すぎたりしない限り、樹形図の距離を測る優れた「素早い推測者」になり得ることを証明しています。これは有望な出発点ですが、AIがこの分野の最大の課題に対処できるようになるには、まだ成長の余地が多く残されています。