Identification of Essential Proteins Using Induced Stars in Protein–Protein Interaction Networks

Chrysafis Vogiatzis () and Mustafa Can Camur ()
Additional contact information
Chrysafis Vogiatzis: Department of Industrial and Systems Engineering, North Carolina A&T State University, Greensboro, North Carolina 27411;
Mustafa Can Camur: Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, Troy, New York 12180

INFORMS Journal on Computing, 2019, vol. 31, issue 4, 703-718

Abstract: In this work, we propose a novel centrality metric, referred to as star centrality , which incorporates information from the closed neighborhood of a node, rather than solely from the node itself, when calculating its topological importance. More specifically, we focus on degree centrality and show that in the complex protein–protein interaction networks, it is a naive metric that can lead to misclassifying protein importance. For our extension of degree centrality when considering stars, we derive its computational complexity, provide a mathematical formulation, and propose two approximation algorithms that are shown to be efficient in practice. We portray the success of this new metric in protein–protein interaction networks when predicting protein essentiality in several organisms, including the well-studied Saccharomyces cerevisiae , Helicobacter pylori , and Caenorhabditis elegans , where star centrality is shown to significantly outperform other nodal centrality metrics at detecting essential proteins. We also analyze the average and worst-case performance of the two approximation algorithms in practice and show that they are viable options for computing star centrality in very large-scale protein–protein interaction networks, such as the human proteome, where exact methodologies are bound to be time and memory intensive.

Keywords: centrality; protein-protein interaction networks; complex network analysis (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0872 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:4:p:703-718

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().