Studying Connectivity Properties in Human Protein–Protein Interaction Network in Cancer Pathway

The critical node detection problem seeks a set of nodes with at most a given cardinality, whose deletion results in maximum pairwise disconnectivity. The critical nodes are responsible for the overall connectivity of the graph. In a prior work by the authors, a novel combinatorial algorithm is proposed to identify critical nodes in sparse graphs. The robustness of the algorithm is demonstrated on several test instances. In this work, we apply this algorithm on the human PPI network. In this article, the human protein–protein interaction (PPI) network is considered, where the nodes correspond to proteins and the edges correspond to the interaction between the proteins. The heuristic technique is applied to identify the critical nodes on a subgraph of the PPI network induced by a node set corresponding to the proteins that are present in the cancer pathway in the human PPI network. These set of proteins are obtained from the Human Cancer Protein Interaction Network (HCPIN) database. The information about the interactions between these proteins are obtained from the Human Protein Resource Database (HPRD), in order to construct the graph. The critical nodes in the human cancer protein network correspond to the hub proteins that are responsible for the overall connectivity of the graph and play a role in multiple biological processes. The dysfunction of the interactions with some of the hub proteins or mutation in these proteins have been directly linked to cancer and other diseases. In this research, such hub proteins were identified from a purely graph theoretic perspective in terms of their role in determining the overall connectivity of the PPI network. This new technique will shed light on new hub proteins that are yet to be discovered and the proteins responsible for other genetic disorders.