title: Predicting protein complexes from weighted protein-protein interaction graphs with a novel unsupervised methodology: Evolutionary enhanced Markov clustering.
abstract: OBJECTIVE
  Proteins are considered to be the most important individual components of biological systems and they combine to form physical protein complexes which are responsible for certain molecular functions. Despite the large availability of protein-protein interaction (PPI) information, not much information is available about protein complexes. Experimental methods are limited in terms of time, efficiency, cost and performance constraints. Existing computational methods have provided encouraging preliminary results, but they phase certain disadvantages as they require parameter tuning, some of them cannot handle weighted PPI data and others do not allow a protein to participate in more than one protein complex. In the present paper, we propose a new fully unsupervised methodology for predicting protein complexes from weighted PPI graphs.
  
  
  METHODS
  The proposed methodology is called evolutionary enhanced Markov clustering (EE-MC) and it is a hybrid combination of an adaptive evolutionary algorithm and a state-of-the-art clustering algorithm named enhanced Markov clustering. EE-MC was compared with state-of-the-art methodologies when applied to datasets from the human and the yeast Saccharomyces cerevisiae organisms.
  
  
  RESULTS
  Using public available datasets, EE-MC outperformed existing methodologies (in some datasets the separation metric was increased by 10-20%). Moreover, when applied to new human datasets its performance was encouraging in the prediction of protein complexes which consist of proteins with high functional similarity. In specific, 5737 protein complexes were predicted and 72.58% of them are enriched for at least one gene ontology (GO) function term.
  
  
  CONCLUSIONS
  EE-MC is by design able to overcome intrinsic limitations of existing methodologies such as their inability to handle weighted PPI networks, their constraint to assign every protein in exactly one cluster and the difficulties they face concerning the parameter tuning. This fact was experimentally validated and moreover, new potentially true human protein complexes were suggested as candidates for further validation using experimental techniques.
authors.affiliation: Department of Computer Engineering and Informatics, University of Patras, Building B University Campus Rio, Zip Code: 26500, Patras, Greece. Electronic address: theofilk@ceid.upatras.gr.
authors.forename: Konstantinos
authors.initials: K
authors.lastname: Theofilatos
authors.affiliation: Department of Computer Engineering and Informatics, University of Patras, Building B University Campus Rio, Zip Code: 26500, Patras, Greece.
authors.forename: Niki
authors.initials: N
authors.lastname: Pavlopoulou
authors.affiliation: Department of Computer Engineering and Informatics, University of Patras, Building B University Campus Rio, Zip Code: 26500, Patras, Greece.
authors.forename: Christoforos
authors.initials: C
authors.lastname: Papasavvas
authors.affiliation: Department of Computer Engineering and Informatics, University of Patras, Building B University Campus Rio, Zip Code: 26500, Patras, Greece.
authors.forename: Spiros
authors.initials: S
authors.lastname: Likothanassis
authors.affiliation: Department of Computer Engineering and Informatics, University of Patras, Building B University Campus Rio, Zip Code: 26500, Patras, Greece.
authors.forename: Christos
authors.initials: C
authors.lastname: Dimitrakopoulos
authors.affiliation: Department of Agricultural Technology, Technological Educational Institute of Kalamata, Antikalamos, Zip Code: 24100, Kalamata, Greece.
authors.forename: Efstratios
authors.initials: E
authors.lastname: Georgopoulos
authors.affiliation: Department of Electrical Engineering, Katholieke Universiteit, Kasteelpark Arenberg 10 - box 2440, Zip Code: 3001, Leuven Belgium; iMinds Future Health Department, Katholieke Universiteit, Oude Markt 13 - bus 5005, Zip Code: 3000, Leuven, Belgium.
authors.forename: Charalampos
authors.initials: C
authors.lastname: Moschopoulos
authors.affiliation: Department of Computer Engineering and Informatics, University of Patras, Building B University Campus Rio, Zip Code: 26500, Patras, Greece; Department of Social Work, School of Sciences of Health and Care, Technological Educational Institute of Patras, M. Alexandrou str. 1, Zip Code: 263 34, Patras, Greece. Electronic address: mavroudi@ceid.upatras.gr.
authors.forename: Seferina
authors.initials: S
authors.lastname: Mavroudi
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods; D030562:Databases, Protein; D006801:Humans; D008390:Markov Chains; D025941:Protein Interaction Mapping / Q000379:methods*; D060066:Protein Interaction Maps / Q000502:physiology; D012441:Saccharomyces cerevisiae
keywords: Evolutionary algorithms; Evolutionary enhanced Markov clustering; Functional characterization of proteins and protein complexes; Genetic algorithms; Large scale biological networks analysis; Protein complex prediction; Weighted protein–protein interaction networks