W54 Nucleic Acids Research, 2010, Vol. 38, Web Server issue linked by coils of diﬀerent lengths in a protein structure family. These multiple common substructures, diﬀerent from canonical secondary structures, might be used not only for the discovery of new domains or folds in the structure database but also for the identiﬁcation of func- tional and evolutionary relationships of protein structures since they are more conserved than other regions (10–12). However, aligning protein substructures is known to be a non-deterministic polynomial (NP) time-hard problem, and the existing methods are rarely designed to handle such kind of problem. The problem becomes more challenging as one considers the growing rates at which new protein structures are being added to the database. Hence, the main goal of ProteinDBS v2.0 is to tackle these issues and equip the community with user-friendly tools that can deliver eﬃcient and accurate results for protein structure comparison and search. ProteinDBS v2.0 has been optimized in the following aspects: (i) The global comparison method introduces a novel knowledge-based feature extraction as well as online database indexing (13). (ii) The newly designed approach for local comparisons applies information retrieval algorithms to extract frequently occurring substructure patterns and utilizes an index tree to eﬃciently manage the data (14). (iii) The database of global comparisons is being updated weekly from the PDB website, and the database of local comparisons has been generated using the latest release of SCOP 1.75 (15) and the non-redundant protein data set PDBSelect (16). (iv) The eﬃciency of ProteinDBS has been signiﬁcantly enhanced to meet the requirements of large-scale protein database searching. To our knowledge, ProteinDBS v2.0 is the only server that can simultaneously support large-scale comparison and search of globally and locally similar protein structures. MATERIALS AND METHODS The system architecture of ProteinDBS v2.0, as shown in Figure 1, contains ﬁve modules: (i) protein structure database management; (ii) data pre-processing; (iii) query interface; (iv) distributed search engine; and (v) re- trieval results visualization. A system tutorial can be viewed at the ProteinDBS web site. Protein structure database management ProteinDBS v2.0 maintains two independent databases of protein structures for global and local comparisons. The database of global comparisons is updated weekly and newly added protein structures are automatically down- loaded from the PDB ftp site (ftp://ftp.wwpdb.org/ pub/pdb/). For each new protein structure, a 2D distance matrix is generated from 3D coordinates of the protein chains. The distance matrices are empirically proven capable of representing global protein structural topologies. From the distance matrices, 33 features are then extracted, and a tree structure, an M-Tree (17), is utilized to index the multi-dimensional data. The database of local comparisons is a non-redundant data set of protein chains selected from PDBSelect (16) and SCOP v1.75 (15). When new data set is released, sub- structure units, deﬁned as continuous fragments of backbone with ﬁxed length, are ﬁrst identiﬁed from each protein in the data set using a sliding window. Our as- sumption is that a protein containing similar substructure units should be further investigated to ﬁnd long common substructures. In order to eﬃciently search proteins with similar substructures, the system ﬁrst organizes structur- ally similar substructure units into a cluster and selects a representative for each cluster. The representative is assigned a label called ‘term’ in our server. The system then maps the protein structure into a series of terms by comparing the substructure units with the pre-deﬁned sub- structure representative of each cluster. Finally, the system utilizes an M-Tree to index the terms of the entire database of proteins to facilitate fast searches using infor- mation retrieval techniques. Query interface There are two types of query methods, as shown in the top block of Figure 1: local-to-local and global-to-global search. Both methods feature ‘query by ID’ and ‘query by structure example’. Using an internet browser, a user can upload a new protein chain structure in PDB format or provide a PDB ID contained in the protein database to ﬁnd similar protein structures. Data pre-processing and search engine The global-to-global search, as mentioned previously, ﬁrst maps the query protein structures into a 2D distance matrix and extracts features from the distance matrix. In this way, the query protein can be represented by a data point in the feature space populated by the entire protein database. Thus, one-against-all global comparison is analogous to searching nearest neighbors in feature space, and such a search can be completed in real time. For the local-to-local search, the system ﬁrst extracts substructure units of the query protein and then clusters them into groups. From the index of database terms, the system ﬁnds candidate proteins for comparison and ﬁlters out those proteins without common substructures. To achieve accurate substructure comparison, the system deploys a coarse-to-ﬁne strategy to align the query protein and a database protein. Speciﬁcally, the system ﬁrst ﬁnds relevant matches at the substructure level with a customized dynamic programming algorithm (14) and then reﬁnes the substructure alignment at the atomic level. This two-level alignment framework is a tradeoﬀ allowing the system to achieve high eﬃciency without sacriﬁcing accuracy of results. Due to page limitations, interested readers are referred to (13,14) for further discussion of the detailed algorithms. Retrieval results visualization The global comparison retrieval results for a query chain 1o7j_A are shown in Figure 2. A set of top-ranked