A graph modification approach for finding core-periphery structures in protein interaction networks

Sharon Bruckner, Falk Hüffner, Christian Komusiewicz

Abstract

The core-periphery model for protein interaction (PPI) networks assumes that protein complexes consist of a dense core and a possibly sparse periphery adjacent to core vertices. This work aims to uncover global core-periphery structures by fitting input networks to hypothetical ground truth models through a minimum number of edge modifications. We propose two exact graph-theoretic formulations—Split Cluster Editing and Monopolar Editing—and analyze their theoretical properties, showing both to be NP-hard. We then develop efficient exact and heuristic algorithms, evaluating them on subnetworks of the S. cerevisiae PPI network to demonstrate their biological relevance and accuracy.

Introduction: Beyond Simple Clustering

In Protein-Protein Interaction (PPI) networks, identifying functional complexes is a fundamental task. Traditional approaches often rely on the assumption that these complexes are cliques—subgraphs where every protein interacts with every other. However, biological reality is more nuanced: many complexes are composed of a stable, highly connected "core" surrounded by "attachment" proteins that interact with the core transiently or sparsely.

Existing methods for finding these structures typically use "seed growing" heuristics, which expand a small core greedily. While useful, these local approaches often fail to capture the global structure of the network. This paper proposes a global optimization framework that treats the entire network as a collection of core–periphery structures, seeking the minimum number of edge additions or deletions required to transform the observed data into a theoretically sound model.

Methods: Graph Editing Models

The authors introduce two primary mathematical models to represent core-periphery structures:

  1. Split Cluster Editing (SCE): This model partitions the network into disjoint "split graphs." Each component contains exactly one core (a clique) and one dedicated periphery (an independent set where proteins interact only with the core, not each other).
  2. Monopolar Editing (ME): A more flexible approach where cores remain disjoint cliques, but the periphery is shared. In this model, a single periphery protein can be associated with multiple different cores, reflecting the multi-functional nature of many "linker" proteins in biological systems.
Comparison of graph editing models: Input graph G, Cluster Editing, Split Cluster Editing, and Monopolar Editing.

Both problems are computationally challenging (NP-hard). To address this, the researchers developed two types of algorithmic solutions:

  • Exact Algorithms: Utilizing Integer Linear Programming (ILP) with "forbidden subgraph" constraints to find the mathematically optimal set of edits.
  • Heuristic Algorithms: Implementing Simulated Annealing to provide high-quality solutions for larger networks where exact solvers become prohibitively slow.

Biological Evaluation and Insights

The models were tested on functional subnetworks (Cell Cycle, Transcription, and Translation) of the S. cerevisiae (yeast) PPI network from the BioGRID database. Using the hand-curated CYC2008 database as a ground truth, the researchers found that the Monopolar Editing (ME) model consistently outperformed the more rigid Split Cluster model.

Key findings include:

  • The Shared Periphery Advantage: The success of the ME model suggests that real biological systems rely on transient attachments that serve multiple functional modules simultaneously.
  • Functional Coherence: Analysis of Gene Ontology (GO) terms confirmed that proteins within the identified "cores" were significantly more likely to share biological functions than those in the periphery, validating the core–attachment hypothesis.
  • Global Optimization Efficacy: By optimizing the entire graph at once, the algorithms avoided the local optima traps common in greedy search methods. In the Cell Cycle network, the ME model identified 20 complexes, surpassing traditional clustering algorithms like SCAN (12) and local-search methods like LUO (15).

Conclusion and Future Directions

This research demonstrates that modeling PPI networks as global core–periphery structures provides a more accurate reflection of biological complexes than simple clique-based clustering. While the Monopolar model is theoretically complex, it proved highly effective in practice, often requiring fewer edits to fit real-world data than simpler models.

Future work may involve relaxing the "clique" requirement for cores to accommodate dense but imperfectly connected subgraphs (k-plexes) and incorporating edge weights to account for varying levels of confidence in protein interaction data. As PPI datasets continue to grow, these global modification approaches will be essential for mapping the functional landscape of the cell.

Summary updated

BibTeX
@inproceedings{bruckner2014graph,
  author = {Sharon Bruckner and Falk Hüffner and Christian Komusiewicz},
  title = {{A graph modification approach for finding core-periphery structures in protein interaction networks}},
  booktitle = {WABI},
  year = {2014},
  doi = {10.1007/978-3-662-44753-6\_25},
}
Figure