Multifunctional proteins revealed by overlapping clustering in protein interaction network

Abstract

Motivation: Multifunctional proteins perform several functions. They are expected to interact specifically with distinct sets of partners, simultaneously or not, depending on the function performed. Current graph clustering methods usually allow a protein to belong to only one cluster, therefore impeding a realistic assignment of multifunctional proteins to clusters.

Results: Here, we present Overlapping Cluster Generator (OCG), a novel clustering method which decomposes a network into overlapping clusters and which is, therefore, capable of correct assignment of multifunctional proteins. The principle of OCG is to cover the graph with initial overlapping classes that are iteratively fused into a hierarchy according to an extension of Newman's modularity function. By applying OCG to a human protein-protein interaction network, we show that multifunctional proteins are revealed at the intersection of clusters and demonstrate that the method outperforms other existing methods on simulated graphs and PPI networks.

Availability: This software can be downloaded from http://tagc.univ-mrs.fr/welcome/spip.php?rubrique197

Contact: brun@tagc.univ-mrs.fr

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Flowchart of the OCG algorithm. The graph is covered by an initial overlapping class system. The initial classes are hierarchically fused optimizing the modularity of the partition, leading to overlapping clusters.

Fig. 2.

(A) Theoretical partition composed of 200 vertices. The four overlapping regions contain 10 vertices each. (B) Comparison of OCG performance, according to the initial class system chosen, when applied to simulated graphs with different edge probabilities (P_i=0.15, 0.20, 0.25, from light grey to black). Results are represented in ROC space.

Fig. 3.

(A) Topological and functional features of multi- versus monoclustered proteins. For each feature, the distributions of mono- and multiclustered proteins are represented by boxplots (line = median; dot = mean). (B) Gene Ontology terms overrepresented among multiclustered proteins [Image created by SimCT (Hermann et al., 2009)].

Fig. 4.

Comparison of the performances of CFinder, Link Communities and OCG when applied to different random graphs (A) Erdös-Rényi; (B) Random spanning trees; (C) Geo3D with different edge probabilities (p_i=0.20, 0.25,…, 0.45, 0.50, from light grey to black). Results are represented in ROC space.