PERTANIKA JOURNAL OF SCIENCE AND TECHNOLOGY

Defining protein complexes by analysing the protein–protein interaction (PPI) networks is a crucial task in understanding the principles of a biological cell. In the last few decades, researchers have proposed numerous methods to explore the topological structure of a PPI network to detect dense protein complexes. In this paper, the overlapping protein complexes with different densities are predicted within an acceptable execution time using seed expanding model and topological structure of the PPI network (SETS). SETS depend on the relation between the seed and its neighbours. The algorithm was compared with six algorithms on six datasets: five for yeast and one for human. The results showed that SETS outperformed other algorithms in terms of F-measure, coverage rate and the number of complexes that have high similarity with real complexes.

• Adamcsek, B., Palla, G., Farkas, I. J., Derényi, I., & Vicsek, T. (2006). CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics, 22(8), 1021-1023. https://doi.org/10.1093/bioinformatics/btl039

• Aloy, P., Böttcher, B., Ceulemans, H., Leutwein, C., Mellwig, C., Fischer, S., Gavin, A.-C., Bork, P., Superti-Furga, G., & Serrano, L. (2004). Structure-based assembly of protein complexes in yeast. Science, 303(5666), 2026-2029. https://doi.org/10.1126/science.1092645

• Altaf-Ul-Amin, M., Shinbo, Y., Mihara, K., Kurokawa, K., & Kanaya, S. (2006). Development and implementation of an algorithm for detection of protein complexes in large interaction networks. BMC Bioinformatics, 7, Article 207. https://doi.org/10.1186/1471-2105-7-207

• Bader, G. D., & Hogue, C. W. (2003). An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4, Article 2. https://doi.org/10.1186/1471-2105-4-2

• Brohée, S., & van Helden, J. (2006). Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics, 7, Article 488. https://doi.org/10.1186/1471-2105-7-488

• Feng, J., Jiang, R., & Jiang, T. (2010). A max-flow-based approach to the identification of protein complexes using protein interaction and microarray data. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(3), 621-634. https://doi.org/10.1109/TCBB.2010.78

• Friedel, C. C., Krumsiek, J., & Zimmer, R. (2008). Bootstrapping the interactome: unsupervised identification of protein complexes in yeast. In M. Vingron & L. Wong (Eds.), Lecture notes in computer science: Research in computational molecular biology (Vol. 4955, pp. 3-16). Springer. https://doi.org/10.1007/978-3-540-78839-3_2.

• Goldberg, D. S., & Roth, F. P. (2003). Assessing experimentally derived interactions in a small world. Proceedings of the National Academy of Sciences, USA, 100(8), 4372-4376. https://doi.org/10.1073/pnas.0735871100

• Hartwell, L. H., Hopfield, J. J., Leibler, S., & Murray, A. W. (1999). From molecular to modular cell biology. Nature, 402(6761), C47-C52. https://doi.org/10.1038/35011540

• Jiang, P., & Singh, M. (2010). SPICi: A fast clustering algorithm for large biological networks. Bioinformatics, 26(8), 1105-1111. https://doi.org/10.1093/bioinformatics/btq078

• Krogan, N. J., Cagney, G., Yu, H., Zhong, G., Guo, X., Ignatchenko, A., Li, J., Pu, S., Datta, N., & Tikuisis, A. P. (2006). Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature, 440(7084), 637-643. https://doi.org/10.1038/nature04670

• Li, M., Chen, J. E., Wang, J. X., Hu, B., & Chen, G. (2008). Modifying the DPClus algorithm for identifying protein complexes based on new topological structures. BMC Bioinformatics, 9, Article 398. https://doi.org/10.1186/1471-2105-9-398

• Li, M., Chen, W., Wang, J., Wu, F. X., & Pan, Y. (2014). Identifying dynamic protein complexes based on gene expression profiles and PPI networks. BioMed Research International, 2014, Article 375262. https://doi.org/10.1155/2014/375262

• Li, X. L., Foo, C. S., Tan, S. H., & Ng, S. K. (2005). Interaction graph mining for protein complexes using local clique merging. Genome Informatics, 16(2), 260-269. https://doi.org/10.11234/gi1990.16.2_260

• Liu, G., Wong, L., & Chua, H. N. (2009). Complex discovery from weighted PPI networks. Bioinformatics, 25(15), 1891-1897. https://doi.org/10.1093/bioinformatics/btp311

• Liu, G., Yong, C. H., Wong, L., & Chua, H. N. (2010, December 18-21 ). Decomposing PPI networks for complex discovery [Paper presentation]. 2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Hong Kong, China. https://doi.org/10.1109/BIBM.2010.5706577.

