1 INTRODUCTION {#SEC1}
==============

Following huge efforts from the structural genomics research community, protein structure databases are ever expanding. Whenever a new protein structure is determined, an important step is to identify its structural neighbors, which can provide important clues about its function and evolutionary linkages. Since the protein structure is relatively more robust than sequence during evolution, structure comparison methods can discover remote homologous proteins for a given protein. They also play a key role in understanding the diversity of structure space by analyzing the existing structure databases. In order to derive interesting scientific insights from the vast structure databases available now, highly efficient methods for comparing protein structures are required.

The success of structure comparison methods can be measured based on their effectiveness in detecting closely and remotely homologous proteins ([@B20]). The closely homologous proteins have similar structures with relatively lesser number of insertions and deletions. On the other hand, remote homologs possess significantly different structures. The similarity in these cases can be inferred based on the similarity of structural fragments. Fragment level protein structure comparison works well in practice as demonstrated by several methods ([@B3]; [@B9]; [@B14]; [@B23]). The first fragment-based comparison method was proposed by Remington and Mathews, which performs rigid body superposition of fixed length backbone fragments from individual proteins ([@B14]). The rigid body superposition was later used by Zuker and Somorjai to define the distance between backbone fragments while comparing them using dynamic programming ([@B23]). The fragment-based structure comparison was also used in identification and ranking of local features ([@B9]). For further details, the readers are referred to an excellent review paper by [@B20]). Recently, researchers proposed an interesting vector space representation of protein structures using fragments as the bases ([@B3]). The method, FragBag, appears to perform the task of retrieving similar structures efficiently and is the state-of-the-art method in fragment-based structure comparison.

FragBag represents each structure as a bag of fragments, which is the most basic model of retrieval proposed in text literature. The success of FragBag opens up many interesting avenues, where advanced language modeling techniques proposed in Information Retrieval (IR)/Statistical Natural Language Processing (NLP) can be adopted for representing protein structures. Such approaches are expected to achieve better performance in terms of efficiency and accuracy of identifying structural homologs. The article focuses on two important problems in this context: (i) effective protein structure representation that captures inherent relationship between fragments and facilitates efficient comparison between the structures and (ii) effective framework to address different retrieval requirements. We propose a new representation for protein structures based on latent dirichlet allocation (LDA) ([@B2]). LDA models a collection of discrete objects as a mixture of latent topics, and has been shown to work remarkably well in text and image retrieval domain. The success of LDA in text domain is attributed to effective capturing of relationship between words. Drawing a parallel, here we demonstrate that LDA indeed models relationships between fragments in protein structures effectively and achieves a competitive performance with state-of-the-art structural methods at a fraction of the computation costs. Another important contribution of this work is that we propose multi-viewpoint homology detection framework to effectively find close, as well as, remote homologous proteins for a query protein structure. This is the first attempt to adopt advanced models from IR and statistical NLP for addressing protein structure comparison problem.

2 RELATED WORK {#SEC2}
==============

Several methods have been proposed in literature for protein structure comparison. These methods compare a pair of protein structures, compute a quantitative measure of similarity and most often generate a structural alignment. [@B20]) have compiled a comprehensive review describing challenges in protein structure comparison and its importance along with various proposed methods. These methods differ on the following two broad points: (i) choice of appropriate representation and (ii) algorithm for retrieval of homologous structures from the database.

