Interaction Graph Mining for Protein Complexes Using Local Clique Merging

Xiao-Li Li[1] (
Soon-Heng Tan[1],[2] (
Chuan-Sheng Foo[1],[3] (
See-Kiong Ng[1] (

[1]Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613
[2]School of Computing, National University of Singapore, Singapore 119260
[3]Computer Science Department, Stanford University, Serra Mall, Stanford CA 94305-9025 USA


While recent technological advances have made available large datasets of experimentally-detected pairwise protein-protein interactions, there is still a lack of experimentally-determined protein complex data. To make up for this lack of protein complex data, we explore the mining of existing protein interaction graphs for protein complexes. This paper proposes a novel graph mining algorithm to detect the dense neighborhoods (highly connected regions) in an interaction graph which may correspond to protein complexes. Our algorithm first locates local cliques for each graph vertex (protein) and then merge the detected local cliques according to their affinity to form maximal dense regions. We present experimental results with yeast protein interaction data to demonstrate the effectiveness of our proposed method. Compared with other existing techniques, our predicted complexes can match or overlap significantly better with the known protein complexes in the MIPS benchmark database. Novel protein complexes were also predicted to help biologists in their search for new protein complexes.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics