title: LB3D: a protein three-dimensional substructure search program based on the lower bound of a root mean square deviation value.
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 article, we present a novel protein 3D structure search method to find all substructures with root mean square deviations (RMSDs) to the query structure that are lower than a given threshold value. Our new algorithm 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. The new method is 1.8-41.6 times faster than the practically best known O(N) algorithm, according to computational experiments using a huge database (i.e., >20,000,000 C-alpha coordinates).
authors.affiliation: School of Pharmacy, Kitasato University, Tokyo, Japan.
authors.forename: Genki
authors.initials: G
authors.lastname: Terashi
authors.forename: Tetsuo
authors.initials: T
authors.lastname: Shibuya
authors.forename: Mayuko
authors.initials: M
authors.lastname: Takeda-Shitaka
mesh_terms: D000465:Algorithms; D030562:Databases, Protein; D011487:Protein Conformation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*; D040901:Proteomics / Q000379:methods*; D057386:Search Engine / Q000379:methods*; D012984:Software
chemical_list: D011506:Proteins