The Assessment of Essential Genes in the Stability of Ppi Networks Using Critical Node Detection Problem

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 scalefree 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 wellknown 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/”.