ゲノム情報科学研究教育機構  アブストラクト
Date Oct 18, 2013
Speaker Dr. Tetsuo Shibuya, The University of Tokyo
Title Indexing Protein 3-D Structures for Faster Structural Similarity Queries
Abstract Searching for protein structure-function relationships using three-dimensional (3D) structural coordinates represents a fundamental approach for determining the function of proteins with unknown functions. Since protein structure databases are rapidly growing in size, the development of a fast search method to find similar protein substructures by comparison of protein 3D structures is essential. In this talk, we introduce a new indexing algorithm for fast protein 3-D structure similarity queries based on the root mean square deviatins (RMSDs), the most fundamental similarity measure for protein structure comparisons. The new method runs in O(m + N/m^{0.5}) time, after O(N log N) preprocessing, where N is the database size and m is the query length. It is about 2 to 50 times faster than the previous practically best-known O(N) algorithm, which was also proposed by us, even if we include the preprocessing time. It is almost 20-1000 times faster than the naive comparison algorithm, according to experiments on a huge SCOP database.
「セミナー」に戻る      
 ホーム