The popular representation choices include (i) complete 3D coordinate information or partial coordinate information of backbone atoms, (ii) representation of various elements using their properties such as ϕ-ψ angle, solvent accessibility, etc. The first type of representation preserves sequential and topological relationships between individual elements of the structure. The methods developed to compare the first type of representation are partitioned into two: the ones using dynamic programming (DP) ([@B17]; [@B19]) and others not using DP ([@B8]; [@B18]). These methods are computationally expensive and do not scale well for large number of structures. Moreover, a large number of these comparisons do not yield results since many structures are not related. To overcome these problems, researchers proposed a two stage approach widely known as the filter and match paradigm. The filtering step employs efficient and fast algorithms to obtain a small set of most likely similar proteins. These proteins are subjected to rigorous and computationally expensive structure alignment methods in the second step, which is known as a match step. The desired efficiency in filtering step is achieved by representing each protein as a vector in the space spanned by appropriate features and comparing them in the vector space. For instance, method proposed by [@B4]) and PRIDE represented protein structures using corresponding distance matrix. Rogen and Fein represented protein with topological features of backbone using knot invariants ([@B16]). Zotenko and co-workers represented each protein structure as a vector of frequencies of structural models, each of which is a spatial arrangement of triplets of secondary structure elements ([@B22]). Several other feature-based structure representation and comparison methods have also been proposed in literature such as [@B5]), [@B21]), etc. For complete survey on these methods, the readers are referred to a survey by [@B1]).

