An Effective Link-Based Clustering Algorithm for Detecting Overlapping Protein Complexes in Protein-Protein Interaction Networks
Lun Hu, Jun Zhang, Xiangyu Pan, Xin Luo, Huaqiang Yuan
Abstract
Protein complexes are one most important kind of functional modules for biological processes in cells. In this regard, their detection is vital for understanding the principle of cell organization and function. A variety of clustering algorithms have been developed to detect protein complexes from protein-protein interaction (PPI) networks. However, most of them are based on a certain clustering criterion. Given the fact that proteins should interact with each other rather than act independently, we reason that clustering upon interactions can better characterize protein complexes than upon proteins, thus improving the detection accuracy. To this end, a link-based clustering algorithm has been proposed in this paper to effectively detect overlapping protein complexes. It first measures the similarity between pairwise interactions from the perspectives of network topology and Gene Ontology. The problem of protein complex detection is then formulated as an optimization problem of link-based clustering, which is resolved by the proposed algorithm. This proposed algorithm explores the intrinsic correlation between protein complexes and interactions for detecting functionally significant protein complexes. Experimental results on five independent PPI datasets collected from the species of yeast and human demonstrate that compared with state-of-the-art algorithms, the proposed algorithm has significantly improved the detection accuracy for protein complexes.