A fast diagonalization algorithm to enable singular value decomposition of large matrices for efficient template matching

細胞の目に見えないパズル

巨大で渦巻くスノードームの中に、ある特定の小さなおもちゃが隠されているところを想像してみてください。今度は、そのスノードームが生きている細胞であり、おもちゃがタンパク質分子であり、雪が、混ざり合ってぼやけた状態にある数千もの他の分子の混沌とした混合物であると想像してください。これは、クライオ電子顕微鏡（cryo-EM）と呼ばれる強力な顕微鏡を使用する科学者たちが直面している日常的な課題です。この技術は、細胞の微細な部分が氷の中に閉じ込められるほど急速に細胞を凍結させることで、それらを観察することを可能にします。しかし、細胞は非常に混雑しており、画像も粒状で粗いため、特定のタンパク質を見つけ出すことは、吹雪の中でたった一つの特定の雪の結晶を見つけ出すようなものです。

これを解決するために、科学者は「テンプレートマッチング」と呼ばれる手法を用います。これは、ハイテクな「ウォーリーをさがせ！」のようなものだと考えてください。ただし、漫画のキャラクターを探す代わりに、3D分子を探すのです。コンピュータで生成された完璧な分子モデル（テンプレート）を用意し、それをぼやけた顕微学画像の上でスライドさせながら、あらゆる場所や角度で適合するかどうかをチェックしていきます。問題は、分子が回転したり傾いたりする仕方が非常に多いため、たった一つの画像に対して2,000万通り以上の異なる位置をチェックしなければならないことです。細胞内のすべてのタンパク質に対してこれを行うには、膨大なコンピュータ・パワーが必要となり、大規模に行うことは事実上不可能です。それは、スマートな検索エンジンを使うのではなく、図書館にあるすべての本を、一ページずつすべて確認しながら読もうとするようなものです。

魔法の手品：探索の折り畳み

この論文は、その探索を加速させ、山のような仕事を小さな丘に変えるための巧妙な新しい方法を紹介しています。カリフォルニア大学バークレー校の研究者である著者たちは、膨大な「もしも」のリスト（2,000万通りの位置）には、隠された秘密があることに気づきました。それは「対称性」です。

ピザ生地を空中で回転させている場面を想像してみてください。生地をどのように回転させても、生地自体の形は変わりません。ただ、見た目が回転しているように見えるだけです。これらの顕微鏡画像の世界において、タンパク質を見つけるために使用される数学的処理も同様に振る舞います。画像を回転させると、数学的処理はその答えを回転させますが、問題の核となる「形」は変わりません。著者たちは、この回転の対称性があるため、2,000万もの位置を個別にチェックする必要はないと気づいたのです。その代わりに、数学的なショートカットを使って問題を「折り畳む」ことができます。

彼らは、高速なアルゴリズムを開発しました。それはまるで魔法のデコーダーリング（解読リング）のように機能します。巨大で乱雑なパズルを一度に解こうとする代わりに、このアルゴリズムは、画像がどのように回転するかに基づいて、問題をより小さく管理しやすい塊へと分解します。これは、巨大で扱いづらい行列（あらゆる可能性を表す巨大な数字のグリッド）を、より小さく整理された一連のパーツへと変換します。この回転の対称性を活用することで、彼らはフルサイズの、手に負えないほどの巨大なグリッドを構築することなく、最も重要なパターン（特異値および特異ベクトルと呼ばれます）を計算することができます。

結果は驚異的です。彼らのテストでは、この新手法は誤差を極めて低く（わずか0.01%）保ったまま、データを3,500倍の係数で圧縮することができました。これを比較すると、もし従来の方法で一つの細胞画像から一つのタイプのタンパク質を見つけるのに4時間かかっていたとしたら、この新手法はその作業をほんの一瞬で完了できることになります。ある特定のテストでは、この新しいアルゴリズムは、検出されたすべての特徴量に対して205倍速く動作し、従来のメソッドが発見できたよりも22.5倍多くの特徴量を捉えることができました。

著者らはまた、このトリックが大規模なスケールでも機能することを示しました。彼らは、タンパク質がどのような姿になり得るかをカバーする、非常に高い解像度（2オングストローム）のテンプレートマッチング行列を、わずか14分で分解することに成功しました。これは、以前であればあまりにもコストがかかり、時間がかかりすぎて試行すらできなかった作業です。論文では、フルスケールの行列を標準的なコンピュータツールで直接解くことは依然として困難であると述べていますが、この新しい「対称性を利用した」手法によって、それが実現可能なものとなりました。これは単にスピードを上げるだけでなく、細胞内のより多くのタンパク質を発見するための扉を開き、分子レベルでの生命の仕組みの完全な地図を作成する助けとなります。著者らは、これが「マルチプレシジョン（多精度）」探索、つまりコンピュータが広範な一致を素早くスキャンし、その後で高詳細なチェックへとズームインできる仕組みにつながると示唆しており、細胞装置の研究をこれまで以上に迅速かつ包括的なものにすると述べています。