線形時間タンパク質3次元構造探索アルゴリズム

概要

論文の詳細を見る
RMSD(Root Mean Square Deviation)は、2つの同じ長さの座標列を比較するのに最もよく用いられる指標であり、分子生物学、コンピュータグラフィックス、ロボティクス等の様々な分野で用いられている。本論文では、タンパク質などの分子の3次元立体構造データベースから、クエリーとする立体構造からのRMSDが与えられた閾値よりも小さい部分構造をすべて求める、という最も基本的な問題に対し、平均計算時間が線形時間となる初めてのアルゴリズムを提案する。なお、この問題では、これまで平均計算量を考える試みはまったくなされておらず、本論文はその初めての試みでもある。また、このアルゴリズムは理論的にこれまでのアルゴリズムより高速であるだけでなく、実用上も高速なアルゴリズムであり、タンパク質立体構造データベースPDB上の実験では、従来手法に対し、3.6倍から28倍もの高速化を実現した。また、さらに、平均計算量が高速な検索を実現する索引手法についても提案する。
2009-02-26