Fast and Accurate Method for Identifying High-quality Protein-interaction Modules by Clique Merging and Its Application to Yeast

Molecular networks in cells are organized into functional modules, where genes in the same module interact densely with each other and participate in the same biological process. Thus, identification of modules from molecular networks is an important step toward a better understanding of how cells function through the molecular networks. Here, we propose a simple, automatic method, called MC(2), to identify functional modules by enumerating and merging cliques in the protein-interaction data from large-scale experiments. Application of MC(2) to the S. cerevisiae protein-interaction data produces 84 modules, whose sizes range from 4 to 69 genes. The majority of the discovered modules are significantly enriched with a highly specific process term (at least 4 levels below root) and a specific cellular component in Gene Ontology (GO) tree. The average fraction of genes with the most enriched GO term for all modules is 82% for specific biological processes and 78% for specific cellular components. In addition, the predicted modules are enriched with coexpressed proteins. These modules are found to be useful for annotating unknown genes and uncovering novel functions of known genes. MC(2) is efficient, and takes only about 5 min to identify modules from the current yeast gene interaction network with a typical PC (Intel Xeon 2.5 GHz CPU and 512 MB memory). The CPU time of MC(2) is affordable (12 h) even when the number of interactions is increased by a factor of 10. MC(2) and its results are publicly available on http://theory.med.buffalo.edu/MC2.