Clustering protein-protein interaction data with spectral clustering and fuzzy random walk

Spectral Clustering is a graph clustering algorithm that makes use of eigenvector obtained from a matrix describing pairwise similarity between data points. It provides a dimensionality reduction for clustering in lower dimensions. One example of spectral clustering application is the clustering of protein-protein interaction (PPI) network. PPI networks are usually represented as a graph network with proteins and interactions as vertices and edges respectively. However, this spectral clustering only produces a hard clustering of proteins, whereas there may be some relationship between each protein clusters, and possibly multiple functionality for each proteins that has not been detected before. Fuzzy Random Walk is a fuzzy clustering method based on transition probability from a random walk on a dataset. In this paper, we combine both Spectral Clustering and Fuzzy Random Walk to cluster PPI network of protein TP53, a protein thatplays an important role in managing cell cycle, especially in tumor cell suppression. Using PPI dataset of TP53 obtained from the STRING database, we found the combined algorithm is proven to produce both robust and fuzzy clusters with each cluster explains one of TP53 protein’s functionality related to the tumor cell.


Introduction
The increasing complexity and heterogeneity of a data make it difficult to interpret and extract possibly hidden information within the data. This problem has led the development of many dimensionality reduction and data clustering techniques over past decades. Clustering is a process of revealing the underlying structure of a dataset by grouping the data elements into a groups called clusters [1]. Clustering is usually done based on some similarity measure between data elements, and without any information on how the grouping should be done (unsupervised learning) [2].
Graph is a structure formed by a set ofvertices(also callednodes) and a set ofedgesthat connectthe pairs ofvertices.Graph clusteringis a task of grouping the verticesof the graph into some clusters,by considering the edgestructure of the graph, in such a way that there should bemany edgeswithineach cluster and relatively fewbetweenthe clusters [3]. One of the popular graph clustering techniques are spectral clustering. Spectral clustering provides a dimensionality reduction by using the eigenvectors of a similarity matrix of the graph [4]. Spectral clustering is a global clustering method, as it considers all of the graph vertices in its algorithm. Protein-protein interaction (PPI) is a physical contact of high specificity between two or more proteins as a result of biochemical activity steered by electrostatic force including hydrophobic effect [5]. PPI plays a significant role in almost all biological process [5]. Clustering of PPI network is an effective approach in identifying protein complexes and functional module, which is important in investigating a gene role in a disease and also drug target [6]. Broadly speaking, this approach could also give a new understanding about protein function and cell machinery. Spectral clustering of PPI data gives not only a robust clusters, but also possibly some meaningful interpretation in the lowdimensional embedding [7]. However, spectral clustering only produces a 'hard' clusters, whereas there may be some relationship between each protein clusters, and possibly multiple functionality for each proteinsthat has not been detected.
In this paper, we propose a fuzzy version of spectral clustering by combining spectral clustering with fuzzy random walk [8,9] and apply them toPPI network of protein TP53, an important protein for tumor suppression. We set a 'seed' or clustercenter for each clusters and perform a random walk for each data to determine its membership value. Using PPI datasets of TP53 obtained from the STRING database, we found the combined algorithm is proven to produce both robust and fuzzy clusters with each fuzzy cluster explains each one of TP53 protein's functionality related to the tumor cell.

Methods
Our proposed algorithm combines the concept of spectral clustering and fuzzy random walk along with its specific modification for PPI dataset. The input of the algorithm is a graph = ( , ) with nodes1,2,3, … , . There are some noticeable changes between our method and the original fuzzy random walk [8], namely, the determination of the number of clusters, cluster centers, and the assignment of the membership value. Our algorithm returns the number of cluster and a set of membership values ( ) where itdenotes the membership value of node in cluster . The sum of membership value of a node is 1, that is,

Determining the cluster center
A cluster in protein interaction dataset is often characterized by a densely connected region on the graph. Based on [9], in this paper we define the density of a node as the ratio of number of edges between and its neighbor, to the number of vertices in the neighbor of , which is where denotes a set of edges in the neighbor of , denotes a set of nodes in the neighbor of , and ( ) denotes the set of the neighbors of , a set of nodes that is directly connected to the node . The search of cluster center is done iteratively. For each iteration, node with maximum density is selected as the cluster center and then removed along with its neighbor. The node removal is done to ensure that the cluster centers found are not too close to each other. If two disjoint region and of a graph is indeed adifferent cluster, then the node removal of one of the clusters would not affect the density of the other clustersignificantly.
The iteration process is done until the maximum density is lower than a threshold . Then the set of maximum density node of each iteration is defined as the cluster center for different clusters, and the number of cluster centers is the number of cluster.The default value of threshold parameter is 1. Parameter is optional, if it's not provided, then the optimal number of clusters will be determined by the silhouette coefficient [10].

