k-Partite cliques of protein interactions: A novel subgraph topology for functional coherence analysis on PPI networks.
Many studies are aimed at identifying dense clusters/subgraphs from protein-protein interaction (PPI) networks for protein function prediction. However, the prediction performance based on the dense clusters is actually worse than a simple guilt-by-association method using neighbor counting ideas. This indicates that the local topological structures and properties of PPI networks are still open to new theoretical investigation and empirical exploration. We introduce a novel topological structure called k-partite cliques of protein interactions-a functionally coherent but not-necessarily dense subgraph topology in PPI networks-to study PPI networks. A k-partite protein clique is a maximal k-partite clique comprising two or more nonoverlapping protein subsets between any two of which full interactions are exhibited. In the detection of PPI's maximal k-partite cliques, we propose to transform PPI networks into induced K-partite graphs where edges exist only between the partites. Then, we present a maximal k-partite clique mining (MaCMik) algorithm to enumerate maximal k-partite cliques from K-partite graphs. Our MaCMik algorithm is then applied to a yeast PPI network. We observed interesting and unusually high functional coherence in k-partite protein cliques-the majority of the proteins in k-partite protein cliques, especially those in the same partites, share the same functions, although k-partite protein cliques are not restricted to be dense compared with dense subgraph patterns or (quasi-)cliques. The idea of k-partite protein cliques provides a novel approach of characterizing PPI networks, and so it will help function prediction for unknown proteins.
Advanced Analytics Institute, University of Technology Sydney, Sydney, Australia.
Qian
Q
Liu
Yi-Ping Phoebe
YP
Chen
Jinyan
J
Li
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D005656:Fungal Proteins / Q000378:metabolism; D005786:Gene Expression Regulation; D008954:Models, Biological; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000378:metabolism; D015398:Signal Transduction; D012984:Software; D015003:Yeasts / Q000378:metabolism
D005656:Fungal Proteins; D011506:Proteins
Maximal k-partite clique; Protein functional coherence; graphs; k-Partite protein cliques