接頭辞並べ替え幾何的接尾辞木
スポンサーリンク
概要
- 論文の詳細を見る
タンパク質立体構造解析はポストゲノム時代の最重要課題の1 つであり、近年、それらに対する高速かつ正確な検索アルゴリズムが極めて重要になってきている。幾何的接尾辞木とは、そのような検索のための索引データ構造である。タンパク質立体構造の類似性はRMSD(root mean square deviations)とよばれる指標で計算することが多いが、この幾何的接尾辞木を用いれば、タンパク質立体構造データベースの中からクエリーとのRMSDが一定値以下のすべてのタンパク質をすべて高速に検索することが可能である。本論文では、さらに一歩進めて、この幾何的接尾辞木を拡張した接頭辞並べ替え幾何的接尾辞木(PSGST:prefix-shuffled geometric suffix tree)というデータ構造を提案する。また本論文では、このPSGSTを用いることでもともとの幾何的接尾辞木の検索性能を大幅に上げることができることを実験を通して示す。このデータ構造は、データベース中にクエリー構造と類似した構造が少ない場合には特に良い性能を示す。最も良い例では100倍以上の高速化に成功している。
- 2007-05-11
著者
関連論文
- 線形時間タンパク質3次元構造探索アルゴリズム
- 効率的な部分構造RMSD問い合わせブルゴリズム
- タンパク質ヒンジ構造検出のための高速かつ正確なアルゴリズム
- 接頭辞並べ替え幾何的接尾辞木
- バイオインフォマテイクスの現状と課題(学生/教養のページ)
- 分子合成経路発見のためのグラフタイリングアルゴリズム(セッション2)
- 幾何的接尾辞木 : タンパク質3次元構造検索のための新しい索引構造(セッション1)
- 複数生物学的配列のアラインメントのパラメトリック的考察
- 複数の生物学的配列の準最適アラインメントについて
- Spaced Seedの検索のための索引