Amirkabir University of Technology AUT Journal of Mathematics and Computing 2783-2449 3 1 2022 02 01 The assessment of essential genes in the stability of PPI networks using critical node detection problem 59 76 4505 10.22060/ajmc.2021.20101.1053 EN Javad Rezaei Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Fatemeh Zare Mirakabad Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran 0000-0003-2849-3778 Sayed-Amir Marashi Department of Biotechnology, College of Science, University of Tehran, Tehran, Iran Seyed Ali MirHassani Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran 0000-0002-9894-7053 Journal Article 2021 05 31 Essential 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 the topological importance of a protein in protein-protein interaction networks and its essentiality. Different centrality criteria such as degree, between ness, 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 topo[1]logical 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 is 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_149ef6419512be56a93169cd5e6fa8fd.pdf