Complexes discovery from weighted protein-protein interaction networks

Motivation: Protein complexes are important for understanding the principles of cellular organization and function. With the increasing availability of large amounts of high-throughput protein-protein interaction (PPI) data, a vast number of algorithms have been proposed which seek to discover protein complexes from PPI networks. However, such algorithms are hindered by the high rate of noise in high-throughput PPI data, including spurious and missing interactions, which makes it difficult to predict complexes accurately. Results: we propose a method which attempts to construct a weighted protein network in order to induce a specific rate of noise in high-throughput PPI data, which consists of two steps. Step 1, a novel weighting scheme called SCS is adapted to multiple data sources. Each protein pair is weighted not only by the Hypergeometric method, to calculate a similarity score, but also considering the network topology property to penalize proteins with fewer common neighborhoods. Step 2, the weighted graph which produced in the first step is clustered, and the clustered interaction networks are also cross-validated against the confirmed protein complexes present in the MIPS and CYC2008 database. The results of our experimental work show that: (i) the proposed method can improve the performance of clustering results considerably; (ii) the proposed method effectively reduces the impact of random noise on clustering performance; and (iii) the general performance of the proposed scoring method is better than Iterative AdjstCD.