Interaction graph mining for protein complexes using local clique merging.
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.
Li
Xiao-Li
XL
Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613. xlli@i2r.a-star.edu.sg
Tan
Soon-Heng
SH
Foo
Chuan-Sheng
CS
Ng
See-Kiong
SK
D000465:Algorithms; D046912:Multiprotein Complexes / Q000737:chemistry / Q000502:physiology*; D011237:Predictive Value of Tests; D025941:Protein Interaction Mapping / Q000379:methods / Q000706:statistics & numerical data*; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry
D046912:Multiprotein Complexes; D029701:Saccharomyces cerevisiae Proteins