k-Partite cliques of protein interactions: A novel subgraph topology for functional coherence analysis on PPI networks

• We propose to transform PPI networks into induced KK-partite graphs.
• We introduce k  -partite protein cliques in KK-partite graphs to study PPI networks.
• k-Partite cliques, especially their each partite, share high functional coherence.
• k-Partite clique is a functionally coherent but not necessarily dense novel subgraphs.

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-partiteK-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-partiteK-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.