接頭辞並べ替え幾何的接尾辞木

• Item type: SIG Technical Reports(1)
• 公開日: 2007-05-11
• タイトル: 接頭辞並べ替え幾何的接尾辞木
• タイトル / 言語: en
• タイトル: Prefix-Shuffled Geometric Suffix Tree
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学医科学研究所ヒトゲノム解析センター
• 著者所属(英): en
• 著者所属(英): Human Genome Center, Institute of Medical Science, University of Tokyo
• 著者名: 渋谷, 哲朗
• 著者名(英): Tetsuo, SHIBUYA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: タンパク質立体構造解析はポストゲノム時代の最重要課題の１つであり、近年、それらに対する高速かつ正確な検索アルゴリズムが極めて重要になってきている。幾何的接尾辞木とは、そのような検索のための索引データ構造である。タンパク質立体構造の類似性は RMSD (root mean square deviations)とよばれる指標で計算することが多いが、この幾何的接尾辞木を用いれば、タンパク質立体構造データベースの中からクエリーとの RMSD が一定値以下のすべてのタンパク質をすべて高速に検索することが可能である。本論文では、さらに一歩進めて、この幾何的接尾辞木を拡張した接頭辞並べ替え幾何的接尾辞木 (PSGST:prefix-shuffled geometric suffix tree)というデータ構造を提案する。また本論文では、この PSGST を用いることでもともとの幾何的接尾辞木の検索性能を大幅に上げることができることを実験を通して示す。このデータ構造は、データベース中にクエリー構造と類似した構造が少ない場合には特に良い性能を示す。最も良い例では100倍以上の高速化に成功している。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate index data structures for such 3-D structures are highly desired for research on proteins. The geometric suffix tree is a very sophisticated index structure that enables fast and accurate search on protein 3-D structures. By using it, we can search from 3-D structure databases for all the substructures whose RMSDs (root mean square deviations) to a given query 3-D structure are not larger than a given bound. In this paper, we propose a new data structure based on the geometric suffix tree whose query performance is much better than the original geometric suffix tree. We call the modified data structure the prefix-shuffled geometric suffix tree (or PSGST for short). According to our experiments, the PSGST outperforms the geometric suffix tree in most cases. The PSGST shows its best performance when the database does not have many substructures similar to the query. The query is sometimes 100 times faster than the original geometric suffix trees in such cases.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 40(2007-AL-112), p. 1-8, 発行日 2007-05-11
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会