Identifying Essential Proteins in Dynamic PPI Network with Improved FOA


  • Xiujuan Lei School of Computer Science Shaanxi Normal University Xian 710119,Shaanxi, China
  • Siguo Wang School of Computer Science Shaanxi Normal University Xian 710119,Shaanxi, China
  • Linqiang Pan 1. Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China School of Automation Huazhong University of Science and Technology Wuhan 430074, Hubei, China 2. School of Electric and Information Engineering Zhengzhou University of Light Industry Zhengzhou 450002, Henan, China


essential proteins, protein-protein interaction (PPI), dynamic PPI networks, subcellular localization data, fruit fly optimization algorithm (FOA)


Identification of essential proteins plays an important role for understanding the cellular life activity and development in postgenomic era. Identification of essential proteins from the protein-protein interaction (PPI) networks has become a hot topic in recent years. In this work, fruit fly optimization algorithm (FOA) is extended for identifying essential proteins, the extended algorithm is called EPFOA, which merges FOA with topological properties and biological information for essential proteins identification. The algorithm EPFOA has the advantage of identifying multiple essential proteins simultaneously rather than completely relying on ranking score identification individually. The performance of EPFOA is analyzed on dynamic PPI networks, which are constructed by combining the gene expression data. The experimental results demonstrate that EPFOA is more efficient in detecting essential proteins than the state-of-the-art essential proteins detection methods.


Binder, J. X., Pletscher-Frankild, S., Tsafou, K., Stolte, C., O'Donoghue, S. I., Schneider, R., Jensen, L. J. (2014); COMPARTMENTS: Unification and Visualization of Protein Subcellular Localization Evidence, Database, bau012, 2014.

Bocu, R., Tabirca, S. (2011); The Flag-based Algorithm - A Novel Greedy Method that Optimizes Protein Communities Detection, International Journal of Computers Communications & Control, 6(1), 33-44, 2011.

Bonacich, P. (1987); Power and Centrality: A Family of Measures, American Journal of Sociology, 92(5), 1170-1182, 1987.

Cherry, J. M., Adler, C., Ball, C., Chervitz, S. A., Dwight, S. S., Hester, E. T., Schroeder, M. (1998); SGD: Saccharomyces Genome Database, Nucleic Acids Research, 26(1), 73, 1998.

Consortium, G. O. (2015); Gene Ontology Consortium: Going Forward, Nucleic Acids Research, 43 (Database issue), 1049-1056, 2015.

Consortium, G. O., Blake, J. A., Dolan, M., Drabkin, H., Hill, D. P., Li, N., Buza, T. (2013); Gene Ontology Annotations and Resources, Nucleic Acids Research, 41(D1), 530-535, 2013.

Cullen, L. M., Arndt, G. M. (2005); Genome-Wide Screening for Gene Function Using RNAi in Mammalian Cells, Immunology Cell Biology, 83(3), 217-223, 2005.

Dzitac, I. (2015); Impact of Membrane Computing and P Systems in ISI WoS. Celebrating the 65th Birthday of Gheorghe Paun, International Journal of Computers Communications & Control, 10(5), 617-626, 2015.

Estrada, E., Rodriguez-Velázquez, J. A. (2005); Subgraph Centrality in Complex Networks, Physical Review E Statistical Nonlinear Soft Matter Physics, 71(2), 056103, 2005.

Gavin, A. C., Aloy, P., Grandi, P., Krause, R., Boesche, M., Marzioch, M., Dampelfeld, B. (2006); Proteome Survey Reveals Modularity of The Yeast Cell Machinery, Nature, 440(7084), 631-636, 2006.

Giaever, G., Chu, A. M., Ni, L., Connelly, C., Riles, L., Véronneau, S., André, B. (2002); Functional Profiling of the Saccharomyces Cerevisiae Genome, Nature, 418(6896), 387, 2002.

Gill, N., Singh, S., Aseri, T. C. (2014); Computational Disease Gene Prioritization: An Appraisal, Journal of Computational Biology A Journal of Computational Molecular Cell Biology, 21(6), 456-465, 2014.

Hsing, M., Byler, K. G.,Cherkasov, A. (2008); The Use of Gene Ontology Terms for Predicting Highly-Connected 'Hub' Nodes in Protein-Protein Interaction Networks, BMC Systems Biology, 2(1), 1-14, 2008.

Jeong, H., Mason, S. P., Barabási, A. L., Oltvai, Z. N. (2001); Lethality and Centrality in Protein Networks, Nature, 411(6833), 41-42, 2001.

Jimenezsanchez, G., Childs, B., Valle, D. (2001); Human Disease Genes, Nature, 409(6822), 853-855, 2001.