3 PROPOSED APPROACH {#SEC3}
===================

As mentioned in the introduction, the framework for protein structure comparison has two subproblems to be handled. In this section, we will elaborate the proposed framework to address these subproblems. These proposed techniques draw a huge motivation from statistical NLP.

3.1 Representation of proteins in topic space {#SEC3.1}
---------------------------------------------

The key point of the proposed approach is to represent proteins as probability distributions over latent topics. Note that the topic is an abstract concept and is represented as a multinomial distribution over fragments. Given this representation, a collection of protein structures can be modeled using three-level hierarchical Bayesian generative model known as LDA ([@B2]). Intuitively, this formalism clusters similar fragments into topics, which provides significant advantage over models that perform fragment to fragment comparison (except identity) while comparing protein structures. We explain this concept with a simple example. Suppose we are interested in comparing two documents, one containing words *dog* and *cat* and the other containing *bark* and *mews*. Naive word level comparison of the two documents reveal that they are unrelated, when they actually talk about semantically related topics (dog barking and cat mews in this case). This example can be extended to protein structures, where fragments are entities equivalent to words in the document. The fragments are grouped into a topic in a probabilistic manner and the search for homologous proteins can be performed more accurately in the topic space. Before introducing formal aspects of the problem formulation, we describe the key ingredients: A *fragment f*~*i*~ is the basic unit of protein structure. It is part of the fragment library of choice *F*. *F*={*f*~1~,*f*~2~,...,*f*~*L*~}, where *L* is the size of fragment library *F*.A *protein* is a sequence of *n* fragments, denoted by *S*={*f*~*i*~\|*f*~*i*~ε*F*}. The protein structure is converted into a sequence of fragments using the method described in [@B3]).A *universe* is a collection of *N* proteins, denoted by *U*={*s*~1~,*s*~2~,...,*s*~*N*~}.

The graphical model representation of LDA is provided in [Figure 1](#F1){ref-type="fig"}. It models the protein structure collection according to the following generative process: Pick a multinomial distribution φ~*z*~ for each topic *z* from a dirichlet distribution with parameter β.For each protein *s*, pick a multinomial distribution θ~*s*~ from a dirichlet distribution with parameter α.For each fragment *f*~*i*~ in protein structure *s*, pick a topic *z*ε{1,...,K} with parameter θ~*s*~.Pick fragment *f*~*i*~ from the multinomial distribution φ~*z*~. Fig. 1.Graphical representation of LDA; K is the number of topics; N is the number of protein structures; *N*~*s*~ is the number of fragments in protein structure *s*.

According to the model, each protein is a mixture of latent variables *z* (referred to as clusters/topics), and each latent variable *z*~*i*~ is a probability distribution over fragments. Given *N* proteins, *K* topics, *L* unique fragments in the collection, we can represent *p*(*f*\|*z*) for the fragment *f*, with a set of *K* multinomial distributions φ over the *L* fragments, *P*(*f*\|*z*=*j*)=φ~*f*~^(*j*)^. *P*(*z*) is modeled with a set of *N* multinomial distributions θ over *K* topics. One way to achieve is to use expectation--maximization to find the estimates of φ and θ. It suffers from local maxima issues, and its hard to model an unseen protein since it does not assume anything about θ. LDA overcomes these issues by assuming a prior distribution on θ and φ to provide a complete generative model. It uses dirichlet distribution[^1^](#FN1){ref-type="fn"} for choosing priors α for θ and β for φ.

The likelihood of generating a universe of protein structure collections is

Exact inference is LDA model is intractable and hence a number of approximate inference techniques such as variational methods ([@B2]), expectation propagation ([@B7]) and Gibbs sampling ([@B6]; [@B7]) have been proposed in the literature. We use Gibbs sampling-based inferencing to estimate φ and θ. From a sample, and are approximated using following equations after a fixed number of iterations, which is commonly known as burn in period. Here, *n*~*i*,*j*~ is the number of instances of fragment *f*~*i*~, assigned to topic *z*=*j*. α and β are hyperparameters that determine the smoothness of the distribution. *n*~*i*,*j*~^(*s*~*i*~)^ is the number of fragments in protein *s*~*i*~ that belong to topic *z*=*j*. Thus, the total number of fragments assigned to topic *z*=*j* is given by ∑~*v*=1~^*V*^*n*~*i*,*j*~^(*v*)^. The total number of fragments in protein *s*~*i*~ is given by ∑~*t*=1~^*T*^*n*~*i*,*j*~^(*s*~*i*~)^. The terms, ∑~*v*=1~^*V*^*n*~*i*,*j*~^(*v*)^ and ∑~*t*=1~^*T*^*n*~*i*,*j*~^(*s*~*i*~)^ are normalizing factors.

The work flow for building topic model is as follows: We take collection of protein structures as an input. We process each structure and obtain the corresponding fragment by matching its substructures with the library. At the end of this process, we obtain a bag of fragments for each protein. This process is depicted in [Figure 2](#F2){ref-type="fig"}.We learn the topic model on the collection using the machinery described earlier in this section.Each protein is then represented as a probability distribution over the latent topics discovered by LDA. Fig. 2.Example protein structure with bag of fragments and topic space representations; built for a given fragment library. (**a**) shows an example protein structure and (**b**) shows a given fragment library. Each substructure in protein is compared against the fragment library and the closest matching fragment is used to represent the substructure. Thus, we obtain bag of fragments representation for protein structure as shown in (**c**). We model the structure as a probability distribution over latent topics. In (**d**) we have shown a toy representation using three topics, which forms a simplex.

3.2 Multi-viewpoint-based retrieval {#SEC3.2}
-----------------------------------

A simple framework for protein retrieval is given in [Figure 3](#F3){ref-type="fig"}, where the universe of proteins are modeled using the representation *R* chosen. In order to rank the proteins based on the structural similarity for a query protein, the query protein is modeled and transformed to the same representation space *R*. Once the transformation is done, the protein structures in the collection are ranked based on their structural similarity with the query protein using a retrieval technique. Most simplest technique would involve a boolean vector representation for each protein. Here, the fragments from the fragment library are matched against the protein structure, and a vector of size of the fragment library is built. The vector has 1 in the position of fragments that are present and 0 in the place of fragments that are absent. And retrieval can be based on Jaccard Coefficient ([@B13]). It can be replaced by other IR techniques such as term frequency (TF), term frequency-inverse document frequency (TF-IDF), etc. The similarity metrics must be chosen according to the choice of representation ([@B13]). We refer to this family of techniques as naive vector space models. Fig. 3.Typical IR model.

As mentioned earlier, the retrieval might have different objectives for different applications. For example, retrieving proteins that are similar, whether they are close homologs or remote homologs. Text-based IR researchers have shown that retrieval based on combination of multiple query representations, multiple representations of text documents or multiple IR techniques provide significantly improved results compared with single representation-based technique, especially when there are multiple retrieval requirements across users. These techniques are referred to as multi-viewpoint-based IR in literature ([@B15]). Schema of multi-viewpoint IR is given in [Figure 4](#F4){ref-type="fig"}. The intuition behind doing this is: retrieval information about an author, publication or book would require exact keyword match, but querying based on topics, for example 'sports news', must allow more than just keyword match. Motivated by the success of multi-viewpoint-based text IR works, we propose a multi-viewpoint-based retrieval system for protein structure collection. Protein structure similarity can be captured by not only matching fragments in the protein structure, but also similar fragments (not just identity) must also be considered to help protein structure comparison. This is achieved by modeling the protein structure using LDA, which maps the fragments to a topic space using their cooccurrence information. Protein structure comparison at topic space performs a soft matching by considering similar fragments too. Fig. 4.Multi-viewpoint-based IR.

The proposed model combines the plain vector (boolean or frequency-based) representation of fragments in protein structure and topic space representation using LDA. Query protein and proteins in the collection are transformed into a naive vector space model and LDA representation. The retrieval techniques for both the modeling methods are different. Let us assume a simple boolean representation and a cosine similarity metric for the naive vector space model. Cosine similarity between two protein structures represented using boolean vectors A, B is given below We refer to the similarity based on naive vector representation as *FragSimilarity*. LDA-based representation uses the asymmetric Kullback Leibler (KL) divergence measure to rank proteins. Asymmeric KL divergence between two proteins represented by the topic distribution vector P and Q is given below The ranking based on these two techniques are combined using a weighted combination of similarity values. KL divergence captures the distance and not similarity value as in the case of cosine similarity. The range of values for cosine similarity (0,1) and KL divergence (−∞,0) are different. KL divergence values are normalized using min--max normalization to get normalized KL divergence measure *D*~KL~^norm^, and converted into similarity value by performing 1−*D*~KL~^norm^. Finally, the values are combined as follows λ~1~ and λ~2~ denote the relative weight for the retrieval schemes based on vector representation and LDA, respectively. The model can also be extended to more representation schemes, where 0≤λ~*i*~≤1 and ∑~*i*~λ~*i*~=1 Comparison of various vector representations and similarity metrics are given in the [Section 4](#SEC4){ref-type="sec"}.

4 EXPERIMENTAL RESULTS {#SEC4}
======================

The experiments are performed on FragBag dataset ([@B3]) containing 2930 sequence non-redundant structures selected from CATH version 2.4. The dataset was constructed by using a best-of-six structural aligner using SSAP ([@B19]), STRUCTAL, DALI ([@B8]), LSQMAN ([@B10]), CE ([@B18]) and SSM ([@B11]; [@B3]). The structural neighbors of each protein are determined using threshold on structural alignment score (SAS) obtained from the alignments. The following three SAS thresholds, 2, 3.5 and 5 Å, are used to obtain close to remote homologs of the query protein. Each protein in the dataset is represented as a probability distribution over the latent topics discovered by LDA and is used as a query for evaluating performance of our method in ranking its structural neighbors. For constructing topic models, we use 7 out of 24 fragment libraries proposed by [@B11]) based on their performance as reported in earlier work ([@B3]). These seven libraries are as follows: 100 (5), 300 (6), 250 (7), 600 (9), 600 (10), 400 (11) and 400 (12). Here, each library is represented with the number of constituent fragments and their size. For example, 400 (11) represents a library containing 400 fragments of size 11. The ranking performance is measured using area under the curve (AUC) of receiver operating characteristics (ROC) curve. The overall AUC value is obtained by averaging individual AUC values across 2930 query proteins. The AUC takes values between 0 and 1 and its value closer to 1 indicates higher ranking performance.

A number of similarity measures exist for comparing protein structures in topic space. We compare the performance of the following distance measures: cosine similarity (CO), Euclidean distance (EU) and KL divergence (KL) and select the one with the highest performance. The topics were discovered from proteins represented using fragments from 400 (11) library, which is chosen due to its top performance in FragBag experiments ([@B3]). [Table 1](#T1){ref-type="table"} contains the results for three different SAS thresholds: 2, 3 and 5 Å. It can be seen that KL and CO are more appropriate for SAS threshold of 2 and 5 Å, while KL performs slightly better than CO for SAS threshold of 3.5 Å. We use KL as a preferred distance measure for further analysis, since it outperforms the other two measures in most of the choices of the number of topics ([Table 1](#T1){ref-type="table"}). Table 1.Comparison of three different distance measuresDistanceTopicsSAS10100150200250300400500KL0.850.890.90.90.90.90.90.9EU0.840.870.880.880.870.870.870.872CO0.850.890.890.890.90.90.90.9KL0.710.770.770.780.770.780.780.77EU0.690.710.730.730.730.730.720.723.5CO0.700.730.760.760.760.770.770.77KL0.680.690.690.690.680.680.680.67EU0.670.670.670.660.660.650.650.655CO0.680.690.690.690.690.690.690.68[^2]

In order to select the ideal number of topics, we represented proteins with various number of topics obtained for each of the seven fragment libraries and ranking performance of our method is obtained in terms of average AUC value for each of the SAS thresholds ([Table 2](#T2){ref-type="table"}). The analysis reveals that the representation using 200--250 topics has the best ranking performance. We use the best performing number of topics for each library in the further analyses. Table 2.Selection of the best number of topics for representing proteins, using each of the seven libraries, based on their ranking performance indicated by the average AUCLibraryTopicsSAS10100150200250300400500100 (5)0.830.850.860.880.880.870.860.84300 (6)0.840.850.860.880.880.880.870.85250 (7)0.850.870.880.890.90.890.890.89600 (9)0.850.890.90.90.90.90.890.882600 (10)0.850.880.90.90.90.90.90.88400 (11)0.850.890.90.90.90.90.90.9400 (12)0.840.890.90.90.90.890.890.87100 (5)0.700.730.730.740.730.720.720.74300 (6)0.710.740.750.760.760.760.750.75250 (7)0.710.750.750.760.760.760.760.75600 (9)0.720.770.770.780.780.780.770.77600 (10)0.720.770.770.780.780.770.770.773.5400 (11)0.710.770.770.780.770.780.770.77400 (12)0.710.770.770.770.760.760.760.76100 (5)0.670.680.680.680.670.670.670.67300 (6)0.660.670.680.680.680.680.680.67250 (7)0.660.690.690.680.680.680.670.67600 (9)0.680.690.70.690.680.680.680.67600 (10)0.670.690.690.690.680.680.680.665400 (11)0.680.690.690.690.680.680.680.67400 (12)0.690.70.70.70.690.690.690.67

As mentioned in [Section 3.2](#SEC3.2){ref-type="sec"}, multi-viewpoint IR combines LDA and simple vector space model with weights λ~1~ and λ~2~. In this section, we identify the best simple vector space model from the following choices: (i) term frequency (TF), (ii) term frequency and inverse document frequency (TF-IDF) and (ii) boolean (Bool). We choose cosine similarity to compare vectors, since it has been shown to work well for such representations in literature. The AUC score for different λ values are given in [Table 5](#T5){ref-type="table"}. The values are computed on 400(11) library, which gives the best results across different number of LDA topics (from [Table 2](#T2){ref-type="table"}). The analysis of [Table 3](#T3){ref-type="table"} reveals that the multi-viewpoint IR with either TF or TF-IDF as a simple vector space model performs better than FragBag ([@B3]). Overall, combining TF and LDA gives the best results ([Table 3](#T3){ref-type="table"}). The experiments are repeated for other libraries using the best multi-viewpoint IR model (TF and LDA) and the results for SAS thresholds 2, 3.5 and 5 are given in [Tables 4](#T4){ref-type="table"}, [5](#T5){ref-type="table"}, [6](#T6){ref-type="table"}, respectively. Table 3.Comparing the average AUC for various Multi-viewpoint IR methodsλ~1~SAS=2SAS=3.5SAS=5IIIIIIIIIIIIIIIIII00.890.870.80.770.720.640.750.730.680.10.890.870.810.780.730.650.750.730.690.20.90.880.810.780.740.660.750.730.690.30.90.880.820.790.750.670.750.740.70.40.910.890.830.790.760.690.770.740.70.50.910.90.850.80.770.70.750.740.710.60.910.90.860.80.780.720.750.730.710.70.910.90.880.80.780.750.750.730.710.80.910.910.890.80.790.770.740.720.710.90.910.90.90.80.780.770.720.70.710.90.90.90.780.780.780.680.680.68[^3] Table 4.Comparison of models built on different libraries for SAS threshold of 2 Åλ~1~400 (12)600 (10)600 (9)250 (7)200 (6)100 (5)00.880.880.880.870.850.860.10.890.890.890.880.860.860.20.890.890.890.880.860.860.30.90.90.90.880.860.860.40.90.90.90.890.870.860.50.90.910.910.890.880.870.60.910.910.910.890.880.870.70.910.910.910.90.890.870.80.910.910.910.90.890.870.90.90.910.910.90.890.8710.890.90.90.890.880.87[^4] Table 5.Comparison of models built on different libraries for SAS threshold of 3.5 Åλ~1~400 (12)600 (10)600 (9)250 (7)200 (6)100 (5)00.760.760.760.740.690.720.10.770.770.770.750.70.720.20.780.770.770.750.710.720.30.780.780.780.760.720.730.40.790.780.790.760.730.730.50.790.790.790.760.740.730.60.790.80.80.770.750.740.70.80.80.80.770.750.740.80.80.80.80.780.760.740.90.790.790.80.770.760.7510.770.770.780.760.760.74[^5] Table 6.Comparison of models built on different libraries for SAS threshold of 5 Åλ~1~400 (12)600 (10)600 (9)250 (7)200 (6)100 (5)00.760.750.750.750.710.730.10.760.750.750.750.720.730.20.760.750.750.750.720.730.30.760.760.760.760.720.730.40.760.760.760.760.730.730.50.760.760.760.760.730.730.60.760.760.760.760.720.730.70.760.750.750.750.720.720.80.750.740.740.740.710.720.90.730.730.730.730.70.7110.690.690.690.690.680.68[^6]

Influence of the weights λ~1~ and λ~2~ on the retrieval performance is shown in [Figure 5](#F5){ref-type="fig"}. It can be seen that for SAS thresholds of 2 and 3.5, best performance is achieved with a higher weight for LDA representation (λ~1~). On the other hand, for SAS threshold of 5, best performance is achieved with a higher weight for simple vector space model (or at least equal to LDA representation). As mentioned earlier, SAS threshold 2 tends to retrieve , are for close homologs, and 5 denotes remote homologs. LDA-based representation performs better in identifying close homologs (SAS threshold of 2 Å) than the remote ones (SAS threshold of 5 Å) for a given query protein. Since the fragment functionality overlap is less as we move up the parent tree for a protein structure, exact match using naive vector space model performs better than LDA representation to identify remote homologs. Motivated by the fact that the best results are spanning different libraries, an ensemble on ranking is attempted. For a given query protein structure, similarity produced by a model, say using library 400 (11), and weights λ~1~=0.6, λ~2~=0.4 is treated as an independent hypothesis. Output of each model (combination of libraries and λ~1~, λ~2~ values) is treated as a hypothesis. The best *k* hypotheses (empirically chosen) are chosen and are combined using *bucket of models* strategy. For example, let *sim*~*X*~(*q*,*s*~*d*~) and *sim*~*Y*~(*q*,*s*~*d*~) be the similarity scores between a query protein *q* and a protein *s*~*d*~ in the database as provided by the models X and Y, respectively. Using the bucket of model strategy, the similarity between *q* and *s*~*d*~ is given by *sim*(*q*,*s*~*d*~)=*max*(*sim*~*X*~(*q*,*s*~*d*~), *sim*~*Y*~(*q*,*s*~*d*~)) This is referred to as a *Combined Model*. We tested it by combining three best models across SAS thresholds. The best models are 600 (9) with weights (0.8, 0.2) for SAS=2; 400 (11) with weights (0.7, 0.3) for SAS=3.5; 400 (11) with weights (0.4, 0.6) for SAS=5. Results for the *Combined Model* is given in [Table 9](#T9){ref-type="table"}. Fig. 5.Impact of weights, λ~1~ and λ~2~, in multi-viewpoint-based IR model. The models are constructed by combining LDA-based topic model with weight λ~1~ and term frequency (TF) vector space model with weight λ~2~.

In order to show the effectiveness of LDA-based representation over BoW representation ([@B3]), we compare their performance on classification and clustering tasks. It can be seen that LDA representation performs better than the BoW for both the tasks, in terms of time taken and standard measures for the tasks. [Table 7](#T7){ref-type="table"} has the comparison results for classification at C level classes in CATH hierarchy (4 classes). Since the dataset chosen is sparse at other levels of CATH hierarchy (has \<10 members for most classes at A, T, H levels), we perform classification only at C level. Radial Basis Function network (RBF) and Naive Bayesian (NB) classifiers are used for the comparison. Results are compared in terms of root mean squared error (RMSE), ROC and accuracy. The values are obtained by averaging results across 10-fold cross validation. [Table 8](#T8){ref-type="table"} contains comparative results in terms of SSE (sum of squared error) for K Means algorithm using both BoW and LDA representations. Table 7.Performance of BoW and LDA representations while classifying proteins at class (C) level of CATH classificationBoWLDABoWLDABoWLDABoWLDARMSEROCAccuracyTime (sec)RBF0.250.230.930.9583.985.76.842.5NB0.330.310.90.92278.680.60.580.19 Table 8.Performance of BoW and LDA for protein structure clustering taskBoWLDAKSSE48556.3363371.61108531.033417.21208154.353348.29507872.793093.441007455.932880.1

The performance of LDA representation and retrieval based on asymmetric KL and multi-viewpoint retrieval using TF and LDA (multiview model I) are compared against naive vector space model with cosine similarity on the chosen seven libraries. For multi-viewpoint-based retrieval, the best weight combination of (λ~1~ and λ~2~) for each library is chosen for the plot. The results are shown in [Figures 6](#F6){ref-type="fig"}, [7](#F7){ref-type="fig"}, [8](#F8){ref-type="fig"} for SAS threshold of 2, 3.5 and 5 Å respectively. [Table 9](#T9){ref-type="table"} gives overall ranking of structural and filter methods, which includes the relative positioning of proposed techniques ([@B12]). It is clear that our method outperforms all the filter-and-match methods. We perform a paired *t*-test and paired sign test with AUC values of each query obtained using proposed models and baseline state-of-the-art filter-and-match method (FragBag). Based on the statistical test, our results are significantly better than the state-of-the-art at 1% significance level. Our results are very competitive even with state-of-the-art structure comparison methods operating at the level of complete 3D representation. It must be noted that our method is much faster than these methods. Fig. 6.Comparison of the average AUC at SAS threshold of 2.0 Å, across libraries, obtained using TF, LDA and multiview model using the best weights from [Table 3](#T3){ref-type="table"}. Fig. 7.Comparison of the average AUC at SAS threshold of 3.5 Å, across libraries, obtained using TF, LDA and multiview model using the best weights from [Table 4](#T4){ref-type="table"}. Fig. 8.Comparison of the average AUC at SAS threshold of 5.0 Å, across libraries, obtained using TF, LDA and multiview model using the best weights from [Table 5](#T5){ref-type="table"}. Table 9.AUCs of ROC curves using best-of-six gold standardMethodsSAS=2SAS=3.5SAS=5AverageRankSpeedSSM using SAS score0.940.90.890.91113Structural using SAS score0.90.810.840.85239**Combined model**0.920.820.75**0.83**3FastStructural using native score0.870.770.830.823439**Multiview model I (400,11)**0.910.80.76**0.823**4FastCE using native score0.90.790.740.81654**Multiview model II (400,11)**0.90.780.73**0.803**7FastFragBag Cos distance (400,11)0.890.770.750.8037Fast**Multiview model III (400,11)**0.890.770.7**0.787**9FastCE using SAS score0.840.720.750.771054FragBag histogram intersection (600,11)0.870.730.70.76711FastSGM0.860.710.680.7512FastFragBag Euclidean distance (40,6)0.860.710.640.73713FastZotenko *et al.* (18)0.780.640.660.69314FastSequence matching by BLAST e-value0.760.570.50.6115FastPRIDE0.720.540.510.5916Fast[^7]

5 CONCLUSION {#SEC5}
============

We proposed a novel framework for representation and comparison of protein structures. We demonstrated that our method outperforms most of the existing filter-and-match methods. Our results are very competitive even with the state-of-the-art structure comparison methods operating at the level of complete 3D representation. Moreover, our method is much faster than these methods. Kolodny and co-workers first proposed the use of IR techniques in protein structure comparison ([@B3]). In this work, we have shown significant improvements by adapting more advanced models from statistical NLP literature to this task. We also take advantage of simpler models through the proposed multiview framework and built a system that can be tuned to the retrieval objectives at hand. This work has firmly established that such fragment-based models can be competitive with the structural methods. It has also opened the doors for deeper analysis, using techniques from statistical NLP, of the role that fragments play in determining the overall structure.

^1^Dirichlet prior is a conjugate prior of multinomial distribution.

*Dataset and tools*: we thank Rachel for providing us the protein structure dataset and fragment libraries and Arun Konagurthu for fit3D code which matches a fragment with protein structure in 3D space.

*Funding:* Innovative Young Biotechnologist Award grant 2008 from Department of Biotechnology, Government of India (to A.V.T.).

*Conflict of Interest*: none declared.

[^1]: ^†^ The work was done when the author was an intern at Department of CSE, IIT Madras.

[^2]: Cosine similarity (CO), Euclidean distance (EU) and KL divergence (KL) based on average area under the curve (AUC) obtained by ranking structurally similar proteins, which are represented in topic space using 400 (11) library.

[^3]: The multi-viewpoint models are obtained by combining latent dirichilet allocation topic model (LDA) with weight λ~1~ and one of the following vector space models (i) term frequency (TF) (I), (ii) term frequency inverse document frequency (TF-IDF) (II) and (iii) boolean (BOOL) (III) with weight λ~2~. Since λ~2~=1− λ~1~, we have not mentioned their values explicitly in the table.

[^4]: Here each library is denoted as *X*(*Y*), where *X* is the number of fragments in the library, each of length *Y*. The ranking performance of a given multi-viewpoint IR model for a given library is given in terms of AUC. The multi-viewpoint model contains LDA model with weight λ~1~ and TF vector space model with weight 1−λ~1~.

[^5]: Here each library is denoted as *X*(*Y*), where *X* is the number of fragments in the library, each of length *Y*. The ranking performance of a given multi-viewpoint IR model for a given library is given in terms of AUC. The multi-viewpoint model contains LDA model with weight λ~1~ and TF vector space model with weight 1 − λ~1~.

[^6]: Here each library is denoted as *X*(*Y*), where *X* is the number of fragments in the library, each of length *Y*. The ranking performance of a given multi-viewpoint IR model for a given library is given in terms of AUC. The multi-viewpoint model contains LDA model with weight λ~1~ and TF vector space model with weight 1 − λ~1~.

[^7]: The proposed approaches are shown in bold. Multiview model I is a combination of TF and LDA, multiview model II is a combination of TF-IDF and LDA and multiview model III is a combination of Boolean vector and LDA. The speed is given as average CPU minutes per query. If the processing time (after preprocessing of protein structure) for a query is \< 0.1 s, then it is mentioned as *fast*.
