効率的な部分構造RMSD問い合わせブルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
タンパク質の立体構造を比較するために最もよく用いられる尺度はRMSD(root mean square deviation)とよばれる尺度である。本論文では、与えられた2つの立体構造に対し、その部分構造同士のRMSDの問い合わせに対し高速に回答するふたつのアルゴリズムを提案する。ひとつめのアルゴリズムでは、すでにアラインメントされた2つの構造に対し、その部分構造同士のRMSDを定数時間で求めるための、線形時間で構築できるデータ構造を提案する。ふたつめのアルゴリズムでは、アラインメントされていない構造同士の任意の同じ長さの部分構造同士のRMSDをO(γ)時間で求めるための、O(nm log γ/γ)時間、O(nm/γ)空間で求めることのできるデータ構造を提案する。さらに本論文では、この手法がRMSDだけでなく、URMSDという別の尺度に関しても用いることができることも示す。
- 2007-09-21
著者
関連論文
- 線形時間タンパク質3次元構造探索アルゴリズム
- 効率的な部分構造RMSD問い合わせブルゴリズム
- タンパク質ヒンジ構造検出のための高速かつ正確なアルゴリズム
- 接頭辞並べ替え幾何的接尾辞木
- バイオインフォマテイクスの現状と課題(学生/教養のページ)
- 分子合成経路発見のためのグラフタイリングアルゴリズム(セッション2)
- 幾何的接尾辞木 : タンパク質3次元構造検索のための新しい索引構造(セッション1)
- 複数生物学的配列のアラインメントのパラメトリック的考察
- 複数の生物学的配列の準最適アラインメントについて
- Spaced Seedの検索のための索引