Spectral clustering of protein sequences

Clustering protein sequences based on their evolutionary relationship is important for sequence annotation as structural and functional relationships can potentially be inferred. Most of the existing methods were based on simply thresholding a measure related to the distance between sequences. We mapped this problem into that of clustering the nodes of a weighted undirected graph in which each node corresponds to a protein sequence and the weights on the edges correspond to a measure of distance between two sequences. The goal is to partition such a graph into a set of discrete clusters whose members are homologs. By formulating the problem this way, it was possible to analyze the limitations that one might expect from earlier methods and we were able to provide a theoretical explanation of why spectral clustering methods should perform better for this problem. Then, we introduced a spectral method that partitions the graph into clusters by considering the random walk formulation on the graph and analyzing the perturbations to the stationary distribution of a Markov relaxation process. This is done by looking at the eigenvectors of the Markov transition matrix. The weights on the edges of the graphs that we used are a nonlinear transformation of the pairwise BLAST E-values, and the parameters of such nonlinear transformation were learned. We tested this algorithm on difficult sets of proteins whose relationships are known from the SCOP database [2, 4, 5]. Our method correctly identified many of the family/superfamily relationships. We found that the eigenvalue spectrum and in particular, the eigengaps provide useful indication on the number of clusters in the dataset. Using this approach the results obtained were much better than those obtained using other methods on the same datasets. In fact, we consistently observed that, the number of clusters obtained for a given set of proteins was close to the number of superfamilies in that set; there were fewer singletons; and the method correctly grouped most remote homologs. In our experiments, the quality of the clusters as quantified by a measure that combines sensitivity and specificity was consistently better (on average, improvements were: 84% over hierarchical clustering, 34% over connected component analysis (similar to GeneRAGE), and 72% over TribeMCL.

In collaboration with Rajkumar Sashidaran (Stanford University), we have recently released SCPS, a fast multi-platform implementation of the spectral method that enables us to detect protein families on a genome-wide scale [1]. We are currently investigating how to improve these results using sequence-profiles scores [3].