• Ma, C. Y., Chen, Y. P. P., Berger, B., & Liao, C. S. (2017). Identification of protein complexes by integrating multiple alignment of protein interaction networks. Bioinformatics, 33(11), 1681-1688. https://doi.org/10.1093/bioinformatics/btx043

• 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 Bioinformatics, 8, Article 408. https://doi.org/10.1186/1471-2105-8-408

• Mewes, H. W., Amid, C., Arnold, R., Frishman, D., Güldener, U., Mannhaupt, G., Münsterkötter, M., Pagel, P., Strack, N., & Stümpflen, V. (2004). MIPS: Analysis and annotation of proteins from whole genomes. Nucleic Acids Research, 32(suppl_1), D41-D44. https://doi.org/10.1093/nar/gkh092

• Nepusz, T., Yu, H., & Paccanaro, A. (2012). Detecting overlapping protein complexes in protein-protein interaction networks. Nature Methods, 9(5), 471-472. https://doi.org/10.1038/nmeth.1938

• Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818. https://doi.org/10.1038/nature03607

• Peng, X., Wang, J., Peng, W., Wu, F. X., & Pan, Y. (2017). Protein–protein interactions: Detection, reliability assessment and applications. Briefings in Bioinformatics, 18(5), 798-819. https://doi.org/10.1093/bib/bbw066

• Pizzuti, C., & Rombo, S. E. (2014). Algorithms and tools for protein–protein interaction networks clustering, with a special focus on population-based stochastic methods. Bioinformatics, 30(10), 1343-1352. https://doi.org/10.1093/bioinformatics/btu034

• Pu, S., Wong, J., Turner, B., Cho, E., & Wodak, S. J. (2009). Up-to-date catalogues of yeast protein complexes. Nucleic Acids Research, 37(3), 825-831. https://doi.org/10.1093/nar/gkn1005

• Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, USA, 101(9), 2658-2663. https://doi.org/10.1073/pnas.0400054101

• Rives, A. W., & Galitski, T. (2003). Modular organization of cellular networks. Proceedings of the National Academy of Sciences, USA, 100(3), 1128-1133. https://doi.org/10.1073/pnas.0237338100

• Schlicker, A., Domingues, F. S., Rahnenführer, J., & Lengauer, T. (2006). A new measure for functional similarity of gene products based on Gene Ontology. BMC Bioinformatics, 7, Article 302. https://doi.org/10.1186/1471-2105-7-302

• Shannon, P., Markiel, A., Ozier, O., Baliga, N. S., Wang, J. T., Ramage, D., Amin, N., Schwikowski, B., & Ideker, T. (2003). Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Research, 13(11), 2498-2504. https://doi.org/10.1101/gr.1239303

• Tadaka, S., & Kinoshita, K. (2016). NCMine: Core-peripheral based functional module detection using near-clique mining. Bioinformatics, 32(22), 3454-3460. https://doi.org/10.1093/bioinformatics/btw488

• Van Dongen, S. M. (2000). Graph clustering by flow simulation [Doctoral dissertation, Utrecht University]. Utrecht University Publication. https://dspace.library.uu.nl/bitstream/handle/1874/848/full.pdf?sequence=1&isAllowed=y.

• Wang, J., Liu, B., Li, M., & Pan, Y. (2010). Identifying protein complexes from interaction networks based on clique percolation and distance restriction. BMC Genomics, 11, Article S10. https://doi.org/10.1186/1471-2164-11-S2-S10

• Wang, R., Liu, G., Wang, C., Su, L., & Sun, L. (2018). Predicting overlapping protein complexes based on core-attachment and a local modularity structure. BMC Bioinformatics, 19, Article 305. https://doi.org/10.1186/s12859-018-2309-9

• Wang, Y., You, Z., Li, X., Chen, X., Jiang, T., & Zhang, J. (2017). PCVMZM: Using the probabilistic classification vector machines model combined with a zernike moments descriptor to predict protein–protein interactions from protein sequences. International Journal of Molecular Sciences, 18(5), Article 1029. https://doi.org/10.3390/ijms18051029

• Xenarios, I., Salwinski, L., Duan, X. J., Higney, P., Kim, S. M., & Eisenberg, D. (2002). DIP, the database of interacting proteins: A research tool for studying cellular networks of protein interactions. Nucleic Acids Research, 30(1), 303-305. https://doi.org/10.1093/nar/30.1.303

• Zaki, N., Efimov, D., & Berengueres, J. (2013). Protein complex detection using interaction reliability assessment and weighted clustering coefficient. BMC Bioinformatics, 14, Article 163. https://doi.org/10.1186/1471-2105-14-163

• Zhao, J., & Lei, X. (2019). Detecting overlapping protein complexes in weighted PPI network based on overlay network chain in quotient space. BMC Bioinformatics, 20, Article 682. https://doi.org/10.1186/s12859-019-3256-9