title: Evaluation and improvements of clustering algorithms for detecting remote homologous protein families.
abstract: BACKGROUND
  An important problem in computational biology is the automatic detection of protein families (groups of homologous sequences). Clustering sequences into families is at the heart of most comparative studies dealing with protein evolution, structure, and function. Many methods have been developed for this task, and they perform reasonably well (over 0.88 of F-measure) when grouping proteins with high sequence identity. However, for highly diverged proteins the performance of these methods can be much lower, mainly because a common evolutionary origin is not deduced directly from sequence similarity. To the best of our knowledge, a systematic evaluation of clustering methods over distant homologous proteins is still lacking.
  
  
  RESULTS
  We performed a comparative assessment of four clustering algorithms: Markov Clustering (MCL), Transitive Clustering (TransClust), Spectral Clustering of Protein Sequences (SCPS), and High-Fidelity clustering of protein sequences (HiFix), considering several datasets with different levels of sequence similarity. Two types of similarity measures, required by the clustering sequence methods, were used to evaluate the performance of the algorithms: the standard measure obtained from sequence-sequence comparisons, and a novel measure based on profile-profile comparisons, used here for the first time.
  
  
  CONCLUSIONS
  The results reveal low clustering performance for the highly divergent datasets when the standard measure was used. However, the novel measure based on profile-profile comparisons substantially improved the performance of the four methods, especially when very low sequence identity datasets were evaluated. We also performed a parameter optimization step to determine the best configuration for each clustering method. We found that TransClust clearly outperformed the other methods for most datasets. This work also provides guidelines for the practical application of clustering sequence methods aimed at detecting accurately groups of related protein sequences.
authors: Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil. juliana.silva_bernardes@upmc.fr.|Sorbonne Universités, UPMC Univ Paris 06, UMR 7238, Biologie Computationnelle et Quantitative, Paris, France. juliana.silva_bernardes@upmc.fr.
authors: Juliana S
authors: JS
authors: Bernardes
authors: Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil. fjimenez@cos.ufrj.br.
authors: Fabio R J
authors: FR
authors: Vieira
authors: Engenharia de Computação e Informação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil. lmmc@poli.ufrj.br.
authors: Lygia M M
authors: LM
authors: Costa
authors: Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil. gerson@cos.ufrj.br.
authors: Gerson
authors: G
authors: Zaverucha
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019143:Evolution, Molecular; D006801:Humans; D005810:Multigene Family; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods
chemical_list: D011506:Proteins
references: Genome Biol. 2006;7(1):R8
references: 16507141
references: BMC Bioinformatics. 2010;11:120
references: 20214776
references: J Comput Biol. 1999 Fall-Winter;6(3-4):281-97
references: 10582567
references: Nat Rev Genet. 2011 Oct;12(10):692-702
references: 21878963
references: Nucleic Acids Res. 2000 Jan 1;28(1):257-9
references: 10592240
references: Nucleic Acids Res. 2006;34(5):1571-80
references: 16547200
references: Bioinformatics. 2012 Apr 15;28(8):1078-85
references: 22368255
references: Comput Appl Biosci. 1996 Apr;12(2):95-107
references: 8744772
references: Nat Methods. 2010 Jun;7(6):419-20
references: 20508635
references: J Mol Biol. 1990 Oct 5;215(3):403-10
references: 2231712
references: BMC Bioinformatics. 2007;8:396
references: 17941985
references: BMC Bioinformatics. 2010;11:89
references: 20158924
references: Nucleic Acids Res. 2002 Apr 1;30(7):1575-84
references: 11917018
references: Nucleic Acids Res. 2000 Jan 1;28(1):254-6
references: 10592239
references: Bioinformatics. 2005 Apr 1;21(7):951-60
references: 15531603
references: Nat Methods. 2012 Feb;9(2):173-5
references: 22198341
references: Proteins. 2003 Nov 15;53(3):683-92
references: 14579359
references: BMC Bioinformatics. 2009;10:150
references: 19445721
references: BMC Bioinformatics. 2011;12:116
references: 21513511