Identifying Functional Groups by Finding Cliques and Near-Cliques in Protein Interaction Networks

Many cellular processes are performed by a group of proteins rather than by individual proteins. When visualized in a protein-protein interaction network, proteins in a same biological unit often form a highly connected subgraph but loosely connected to the rest of the network. Therefore, finding a highly connected subgraph provides useful information to predict the function or protein complex of uncharacterized proteins in the highly connected subgraph. We have developed an efficient algorithm and program for finding cliques and near-cliques in a protein-protein interaction network. Analysis of the interaction network of yeast proteins demonstrates that 77% of the near-cliques identified by our algorithm have at least one function shared by all the proteins within a near- clique, and that 68% of the near-cliques show a good agreement with experimentally determined protein complexes catalogued in MIPS.