Lei, X., Wang, F., Wu, F. X., Zhang, A., Pedrycz, W. (2016); Protein Complex Identification Through Markov Clustering with Firefly Algorithm on Dynamic Protein-Protein Interaction Networks, Information Sciences, 329(6), 303-316, 2016.

Lei, X., Wang, S., Pan, L. (2017); Predicting Essential Proteins Based on Gene Expression Data, Subcellular Localization and PPI Data. Bio-inspired Computing: Theories and Applications: 12th International Conference, Proceedings of, 92-105, 2017.

Li, M., Lu, Y., Wang, J., Wu, F. X., Pan, Y. (2015); A Topology Potential-Based Method for Identifying Essential Proteins from PPI Networks, IEEE/ACM Transactions on Computational Biology Bioinformatics, 12(2), 372, 2015.

Li, M., Wang, J., Chen, X., Wang, H., Pan, Y. (2011); A Local Average Connectivity-Based Method for Identifying Essential Proteins from the Network Level, Computational Biology Chemistry, 35(3), 143-150, 2011.

Li, M., Wang, J., Wang, H., Pan, Y. (2012); Identification of Essential Proteins Based on Edge Clustering Coefficient, IEEE/ACM Transactions on Computational Biology Bioinformatics, 9(4), 1070, 2012.

Li, M., Zhang, H., Wang, J. X., Pan, Y. (2012); A New Essential Protein Discovery Method Based on the Integration of Protein-Protein Interaction and Gene Expression Data, BMC Systems Biology, 6(1), 15, 2012.

Luo, J., Kuang, L. (2014); A New Method for Predicting Essential Proteins Based on Dynamic Network Topology and Complex Information, Computational Biology Chemistry, 52(C), 34, 2014.

Mewes, H. W., Frishman, D., Mayer, K. F. X., Münsterkötter, M., Noubibou, O., Pagel, P., St¨šmpflen, V. (2006); MIPS: Analysis and Annotation of Proteins from Whole Genomes in 2005, Nucleic Acids Research, 34 (Database issue), 169-172, 2006.

Newman, M. E. J. (2005); A Measure of Betweenness Centrality Based on Random Walks, Social Networks, 27(1), 39-54, 2005.

Pan, W. T. (2012); A New Fruit Fly Optimization Algorithm: Taking the Financial Distress Model as an Example, Knowledge-Based Systems, 26(2), 69-74, 2012.

Pan, L., Paun, Gh. (2009); Spiking Neural P Systems with Anti-Spikes. International Journal of Computers Communications & Control, 4(3), 273-282, 2009.

Pál, C., Papp, B., Hurst, L. D. (2003); Genomic function: Rate of Evolution and Gene Dispensability, Nature, 421(6922), 496-497, 2003.

Paun, Gh. (2000); Computing with Membranes, Journal of Computer and System Sciences, 61(1), 108-143, 2000.

Paun, Gh. (2016); Membrane Computing and Economics: A General View, International Journal of Computers Communications & Control, 11(1), 105-112, 2016.

Peng, W., Wang, J., Cheng, Y., Lu, Y., Wu, F., Pan, Y. (2015); UDoNC: An Algorithm for Identifying Essential Proteins Based on Protein Domains and Protein-Protein Interaction Networks, Computational Biology Bioinformatics IEEE/ACM Transactions on, 12(2), 276- 288, 2015.

Przytycka, T. M., Singh, M., Slonim, D. K. (2010); Toward the Dynamic Interactome: It's about Time, Briefings in Bioinformatics, 11(1), 15-29, 2010.

Qin, C., Sun, Y., Dong, Y. (2017); A New Computational Strategy for Identifying Essential Proteins Based on Network Topological Properties and Biological Information, PLoS ONE, 12(7), e0182031, 2017.

Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D. (2004); Defining and Identifying Communities in Networks, Proceedings of the National Academy of Sciences of the United States of America, 101, 2658-2663, 2004.

Ren, J., Wang, J., Li, M., Wang, H., Liu, B. (2011); Prediction of Essential Proteins by Integration of PPI Network Topology and Protein Complexes. Information Bioinformatics Research and Applications - International Symposium, Isbra 2011, Changsha, China, May 27-29, 2011. Proceedings of, 12-24, 2011.

Roemer, T., Jiang, B., Davison, J., Ketela, T., Veillette, K., Breton, A., Marta, C. (2003); Large-Scale Essential Gene Identification in Candida Albicans and Applications to Antifungal Drug Discovery, Molecular Microbiology, 50(1), 167-181, 2003.

Schlicker, A., Lengauer, T., Albrecht, M. (2010); Improving Disease Gene Prioritization Using the Semantic Similarity of Gene Ontology Terms, Bioinformatics, 26(18), i561, 2010.

Song, B., Pan, L., Pérez-Jiménez, M. J. (2016); Cell-Like P Systems with Channel States and Symport/Antiport Rules, IEEE Transactions on NanoBioscience, 15(6), 555-566, 2016.

