A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

あらゆる生命は、そのDNAに刻まれた歴史、すなわち、数千年にわたって集団がいかに移動し、混ざり合い、そして分離してきたかを示す分子の記録を携えています。科学者にとって、この歴史を再構築することは、遺伝的な変異という断片的なピースを集めて、種の家系図という一つの絵を完成させようとする、巨大で断片化されたパズルを組み立てるようなものです。人類の祖先を辿る最も信頼できる方法の一つは、父から息子へとほとんど変化せずに受け継がれる、小さなDNAの断片であるY染色体に注目することです。Y染色体は母親からのDNAと混ざり合うことがないため、明確で途切れることのない系統として機能し、研究者が人類の家系図の深い枝分かれをマッピングすることを可能にします。しかし、遺伝データの量が増大するにつれ、正しい樹形構造を見つけ出す作業は極めて困難になっています。たとえ控えめな人数であっても、彼らを家系図の中に配置する方法の数は膨大であり、標準的なコンピュータが一つひとつの可能性をすべてチェックする能力を超えてしまうのです。この組合せ爆発により、科学者は、素早く最適な答えを推測するものの、それが真の正解であることを保証するわけではない「ヒューリスティクス（発見的な手法）」と呼ばれるショートカットに頼らざるを得なくなっています。

サルデーニャ島のCRS4の研究チームは、二つの異なる戦略を組み合わせることでこの問題に取り組む、新しい計算ワークフローを開発しました。それは、巨大な問題を管理可能な小さな断片に分割し、次に、特殊なタイプの量子に着想を得たアルゴリズムを使用してそれらの断片を解決するという手法です。彼らの研究は、ヒトのY染色体データ、具体的には、一塩基多型として知られる遺伝暗号の一文字の変化に焦点を当てています。研究者たちは、必要な遺伝的変異を欠く72の情報を欠いたサンプルを除去してクリーニングした、150のサンプルを含むデータセットから出発し、分析のために78の男性集団を残しました。その後、彼らはこの新しい手法を用いて進化の樹形図を再構築しました。樹形全体を一度に解決しようとすると、現在のテクノロジーでは複雑すぎるため、彼らはタスクを二つの主要な決定に分割しました。第一に、どのグループの人々が樹形上で共にクラスター（集団）を形成すべきかを決定しました。第二に、時間の方向を示すために、樹形のまさに始まりである「根（ルート）」をどこに配置すべきかを決定しました。

これらの決定を下すために、研究者たちは生物学的な問題を、二次非制約バイナリ最適化問題として知られる数学的な形式へと翻訳しました。平易な言葉で言えば、これは最適な樹形を探すことを、複雑な丘と谷が連なる景観の中で最も低い点を見つけるゲームに変える方法です。ここで、最も低い点は最も可能性の高い家族の歴史を表します。課題は、この景観があまりにも広大で、一度にすべてを探索することができない点にあります。チームの解決策は、ADMM分解と呼ばれる手法を用い、巨大な景観を重なり合う小さなセクションに分割することでした。各セクションは独立して解決され、その後、結果が一つにまとめられ、一貫した全体を形成します。これにより、システムは単一のコンピュータでは処理不可能な規模の問題を扱うことが可能になります。

これらの小さなセクションを解決するために、チームはデジタル・カウンタ・ディアバティック量子最適化と呼ばれる手法を採用しました。このアプローチは、量子力学の原理を用いて、景観の中の最低点を非常に迅速に見つけ出します。他の量子手法が、試行錯誤の遅い反復プロセスを必要とするのに対し、この技術は一度の直接的なパスで解への経路を計算します。研究者たちは、量子プロセッサの挙動を模倣したノイズのないコンピュータ・シミュレーション上で、このワークフローをテストしました。その結果、彼らの手法は、78の集団の家系図を正常に再構築できることが分かりました。生成された樹形図は、アフリカの系統の奥深くに根を置いており、これは人類の起源に関する確立された科学的理解と一致しています。さらに、彼らの新しい手法によって特定されたすべてのグループ分けは、ネイバー・ジョイニング（近隣結合法）と呼ばれる標準的で広く受け入れられている樹形構築技術と一致していましたが、新しい手法は、ネイバー・ジョイニングのリファレンス・ツリーで見つかったグループの40%しか回収できていませんでした。これは、彼らのアプローチが精密である一方で、標準的な手法よりも総クラスター数を少なく特定したことを示しています。

この研究は、大きな問題を分割することと効率的な量子スタイルのソルバーを組み合わせるというハイブリッドなアプローチが、集団ゲノミクスへの実行可能な道であることを示しています。これは、全規模の量子コンピュータが現時点では必要とする大規模でエラーの多いハードウェアを必要とすることなく、従来のショートカットによる推測を超えていく方法を提供します。シミュレートされた量子デバイス上でこれらの困難な樹形再構築問題を解決できることを証明することで、研究者たちは、このテクノロジーが将来、より大きなデータセットに適用される準備ができていることを示しました。彼らの研究は、生の遺伝データを取り込み、特定の遺伝マーカーによって各枝が定義された、根付きで注釈付きの家系図へと変える、明確で段階的なパイプラインを提供しています。この成果は、人類の進化の全容を、近似への依存を減らし、より高い精度でマッピングできる未来へと、分野が確実に進んでいることを示唆しています。