A weighted Cramér’s V Index for the assessment of stability in the fuzzy clustering of class C G protein-coupled receptors

A Weighted Cram´er’s V Index for the Assessment of Stability in the Fuzzy Clustering of Class C G Protein-Coupled Receptors Alfredo Vellido⋆, Christiana Halka, and ` Angela Nebot Department of Computer Science, Universitat Polit`ecnica de Catalunya, Barcelona 08034, Spain {avellido,christiana.halka,angela}@cs.upc.edu http://www.cs.upc.edu/~avellido Abstract. After decades of intensive use, K-Means is still a common choice for crisp data clustering in real-world applications, particularly in biomedicine and bioinformatics. It is well-known that different initializations of the algorithm can lead to different solutions, precluding replicability. It has also been reported that even solutions with very similar errors may widely differ. A criterion for the choice of clustering solutions according to a combination of error and stability measures has recently been suggested. It is based on the use of Cram´er’s V index, calculated from contingency tables, which is valid only for crisp clustering. Here, this criterion is extended to fuzzy and probabilistic clustering by first defining weighted contingency tables and a corresponding weighted Cram´er’s V index. The proposed method is illustrated using Fuzzy C-Means in a proteomics problem. Keywords: Fuzzy clustering; K-Means; Clustering stability analysis; Cram´er’s V index; G Protein-Coupled Receptors 1 Introduction G protein-coupled receptors (GPCRs) are cell membrane proteins of interest due to their role in transducing extracellular signals after specific ligand binding. They have in fact become a core interest for the pharmaceutical industry, as they are targets for more than a third of approved drugs [1]. GPCR functionality is mostly investigated from its crystal 3-D structure. Finding such structure, though, is a difficult undertaking1and only in the last decade, a handful of GPCR structures has been found, most of them belonging to the class A of the GPCR superfamily [2]. Only in 2013, one receptor not belonging to class A but to the Frizzled class and two class B [3, 4] were reported. ⋆This research was partially funded by Spanish MINECO TIN2012-31377 research project. 1Rhodopsin was the first GPCR crystal structure to be determined, back in 2000. 2 Assessment of Stability in the Fuzzy Clustering of Class C GPCRs The first structures of the 7-trans-membrane (7TM) domains of two class C receptors were published in 2014 [5, 6]. Our research focuses on class C GPCRs, which have become a key target for new therapies [7]. The alternative approach when the tertiary 3D crystal structure is not available, is the investigation of the receptor functionality from its primary structure, that is, directly from the amino acid (AA) sequences. The comparative exploration of the sequences of the seven different described subtypes of this class may constitute a first step in the study of the molecular processes involved in receptor signalling. Most of the existing data-based research on primary receptor sequences resorts to their alignment [8], which enables the use of more conventional quantitative analysis techniques. Given that the length of the class C GPCR sequences varies from a few hundred AAs to well over a thousand, alignment risks the loss of relevant sequence information. Alternatively, as in this paper, we can resort to methods for the analysis of alignment-free sequences from their transformation according to the AA properties (for a review see [9]). Previous exploration of the class C GPCR sequences through visualizationoriented clustering [10] and semi-supervised analysis [11] has shown that the existing formal characterization of this class into seven subtypes only partially corresponds to the natural data cluster structure according to unaligned sequence transformations. In the current study, we investigate this issue within a more general clustering framework. Clustering analysis often works by assigning individual data instances to one out of several clusters according to their similarity to representative examples Such assignment is often of a dichotomous or crisp nature: the instance either belongs to or does not belong to a given cluster. Fuzzy and probabilistic clustering methods, instead, assign each data instance to each cluster with an estimated degree or probability of membership. As a result, the uncertainty of the assignment decision is explicitly taken into account in the model. Over the last decades [12], K-Means has become a stalwart method for data clustering, spawning many variants while remaining a common choice, even if as a benchmark, in many real-world applications. K-Means is based on crisp cluster assignments, although variants such as Fuzzy C-Means (FCM)[13] have extended the model to account for partial degrees of membership. K-Means limitations are well studied and include the lack of a closed criterion for the choice of the number of clusters Kand the fact that, under different initializations, the algorithm may yield very different solutions. Recent experimental evidence [14] has shown that K-Means solutions that might be expected to be similar according to the final value of the objective function may in fact be quite dissimilar, and that this effect increases with the value of K. This suggests the convenience of using the objective function as a criterion of model optimality only in combination with some cluster stability criterion if we aim to achieve cluster partition reproducibility. One such combined criterion is the Separation and Concordance (SeCo) map, which joins the Assessment of Stability in the Fuzzy Clustering of Class C GPCRs 3 standard sum-of-squares (SSQ) error and Cram´er’s V stability index, a variation of Pearson’s χ2, which can also be used to inform the choice of K. The calculation of Cram´er’s V index is based on the use of contingency tables, which are only suitable for crisp cluster assignments. In this study, we extend the SeCo criterion to fuzzy and probabilistic clustering by first defining weighted contingency tables and a corresponding weighted Cram´er’s V index. This should be a more faithful assessment of the clustering solution stability for fuzzy and probabilistic methods. The proposed methods are employed to investigate a class C GPCR primary sequence data set extracted from a publicly available database. Two experimental settings for the clustering experiments are used. The first fixes the number of clusters to the number of formal subtypes in the class in order to investigate the level of correspondence between both, while the second relaxes this constraint in order to analyze the stability of the clustering solutions using SeCo maps. 2 Methods 2.1 Alignment-Free Sequence Transformation Methods As previously mentioned, in this paper we resort to methods for the analysis of alignment-free sequences from their transformation according to the AA properties. Three transformations were used in our experiments: –Amino Acid Composition (AAC): This simple transformation reflects the AA composition of the primary sequence. The frequencies of the 20 sequenceconstituting AAs are calculated for each sequence and, as a result, an N×20 data matrix is obtained, where Nis the number of data instances. –Auto Cross Covariance (ACC): The ACC transformation aims to capture the correlation of the physico-chemical AA descriptors along the sequence. The method relies on the translation of the sequences into vectors based on the principal physicochemical properties of the AAs. Data are transformed into a uniform matrix by applying a modified autocross-covariance transform [15]. First, the physico-chemical properties are represented by means of the five z-scores of AA as described in [16]. Then the Auto Covariance (AC) and Cross Covariance (CC) are computed on this first transformation. They, in turn, measure the correlation of the same descriptor (AC) or the correlation of two different descriptors (CC) between two residues separated by a lag along the sequence. From these, the ACC fixed length vectors can be obtained by concatenating the AC and CC terms for each lag up to a maximum lag, l. This transformation generates an N×(z2·l) matrix, where z= 5 is the number of descriptors. –Digram Transformation: The digram transformation is a particular instance of the more general n-gram transformation. It considers the frequencies of occurrence of any given pair of AAs. The n-gram concept has previously been used in protein analysis [17]. This particular transformation generates an N×400 matrix. 4 Assessment of Stability in the Fuzzy Clustering of Class C GPCRs 2.2 Data Clustering Using K-Means and Fuzzy C-Means The K-Means algorithm creates a partition of a set X={x1,...,xN}of observed data into a set of Kclusters Γ={Γ1, . . . , ΓK}by defining a fixed number K of data centroids or prototypes {µ1, . . . , µK}. It does so by assigning individual data observations to their closest prototypes according to a given similarity measure or distance. Such assignment is crisp in the sense that individual observations are associated to individual clusters with complete certainty. Fuzzy and probabilistic clustering techniques relax this approach by assigning, to each observation, a fuzzy degree (for instance in FCM) or a probability (for instance in mixture models) of membership to each cluster. Most approaches to K-Means opt for different forms of random initialisation of the prototypes (seeds). The algorithm’s objective is finding the set Γthat minimises a SSQ error in the form ∑K k=1 ∑x∈Γk∥x−µk∥2. FCM generalizes this objective function to become: C ∑ c=1 N ∑ n=1 ωm nc∥xn−µc∥2(1) for Cfuzzy clusters, fuzzy weights ωand fuzziness parameter m. It is well known that different initialisations of the algorithm make it converge to different local minima and that there is no guarantee of convergence to a global minimum of the objective function. In practical applications, K-Means and FCM are run with a sufficient number of random initialisations and the Γgenerating minimum error is chosen among the rest. 2.3 Clustering Stability Measures Even if finding a minimum error Γis a central objective of K-Means, the stability of the clustering solution is also relevant. Solutions that are reproducible are required. That is, cluster partitions that do not change (much) under different initialisations, i.e., that are stable. This cluster stability is paramount in practical applications and can be quantified using different indices [18]. It was recently brought into attention [14] that K-Means partitions with similar errors might be greatly different from each other (thus unstable) and that this effect increases with the value of K. Assuming that solutions that strike a balance between low error and high stability ought to be sought, Lisboa et al. [14] proposed a framework based on the calculation of Separation/Concordance (SeCo) maps for settings using multiple random initializations of K-Means for different values of K. This entails the simultaneous display of a pair of values for each run of the algorithm, namely: The ∆SSQ, calculated as the total SSQ minus the within-cluster SSQ: K ∑ k=1 N ∑ n=1 ∥xn−µk∥2− K ∑ k=1 ∑ xn∈Γk ∥xn−µk∥2(2) and a concordance index (CI) quantifying stability. In [14], the use of Cram´er’s V index is recommended as a basis for it. The CI is calculated as the median of Assessment of Stability in the Fuzzy Clustering of Class C GPCRs 5 the (nin −1) pairwise Cram´er’s V calculations for nin initializations. For two cluster partitions Γand Γ′of, in turn, Kand K′clusters, Cram´er’s V index is a variation of a χ2test, calculated as V=√χ2/N min(K−1, K′−1), where χ2= K ∑ k=1 K′ ∑ k′=1 (Okk′−Ekk′)2/Ekk′(3) Here, Ois an observed contingency table (K×K′) matrix, whose values Okk′ indicate the number of instances in Xthat have been assigned to cluster kin one run of the algorithm and to cluster k′in another run. The K×K′matrix E contains the corresponding expected values for independent cluster allocations, calculated as Ekk′=1 N(∑K′ j=1 Okj ∑K i=1 Oik′). This use of contingency tables is suitable for crisp cluster assignments such as those provided by K-Means. For soft assignments such as those provided by FCM or Gaussian Mixture Models, instead, this use occludes the richness of the cluster solution by requiring the assignment of instances to clusters to be based on the highest degree of membership or probability. In this paper, we propose a variation of contingency tables that better suits the characteristics of fuzzy and probabilistic models. Elements in what we call weighted observed (wO) contingency tables will now be calculated, following the notation of Eq.1 for FCM, as wOcc′=sumN n=1ωncωnc′; this is, for data instance n, the product of the degree of membership to cluster cin a first run of the algorithm and the degree of membership to cluster c′in a second run. Consequently, we can obtain a weighted expected (wE) contingency table matrix whose elements are defined as wEcc′= (∑C′ j=1 wOcj ∑C i=1 wOic′)/N. This leads to the definition of a new weighted Cram´er’s V index, where Ois replaced by wOand Eby wEin the calculation of χ2in Eq.3. If FCM estimated that all instances had a degree of membership of 1 for a single cluster, the weighted Cram´er’s V index would reduce to its standard formulation. This is unlikely to happen, which means that the proposed index will lead to lower levels of CI in SeCo. This should, therefore, be not only a conservative concordance estimator, but also a more reliable clustering assessment tool, capable of distinguishing solutions with varying levels certainty. Note that SeCo can be used as a flexible tool to chose adequate values of the Kparameter (number of clusters). This is equally true when using the modified index, but, in this case, there should be no bias in favour of “over-optimistic” solutions. 3 Experiments 3.1 Materials and Experimental Setting The data in the following experiments were extracted from GPCRDB2[19] (version 11.3.4 as of March 2011), a public database of G Protein-Coupled Receptor 2http://www.gpcr.org/7tm 6 Assessment of Stability in the Fuzzy Clustering of Class C GPCRs (GPCR) protein primary sequences. The data set comprises a total of 1,510 class C GPCR sequences, belonging to seven subfamilies and including: 351 metabotropic glutamate (mG), 48 calcium sensing (CS), 208 GABA-B (GB), 344 vomeronasal (VN), 392 pheromone (Ph), 102 odorant (Od) and 65 taste (Ta). Their AA lengths vary from 250 to 1,995. Previous research [20] investigated the supervised classification of these data sequences, from several of their alignment-free transformations, including AAC, digram, and ACC, among others. Here, we use K-Means and FCM to investigate to what extent the natural clustering structure of the data fits the subfamilies (classes) description. For that, we first report the results of experiments in which the number of clusters is fixed a priori to be the same as the number of class C GPCR subtypes. These will provide us with a preliminary evaluation of the level of natural subtype overlapping. We then proceed to relax that constraint and the SeCo framework, with the proposed modification of the concordance index in the case of FCM, is applied in a setting with 500 random initializations of the algorithms for different number of clusters. Following [14], only the best 10% △SSQ results are displayed in the SeCo plots. 3.2 Results and Discussion The three transformed data sets were fed to the FCM and K-means algorithms. The class (subtype) specificity for each cluster for each data set was measured and the results are provided in the following paragraphs along with class-entropy measures. This will inform us to what extent the clusters extracted by K-means and FCM algorithms correspond (or not) to the theoretically labeled subtypes. The class-entropy for a given cluster kis calculated as Ek=−∑C j=1 pkj lnpkj, where jis one of the C= 7 class C GPCR subtypes and pkj =mkj /mk, where, in turn, mkis the number of sequences in cluster kand mkj is the number of subtype jsequences in cluster k. For FCM, Figure 1 and Table 1 show that, for the AAC data transformation, almost none of the defined clusters show clear class (subtype) specificity. Only in cluster 1, the first subtype (mG) of GPCR achieves a specificity that is close to 60%, but even in this case, the third subtype (GB) reaches a non-negligible 30%. Several clusters show common specificity profiles: for instance, clusters 1 and 3 are predominantly a mixture of mG and GB, which means that they might truly be a single cluster with some substructure. Cluster 4 is a very mixed combination of Ph and VN, but clusters 2, 6 and 7 seem to be variations of this combination, again suggesting one main cluster with further substructure and important levels of overlapping. The ACC and Digram transformations (Figures 2 and 3, and, again, Table 1), instead, manage to separate some of these clusters to become more subtype-specific. mG and GB are now more clearly discriminated (clusters 1 plus 5 and cluster 3, in turn) with the rest of subtypes showing clear overlapping in some clusters but also high specificity in others (for instance, Ph in ACC cluster 6 and Digram in cluster 7). In any case, the more complex transformations (ACC and Digram) seem to make the FCM clustering model more class C GPCR subtype-specific. Assessment of Stability in the Fuzzy Clustering of Class C GPCRs 7 Fig. 1. Class specificity bar chart (with percentage values) for each FCM cluster of class C GPCR data set with the AAC transformation. Classes 1 to 7 are, in turn, mG, CS, GB, VN, Ph, Od and Ta. Fig. 2. As Figure 1, for the ACC transformation. Fig. 3. As Figure 1, for the Digram transformation. 8 Assessment of Stability in the Fuzzy Clustering of Class C GPCRs Table 1. Number of GPCR sequences-per-cluster (♯) and cluster-specific (Ek) and total entropies for the FCM clustering of class C GPCR data with the three transformations. AAC ACC Digram ♯ Ek♯ Ek♯ Ek Cluster 1 245 1.45 107 0.13 112 0.12 Cluster 2 239 2.16 207 1.52 374 2.39 Cluster 3 200 1.34 202 0.33 200 0.37 Cluster 4 193 1.30 237 1.17 277 1.09 Cluster 5 67 1.97 199 0.89 179 0.26 Cluster 6 263 2.15 279 1.99 205 2.02 Cluster 7 303 1.95 279 2.20 163 1.28 Total Entropy 1.77 1.34 1.29 The results of the K-means algorithm for the seven subtypes of class C GPCRs, for which, for the sake of brevity, we only report the entropy results in Table 2, are consistent with those of FCM. Again, almost none of the defined clusters show clear class (subtype) specificity with AAC data transformation. The ACC and Digram transformations, instead, manage to separate some of these clusters to become more subtype-specific. The similarity between the two algorithms is that mG and GB are more clearly discriminated than the rest of subtypes. Moreover, in the ACC transformation, Ph receptors can also be discriminated from the rest subtypes due to their high specificity in cluster 2. The remaining subtypes show clear overlapping in some of the clusters. Table 2. Number of GPCR sequences-per-cluster (♯), together with cluster-specific (Ek) and total entropies for the K-Means clustering of class C GPCR data with the three transformations. AAC ACC Digram ♯ Ek♯ Ek♯ Ek Cluster 1 270 1.65 260 0.26 222 0.10 Cluster 2 406 2.17 136 0.72 398 1.47 Cluster 3 196 1.33 150 0.23 121 0 Cluster 4 189 1.24 188 1.07 284 1.10 Cluster 5 54 1.34 165 1.57 184 1.90 Cluster 6 56 1.74 379 1.79 197 1.95 Cluster 7 339 2.03 232 1.97 104 1.63 Total Entropy 1.77 1.19 1.39 Comparing the results of both algorithms in terms of the total entropy measure, conclusions are not clear-cut. ACC and Digram show a clear advantage both in FCM and K-Means, but neither shows a clear advantage over the other. Assessment of Stability in the Fuzzy Clustering of Class C GPCRs 9 We now move to the clustering stability analyses results, based on random algorithm initializations and varying number of clusters, using the SeCo maps. For each one of the transformed sets, three SeCo maps were created using: –The K-means objective function and the standard Cram´er’s V index. –The FCM objective function and the standard Cram´er’s V index. –The FCM objective function and the novel weighted Cram´er’s V index proposed. As previously mentioned, a threshold for the △SSQ values to select the 10% top values for each value of Kis expected to allow the degeneracy of similar SSQ values to be resolved. The FCM 10% top results, as reported in Figs. 4 to 6, are very parsimonious (much more so than the complete ones, not reported here), revealing a high concentration of stability results around just a handful of median Cram´ers V index values, in comparison with the still wide spread of K-Means. These results are also very consistent over data transformations. For K-Means, this effect does not necessarily increase as Kincreases for any of the data transformations. For FCM, though, an increase in spread as Kincreases is revealed. Overall, this indicates that FCM is much more resilient than its crisp K-Means counterpart to the variability introduced by random initializations. Fig. 4. Separation-Concordance maps for the AAC data set, including the 10% best results. Top: results for K-Means; bottom: results for FCM, a) with standard Cram´er’s V index; b) with proposed weighted Cram´er’s V index.