Amirkabir University of TechnologyAUT Journal of Mathematics and Computing2783-24493120220201The assessment of essential genes in the stability of PPI networks using critical node detection problem5976450510.22060/ajmc.2021.20101.1053ENJavadRezaeiDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, IranFatemehZare MirakabadDepartment of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic)Sayed-AmirMarashiDepartment of Biotechnology, College of Science, University of Tehran, Tehran, IranSeyed AliMirHassaniDepartment of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic)Journal Article20210531Essential genes and proteins as their products encode the basic functions of a cell in a variety of conditions and are vital for the survival of a cell. Analyzing the characteristics of these proteins provides important biological information. An interesting analysis is to demonstrate the correlation between topological importance of a protein in protein-protein interaction networks and its essentiality. Different centrality criteria such as degree, betweenness, closeness, and eigenvector centralities are used to investigate such a correlation. Despite the remarkable results obtained by these methods, it is shown that the centrality criteria in scale-free networks show a high level of correlations which indicate that they share similar topological information of the networks. In this paper, we use a different approach for analyzing this correlation and use a well-known problem in the field of graph theory, Critical Node Detection Problem and solve it on the protein-protein interaction networks to obtain a subset of proteins called critical nodes which have the most effect on the network stability. Our results show that essential proteins have a more prominent presence in the set of critical nodes than what expected at random samples. Furthermore, the essential proteins represented in the set of critical nodes have a different distribution of topological properties compared to the essential proteins recovered by the centrality-based methods. All the source codes and data are available at “http://bioinformatics.aut.ac.ir/CNDP_PPI_networks/”https://ajmc.aut.ac.ir/article_4505_91e2a84e3ead5466af5dd0b6aaa745ee.pdf