Document Type : Original Article
Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic)
Department of Biotechnology, College of Science, University of Tehran, Tehran, Iran
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 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/”.