High functional coherence in k-partite protein cliques of protein interaction networks

We introduce a new topological concept called <i>k-partite protein cliques</i> to study protein interaction (PPI) networks. In particular, we examine functional coherence of proteins in <i>k</i>-partite protein cliques. A <i>k</i>-partite protein clique is a <i>k</i>-partite maximal clique comprising two or more nonoverlapping protein subsets between any two of which full interactions are exhibited. In the detection of PPI’s <i>k</i>-partite maximal cliques, we propose to transform PPI networks into induced <i>K</i>-partite graphs with proteins as vertices where edges only exist among the graph’s partites. Then, we present a <i>k</i>-partite maximal clique mining (MaCMik) algorithm to enumerate<i> k</i>-partite maximal cliques from <i>K</i>-partite graphs. Our MaCMik algorithm is applied to a yeast PPI network. We observe that there does exist interesting and unusually high functional coherence in <i>k</i>-partite protein cliques—most proteins in<i> k</i>-partite protein cliques, especially those in the same partites, share the same functions. Therefore, the idea of <i>k</i>-partite protein cliques suggests a novel approach to characterizing PPI networks, and may help function prediction for unknown proteins.<br />