Published online 17 March 2006
Article |
Spectral clustering of protein sequences
Bioinformatics Group, The Genome Centre, Barts and The London School of Medicine, Queen Mary, University of London Charterhouse Square, London EC1M 6BQ, UK
*To whom corresponding should be addressed at Molecular Biophysics and Biochemistry Department, Yale University, 266 Whitney Avenue, New Haven, CT 06520-8114, USA. Tel: +1 203 4325065; Fax: +1 203 432 5175 Email: albertopaccanaro{at}yale.edu
Received November 9, 2005. Revised January 31, 2006. Accepted January 31, 2006.
An important problem in genomics is automatically 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 performance of such methods by analysing the distribution 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 structure 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 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 (CCA) (similar to GeneRAGE) and 72% over another global method, TribeMCL].
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  G. A. Pavlopoulos, C. N. Moschopoulos, S. D. Hooper, R. Schneider, and S. Kossida jClust: a clustering and visualization toolbox Bioinformatics, August 1, 2009; 25(15): 1994 - 1996. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. M. Joseph and D. Durand Family classification without domain chaining Bioinformatics, June 15, 2009; 25(12): i45 - i53. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. D. Hooper, I. J. Anderson, A. Pati, D. Dalevi, K. Mavromatis, and N. C. Kyrpides Integration of phenotypic metadata and protein similarity in Archaea using a spectral bipartitioning approach Nucleic Acids Res., April 1, 2009; 37(7): 2096 - 2104. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. V. Tetko, I. V. Rodchenkov, M. C. Walter, T. Rattei, and H.-W. Mewes Beyond the 'best' match: machine learning annotation of protein sequences by integration of different sources of information Bioinformatics, March 1, 2008; 24(5): 621 - 628. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. E. Suzek, H. Huang, P. McGarvey, R. Mazumder, and C. H. Wu UniRef: comprehensive and non-redundant UniProt reference clusters Bioinformatics, May 15, 2007; 23(10): 1282 - 1288. [Abstract] [Full Text] [PDF]
|
|