Overlap maximum matching ratio (OMMR): a new measure to evaluate overlaps of essential modules

Abstract

Protein complexes are the basic units of macro-molecular organizations and help us to understand the cell’s mechanism. The development of the yeast two-hybrid, tandem affinity purification, and mass spectrometry high-throughput proteomic techniques supplies a large amount of protein-protein interaction data, which make it possible to predict overlapping complexes through computational methods. Research shows that overlapping complexes can contribute to identifying essential proteins, which are necessary for the organism to survive and reproduce, and for life’s activities. Scholars pay more attention to the evaluation of protein complexes. However, few of them focus on predicted overlaps. In this paper, an evaluation criterion called overlap maximum matching ratio (OMMR) is proposed to analyze the similarity between the identified overlaps and the benchmark overlap modules. Comparison of essential proteins and gene ontology (GO) analysis are also used to assess the quality of overlaps. We perform a comprehensive comparison of serveral overlapping complexes prediction approaches, using three yeast protein-protein interaction (PPI) networks. We focus on the analysis of overlaps identified by these algorithms. Experimental results indicate the important of overlaps and reveal the relationship between overlaps and identification of essential proteins.

Keywords

Protein-protein interaction network / Essential protein modules / Overlap / Overlap maximum matching ratio

References

[1] Adamcsek, B., Palla, G., Farkas, I.J., , 2006. CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics, 22(8): 1021-1023. [

[2] Bader, G.D., Hogue, C.W.V., 2003. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinform., 4: 2.1-2.27. [

[3] Boyle, E.I., Weng, S., Gollub, J., , 2004. GO::Term-Finder—open source software for accessing gene ontology information and finding significantly enriched Gene Ontology terms associated with a list of genes. Bioinformatics, 20(18): 3710-3715. [

[4] Chen, B., Shi, J., Zhang, S., , 2013. Identifying protein complexes in protein-protein interaction networks by using clique seeds and graph entropy. Proteomics, 13(2): 269-277. [

[5] Cherry, J.M., Adler, C., Ball, C., , 1998. SGD: Saccharomyces Genome Database. Nucl. Acids Res., 26(1): 73-79. [

[6] Dezső, Z., Oltvai, Z.N., Barabási, A.L., 2003. Bioinformatics analysis of experimentally determined protein complexes in the yeast Saccharomyces cerevisiae. Genome Res., 13: 2450-2454. [

[7] Enright, A.J., van Dongen, S., Ouzounis, C.A., 2002. An efficient algorithm for large-scale detection of protein families. Nucl. Acids Res., 30(7): 1575-1584. [

[8] Gavin, A.C., Aloy, P., Grandi, P., , 2006. Proteome survey reveals modularity of the yeast cell machinery. Nature, 440: 631-636. [

[9] Han, J.D., Bertin, N., Hao, T., , 2004. Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature, 430: 88-93. [

[10] Hart, G.T., Lee, I., Marcotte, E.M., 2007. A high-accuracy consensus map of yeast protein complexes reveals modular nature of gene essentiality. BMC Bioinform., 8: 236.1-236.11. [

[11] Hu, H., Yan, X., Huang, Y., , 2005. Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics, 21(suppl 1): i213-i221. [

[12] Jiang, P., Singh, M., 2010. SPICi: a fast clustering algorithm for large biological networks. Bioinformatics, 26(8): 1105-1111. [

[13] Krogan, N., Cagney, G., Yu, H., , 2006. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature, 440: 637-643. [

[14] Lei, X., Wu, S., Ge, L., , 2013. Clustering and overlapping modules detection in PPI network based on IBFO. Proteomics, 13(2): 278-290. [

[15] Leung, H.C.M., Xiang, Q., Yiu, S.M., , 2009. Predicting protein complexes from PPI data: a core-attachment approach. J. Comput. Biol., 16(2): 133-144. [

[16] Liu, G., Wong, L., Chua, H.N., 2009. Complex discovery from weighted PPI networks. Bioinformatics, 25(15): 1891-1897. [

[17] Macropol, K., Can, T., Singh, A.K., 2009. RRW: repeated random walks on genome-scale protein networks for local cluster discovery. BMC Bioinform., 10: 283.1-283.10.[

[18] Maraziotis, I.A., Dimitrakopoulou, K., Bezerianos, A., 2007. Growing functional modules from a seed protein via integration of protein interaction and gene expression data. BMC Bioinform., 8: 408.1-408.15. [

[19] Mewes, H.W., Frishman, D., Mayer, K.F.X., , 2006. MIPS: analysis and annotation of proteins from whole genomes in 2005. Nucl. Acids Res., 34(suppl 1): D169-D172. [

[20] Nepusz, T., Yu, H., Paccanaro, A., 2012. Detecting overlapping protein complexes in protein-protein interaction networks. Nat. Methods, 9(5): 471-472. [

[21] Ni, W.Y., Xiong, H.J., Zhao, B.H., , 2013. Predicting overlapping protein complexes in weighted interactome networks. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 14(10): 756-765. [

[22] Palla, G., Derényi, I., Farkas, I., , 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435: 814-818. [

[23] Pu, S., Wong, J., Turner, B., , 2009. Up-to-date catalogues of yeast protein complexes. Nucl. Acids Res., 37(3): 825-831. [

[24] Shih, Y.K., Parthasarathy, S., 2012. Identifying functional modules in interaction networks through overlapping Markov clustering. Bioinformatics, 28(18): i473-i479. [

[25] Stark, C., Breitkreutz, B.J., Reguly, T., , 2006. BioGRID: a general repository for interaction datasets. Nucl. Acids Res., 34(suppl 1): D535-D539. [

[26] Wu, M., Li, X., Kwoh, C.K., , 2009. A core-attachment based method to detect protein complexes in PPI networks. BMC Bioinform., 10: 169.1-169.16. [

[27] Zhang, R., Lin, Y., 2009. DEG 5.0, a database of essential genes in both prokaryotes and eukaryotes. Nucl. Acids Res., 37(suppl 1): D455-D458. [

[28] Zhao, B., Wang, J., Li, M., , 2014. Prediction of essential proteins based on overlapping essential modules. IEEE Trans. NanoBiosci., 13(4): 415-424. [