%0 Journal Article %T The assessment of essential genes in the stability of PPI networks using critical node detection problem %J AUT Journal of Mathematics and Computing %I Amirkabir University of Technology %Z 2783-2449 %A Rezaei, Javad %A Zare Mirakabad, Fatemeh %A Marashi, Sayed-Amir %A MirHassani, Seyed Ali %D 2022 %\ 02/01/2022 %V 3 %N 1 %P 59-76 %! The assessment of essential genes in the stability of PPI networks using critical node detection problem %K Essential genes %K Protein-protein interaction network %K Centrality %K Critical node %K Network stability %R 10.22060/ajmc.2021.20101.1053 %X 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/”. %U https://ajmc.aut.ac.ir/article_4505_6aa5ff14e54e7a2c643d3d53dab1369d.pdf