幾何的接尾辞木 : タンパク質3次元構造検索のための新しい索引構造(セッション1)

概要

論文の詳細を見る
タンパク質構造解析はポストゲノム時代の非常に重要な研究分野であり、非常に多くのタンパク質構造が次々と解明されるに従いより高速でより正確な3次元構造検索のための索引構造を設計することが急務となっている。本論文ではタンパク質3次元構造を検索するための幾何的接尾辞木と名づけた新しい索引構造を提案する。このデータ構造を用いることで、クエリーとする3次元構造に対して、RMSD (root mean square deviation)あるいはURMSD (unit-vector root mean square deviation)とよばれる指標による指定値以上に類似するデータベース中のタンパク質の3次元構造の部分構造を効率的にすべて列挙することができる。データベースのサイズをnとするとそれに含まれる部分構造はO(n^2)存在するにも関わらず、幾何的接尾辞木を記憶するのに必要なメモリサイズはO(n)である。また、このデータ構造はナイーブに構築するとO(n^3)の計算が必要であるが、本論文ではO(n^2)の構築アルゴリズムを提案する。さらに効率的な検索アルゴリズムも提案する。最後に簡単な計算機実験を通じてこのデータ構造の有用性を検証する。
2006-03-17