Providing SSPCO Algorithm to Construct Static Protein-Protein Interaction (PPI) Networks

Document Type : Regular Article


1 M.Sc., Department of Computer Engineering, Shiraz Branch, Islamic Azad University, Shiraz Branch, Iran

2 M.Sc., Institute for Management and Planning Studies of Tehran, Iran

3 Ph.D., Department of Computer Engineering, Shiraz Branch, Islamic Azad University, Shiraz Branch, Iran


Protein-Protein Inter-action Networks are dynamic in reality; i.e. Inter-actions among different proteins may be ineffective in different circumstances and times. One of the most crucial parameters in the conversion of a static network into a temporal graph is the well-tuning of transformation threshold. In this part of the article, using additional data, like gene expression data in different times and circumstances and well-known protein complexes, it is tried to determine an appropriate threshold. To accomplish this task, we transform the problem into an optimization one and then we solve it using a meta-heuristic algorithm, named Particle Swarm Optimization (SSPCO). One of the most important parts in our work is the determination of interestingness function in the SSPCO. It is defined as a function of standard complexes and gene co-expression data. After producing a threshold per each gene, in the following section we will discuss how using these thresholds, active proteins are determined and then temporal graph is created. For final assessment of the produced graph quality, we use graph clustering algorithms and protein complexes determination algorithms. For accomplishing this task, we use MCL, Cluster One, MCODE algorithms. Due to high number of the obtained clusters, the obtained results, if they have some special conditions, will filter out or be merged with each other. Standard performance criteria like Recal, Precision, and F-measure are employed. There is a new proposed criterion named Smoothness. Our experimental results show that the graphs produced by the proposed method outperform the previous methods.


Main Subjects

[1]     Trewavas A. A Brief History of Systems Biology. Plant Cell 2006;18:2420–30.
[2]     Chen B, Fan W, Liu J, Wu F-X. Identifying protein complexes and functional modules--from static PPI networks to dynamic PPI networks. Brief Bioinform 2014;15:177–94.
[3]     Holme P, Saramäki J. Temporal Networks as a Modeling Framework, 2013, p. 1–14.
[4]     Wang J, Peng X, Li M, Luo Y, Pan Y. Active Protein Interaction Network and Its Application on Protein Complex Detection. 2011 IEEE Int. Conf. Bioinforma. Biomed., IEEE; 2011, p. 37–42.
[5]     Zhang Y, Du N, Li K, Feng J, Jia K, Zhang A. Critical protein detection in dynamic PPI networks with multi-source integrated deep belief nets. 2013 IEEE Int. Conf. Bioinforma. Biomed., IEEE; 2013, p. 29–36.
[6]     Ahmed H, Glasgow J. 3PI: A Novel Method for Predicting High-Confidence Protein-Protein Interactions using Particle Swarm-based Network Alignment, 2013.
[7]     Iqbal M, Freitas AA, Johnson CG. Protein Interaction Inference Using Particle Swarm Optimization Algorithm. Evol. Comput. Mach. Learn. Data Min. Bioinforma., Berlin, Heidelberg: Springer Berlin Heidelberg; n.d., p. 61–70.
[8]     Hashim FA, Houssein EH, Hussain K, Mabrouk MS, Al-Atabany W. Honey Badger Algorithm: New metaheuristic algorithm for solving optimization problems. Math Comput Simul 2022;192:84–110.
[9]     Peraza-Vázquez H, Peña-Delgado AF, Echavarría-Castillo G, Morales-Cepeda AB, Velasco-Álvarez J, Ruiz-Perez F. A Bio-Inspired Method for Engineering Design Optimization Inspired by Dingoes Hunting Strategies. Math Probl Eng 2021;2021:1–19.
[10]   Jana G, Mitra A, Pan S, Sural S, Chattaraj PK. Modified Particle Swarm Optimization Algorithms for the Generation of Stable Structures of Carbon Clusters, Cn (n = 3–6, 10). Front Chem 2019;7.
[11]   Shabani A, Asgarian B, Gharebaghi SA, Salido MA, Giret A. A New Optimization Algorithm Based on Search and Rescue Operations. Math Probl Eng 2019;2019:1–23.
[12]   Ou-Yang L, Dai D-Q, Li X-L, Wu M, Zhang X-F, Yang P. Detecting temporal protein complexes from dynamic protein-protein interaction networks. BMC Bioinformatics 2014;15:335.
[13]   Byrum S, Smart SK, Larson S, Tackett AJ. Analysis of Stable and Transient Protein–Protein Interactions, 2012, p. 143–52.
[14]   Jianyong Sun, Garibaldi JM, Hodgman C. Parameter Estimation Using Metaheuristics in Systems Biology: A Comprehensive Review. IEEE/ACM Trans Comput Biol Bioinforma 2012;9:185–202.
[15]   X. G. Systems biology approaches to the computational modelling of trypanothione metabolism in Trypanosoma brucei. thesis, University of Glasgow. 2010.
[16]   Fonseca R, Paluszewski M, Winter P. Protein Structure Prediction Using Bee Colony Optimization Metaheuristic. J Math Model Algorithms 2010;9:181–94.
[17]   Rodriguez-Fernandez M, Egea JA, Banga JR. Novel metaheuristic for parameter estimation in nonlinear dynamic biological systems. BMC Bioinformatics 2006;7:483.
[18]   Abdullah A, Deris S, Anwar S, Arjunan SN V. An Evolutionary Firefly Algorithm for the Estimation of Nonlinear Biological Model Parameters. PLoS One 2013;8:e56310.
[19]   Maher B, Albrecht A, Loomes M, Yang X-S, Steinhöfel K. A Firefly-Inspired Method for Protein Structure Prediction in Lattice Models. Biomolecules 2014;4:56–75.
[20]   Omidvar R, Parvin H, Rad F. SSPCO Optimization Algorithm (See-See Partridge Chicks Optimization). 2015 Fourteenth Mex. Int. Conf. Artif. Intell., IEEE; 2015, p. 101–6.
[21]   Dehmer M, Emmert-Streib F, Graber A, Salvador A, editors. Applied Statistics for Network Biology. Weinheim, Germany: Wiley-VCH Verlag GmbH & Co. KGaA; 2011.
[22]   Song L, Langfelder P, Horvath S. Comparison of co-expression measures: mutual information, correlation, and model based indices. BMC Bioinformatics 2012;13:328.
[23]   Tang X, Wang J, Liu B, Li M, Chen G, Pan Y. A comparison of the functional modules identified from time course and static PPI network data. BMC Bioinformatics 2011;12:339.
[24]   V D, S. M. Graph Clustering by Flow Simulation. PhD thesis, Center for Math. and Computer Science (CWI). 2000.
[25]   Bader GD, Hogue CW V. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 2003;4:1–27.
[26]   Nepusz T, Yu H, Paccanaro A. Detecting overlapping protein complexes in protein-protein interaction networks. Nat Methods 2012;9:471–2.
[27]   Wang J, Peng X, Li M, Pan Y. Construction and application of dynamic protein interaction network based on time course gene expression data. Proteomics 2013;13:301–12.
[28], last accessed: 10/29/2014 n.d.
[29]   García S, Molina D, Lozano M, Herrera F. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization. J Heuristics 2009;15:617–44.
[30]   Villegas JG. Using nonparametric test to compare the performance of metaheuristics. EU/ME-The Metaheuristics Community, Internet 2011.