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.
|
|