Casbon J A, Saqi M A S. Spectral clustering of protein sequences[J]. Nucleic acids research

An important problem in genomics is automatic-ally clustering homologous proteins when only sequence information is available. Most methods for clustering proteins are local, and are based on simply thresholding a measure related to sequence distance. We first show how locality limits the per-formance of such methods by analysing the distribu-tion of distances between protein sequences. We then present a global method based on spectral clustering and provide theoretical justification of why it will have a remarkable improvement over local methods. We extensively tested our method and compared its performance with other local methods on several subsets of the SCOP (Structural Classification of Proteins) database, a gold standard for protein struc-ture classification. We consistently observed that, the number of clusters that we obtain for a given set of proteins is close to the number of superfamilies in that set; there are fewer singletons; and the method correctly groups most remote homologs. In our experiments, the quality of the clusters as quantif-ied by a measure that combines sensitivity and specificity was consistently better [on average, improvements were 84 % over hierarchical clustering, 34 % over Connected Component Analysis (CCA) (similar to GeneRAGE) and 72 % over another global method, TribeMCL]