Spectral clustering
Basic concept of spectral clustering is to use the eigenvectors of the laplacian matrix of the input graph as the low-dimensional representation of the data [4,12,13,14]. Given the adjacency matrix of the input graph, the laplacian matrix is defined as where is diagonal matrix with its diagonal element = . Now, given the number of clusters , the spectral clustering algorithm computes the first eigenvectors (of smallest eigenvalues) of matrix , and assigns a -dimensional coordinate vector to each node of graph . This coordinate representation of the vertices is then clustered again using other clustering method (usually k-means clustering).
In summary, the steps done in spectral clustering algorithm is presented in the table below [12]  Each data point from the -dimensional data points =1,…, represents a node in the original graph. Fuzzy random walk uses these data points to assign a membership value for each node.

Fuzzy random walk
Fuzzy random walk consists of two steps, the computation of the auxiliary matrix andmembership value assignment by random walk [8]. Consider the -dimensional data points =1,…, . First, wedefine a family of matrices ( ) with its entries ( ), as clusters, meanwhile large value corresponds to the case where all the nodes are highly connected, and thus diffusion occur instantaneously. We search for the intermediate value of , when there is enough time to diffuse, but the equilibrium is not yet reached. We search for a * value that satisfies * = 2 1 | | the adjustment of parameter 1 also gives the same meaning as but restricted to the range (0,1). The default value of 1 is 0.3.Then, wedefine the auxiliary matrix as ( * ). Let = [ ] be a diagonal matrix with its diagonal entries defined by = .
We also define the transition matrix , as = −1 And the random walk time step, This process is done to every node for each clusters. In summary, the steps done in our method, spectral clustering with fuzzy random walk is presented in table below  Input : Graph = ( , ) with nodes 1,2, … , and edge weight as pairwise similarity  For each node , compute and search the maximum . Let the corresponding node be  Remove and neighbor of from , and repeat the search. Stop until the next found satisfies <  Set the number found as the number of cluster , and the set as the cluster centers.

Results and discussion
The implementation of our method is done on PPI data of TP53 protein using the python programming language on software Canopy 1.6.2 (64-bit). The program is run on computer that has specs: Intel®Core TM i5-4200U @ 1.60 GHz, 2.30 GHz, 4.00 GB RAM and Windows 7Ultimate operating system ©2009 Microsoft Corporate 64-bit.
The PPI dataset of TP53 protein that found in Homo sapiens is obtained from STRING (Search Tool for the Retrieval of Interacting Genes) version 10 [11] database available online on string-db.org. This interaction networks consists of 131 proteins (nodes) and 1478 interactions (edges) are presented in the figure below. The cluster centers obtained from this PPI network consists of 6 proteins. The list of cluster centers, the protein name and density score is presented in table below.  From this list we search for optimal number of clusters from = 2 to = 6 using the silhouette coefficient ( ) of a node defined by [9] = − max , where ( ) denotes the intra cluster average distance to node and ( ) denotes the second-closest cluster average distance to node . A silhouette coefficient score for a clustering result is the average of every node silhouette coefficient and is in range (−1,1), where value close to 1 denotes a tightly grouped clusters with high dissimilarity between each clusters while value close to −1 denotes a clustering result that may not properly clustered. For this purpose we assign each node to a cluster based on the highest membership value and compute the silhouette coefficient score for = 2 to = 6 and set the top cluster centers to be the cluster center. The highest silhouette coefficient score is then chosen as the number of clusters. The figure below show the plot of silhouette coefficient score for = 2 to = 6  figure 2 we get the maximum silhouette coefficient value is obtained when the number of cluster is set to 5, and therefore we choose the number of clusters to be 5.
.Even though the main protein, TP53 is not one of the cluster centers, we found that all cluster center listed in the previous table has a direct interaction with protein TP53. This indicates all the cluster formed has some connection regarding its function with protein TP53. The cluster centers for this clustering result are FZR1, RPA1, BCL2L1, CREBBP and TP53BP2. Also, from the membership value, we can infer that some protein has a greater importance than other protein in the same cluster. Although it not shown here, but our method gives the similar performance when compared with spectral clustering only.Without using fuzzy random walk, we can only infer the group in which each

Conclusion and future work
Based on the analysis of our clustering results, we found our method on clustering TP53 PPI network produces a well-separated clusters with its membership value as an additional information on how these proteins interact with other clusters. The cluster centers found (FZR1, RPA1, BCL2L1, CREBBP and TP53BP2) are directly interacting with TP53 proteins, which indicates some connections with TP53 protein. It should be any further work to interpret the clustering result from our method to obtain more understanding by using data from the fields of biology and medical research.
For future work, we plan to study our method further not only to apply it to the biological dataset, but also a more general dataset in a graph form. In order to do that we would try to develop a more general method for detecting a cluster centers. Also, from computational approach, to achieve substantial performance over CPU approaches on a large dataset, we can use massively parallel computing approaches using GPU computing.