Novel centrality metrics for studying essentiality in protein‐protein interaction networks based on group structures

• Published in: Networks 2022-07, Vol.80 (1), p.3-50
• Main Authors: Rasti, Saeid, Vogiatzis, Chrysafis
• Format: Article
• Language: English
• Subjects: biological networks; centrality; Combinatorial analysis; combinatorial branch‐and‐bound; Complexity; group centrality; Integer programming; Mixed integer; network structures; Nodes; Proteins; protein‐protein interaction networks
• ISSN: 0028-3045; 1097-0037
• DOI: 10.1002/net.22071

In this work, we introduce centrality metrics based on group structures, and we show their performance in estimating importance in protein‐protein interaction networks (PPINs). The centrality metrics introduced are extensions of well‐known nodal metrics. However, instead of focusing on a single node, we focus on that node and the set of nodes around it. Furthermore, we require the set of nodes to induce a specific pattern or structure. The structures investigated range from the “stricter“ induced stars and cliques, to a “looser” definition of a representative structure. We derive the computational complexity of all metrics and provide mixed integer programming formulations; due to the problem complexity and the size of PPINs, using commercial solvers is not always viable. Hence, we propose a combinatorial branch‐and‐bound solution approach. We conclude by showing the effectiveness of the proposed metrics in identifying essential proteins in Helicobacter pylori and comparing them to nodal metrics.