ملخص: 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. This article proposes a new data structure for indexing protein 3-D structures. For strings, there are many efficient indexing structures such as suffix trees, but it has been considered very difficult to design such sophisticated data structures against 3-D structures like proteins. Our index structure is based on the suffix tree and is called the geometric suffix tree. By using the geometric suffix tree for a set of protein structures, we can exactly search for all of their substructures whose RMSDs (root mean square deviations) or URMSDs (unit-vector root mean square deviations) to a given query 3-D structure are not larger than a given bound. Though there are O(N2) substructures in a structure of size N, our data structure requires only O(N) space for indexing all the substructures. We propose an O(N2) construction algorithm for it, while a naive algorithm would require O(N3) time to construct it. Moreover we propose an efficient search algorithm. Experiments show that we can search for similar structures much faster than previous algorithms if the RMSD threshold is not larger than 1 ° A. The experiments also show that the construction time of the geometric suffix tree is practically almost linear to the size of the database, when applied to a protein structure database. Categories and Subject Descriptors: E.1 [Data Structures]: Trees; F.2.2 [Analysis of Algorithms and Problem Comlexity]: Nonnumerical Algorithms and Problems—Pattern matching; H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing—Indexing methods; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms, languages, and systems; J.3 [Life and Medical Sciences]: Biology and genetics General Terms: Algorithms

لغة: إنجليزية