Song, B., Song, T., Pan, L. (2017); A Time-Free Uniform Solution to Subset Sum Problem by Tissue P Systems with Cell Division, Mathematical Structures in Computer Science, 27(1), 17-32, 2017.

Song, B., Zhang, C., Pan, L. (2017); Tissue-Like P Systems with Evolutional Symport/Antiport Rules, Information Sciences, 378, 177-193, 2017.

Stephenson, K., Zelen, M. (1989); Rethinking centrality: Methods and Examples, Social Networks, 11(1), 1-37, 1989.

Tang, X., Wang, J., Zhong, J., Pan, Y. (2014); Predicting Essential Proteins Based on Weighted Degree Centrality, IEEE/ACM Transactions on Computational Biology Bioinformatics, 11(2), 407-418, 2014.

Tang, X. W. (2017); Predicting Essential Proteins Using a New Method, Intelligent Computing Theories and Application: 13th International Conference, ICIC 2017, Liverpool, UK, August 7-10, Proceedings of, Part II, 301-308, 2017.

Tang, Y., Li, M., Wang, J., Pan, Y., Wu, F. X. (2015); CytoNCA: A Cytoscape Plugin for Centrality Analysis and Evaluation of Protein Interaction Networks, BioSystems, 127, 67-72, 2015.

Tu, B. P., Mcknight, S. L. (2005); Logic of the Yeast Metabolic Cycle: Temporal Compartmentalization of Cellular Processes, Science, 310(5751), 115, 2005.

Wang, J., Peng, X., Li, M., Luo, Y., Pan, Y. (2011); Active Protein Interaction Network and Its Application on Protein Complex Detection, IEEE International Conference on Bioinformatics and Biomedicine, 37-42, 2011.

Wang, J., Peng, X., Peng, W., Wu, F. X. (2014); Dynamic Protein Interaction Network Construction and Applications, Proteomics, 14(4-5), 338-352, 2014.

Wang, J. Z., Du, Z., Payattakool, R., Yu, P. S., Chen, C. F. (2007); A New Method to Measure the Semantic Similarity of GO Terms, Bioinformatics, 23(10), 1274, 2007.

Wang, L., Zheng, X. L., Wang, S. Y. (2013); A Novel Binary Fruit Fly Optimization Algorithm for Solving The Multidimensional Knapsack Problem, Knowledge-Based Systems, 48(2), 17-23, 2013.

Watts, D. J., Strogatz, S. H. (1998); Collective Dynamics of 'Small-World' Networks, Nature, 393(6684), 440, 1998.

Winzeler, E. A., Shoemaker, D. D., Astromoff, A., Liang, H., Anderson, K., Andre, B., Bussey, H. (1999); Functional Characterization of the S. cerevisiae Genome by Gene Deletion and Parallel Analysis, Science, 285(5429), 901-906, 1999.

Wuchty, S. (2001); Scale-Free Behavior in Protein Domain Networks, Molecular Biology Evolution, 18(9), 1694, 2001.

Wuchty, S., Stadler, P. F. (2003); Centers of Complex Networks, Journal of Theoretical Biology, 223(1), 45, 2003.

Yan, W., Sun, H., Wei, D., Enrico, B., Gabriella, V., Ying, X., Liang, Y. (2014); Identification of Essential Proteins Based on Ranking Edge-Weights in Protein-Protein Interaction Networks, PLoS ONE, 9(9), e108716, 2014.

Zeng, X., Lin, W., Guo, M., Zou, Q. (2017). A comprehensive overview and evaluation of circular RNA detection tools, PLoS Computational Biology, 13(6), e1005420, 2017.

Zhang, R., Lin, Y. (2009); DEG 5.0, A Database of Essential Genes in both Prokaryotes and Eukaryotes, Nucleic Acids Research, 37 (Database issue), D455, 2009.

Zhang, X. F., Dai, D. Q., Ouyang, L., Yan, H. (2014); Detecting Overlapping Protein Complexes Based on a Generative Model with Functional and Topological Properties, BMC Bioinformatics, 15(1), 186, 2014.

Zhang, Y., Lin, H., Yang, Z., Wang, J. (2013); Construction of Ontology Augmented Networks for Protein Complex Prediction, PLoS ONE, 8(5), : e62077, 2013.

Zhao, B., Wang, J., Li, M., Wu, F. X., Pan, Y. (2014); Detecting Protein Complexes Based on Uncertain Graph Model, IEEE/ACM Transactions on Computational Biology Bioinformatics, 11(3), 486-497, 2014.

Zhu, C., Wu, C., Aronow, B. J., Jegga, A. G. (2014); Computational Approaches for Human Disease Gene Prediction and Ranking, Advances in Experimental Medicine Biology, 799, 69, 2014.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.