A Graph Modification Approach for Finding Core-Periphery Structures in Protein Interaction Networks

Sharon Bruckner, Falk Hüffner, Christian Komusiewicz

TL;DR

This paper moves beyond simple "clique-based" clustering to identify protein complexes by modeling them as dense cores surrounded by sparse peripheries. The authors introduce two graph-theoretic models—Split Cluster Editing and Monopolar Editing—and demonstrate that treating protein interaction networks as global core–periphery structures identifies biological complexes more accurately than traditional clustering methods.

What Problem Does This Paper Address?

In Protein-Protein Interaction (PPI) networks, researchers often look for "complexes"—groups of proteins that work together. The standard assumption is that these complexes are cliques (where every protein interacts with every other). However, biology is messier: many complexes consist of a stable, dense core and "attachment" proteins that interact with the core only transiently.

Existing methods for finding these structures usually rely on "seed growing," where a small core is greedily expanded. These are local approaches that can miss the "big picture." The authors of this paper propose a global optimization approach: they want to find the minimum number of edge additions or deletions needed to transform an entire observed network into a "ground truth" model that follows core–periphery rules.

Methods

The authors propose two mathematical models based on graph theory:

  1. Split Cluster Editing (SCE): This model assumes the network is a collection of disjoint "split graphs." In each component, there is one core (a clique) and one periphery (an independent set where proteins don't talk to each other, only to the core).
  2. Monopolar Editing (ME): This is a more flexible model. It assumes cores are disjoint cliques, but the periphery is shared. A single periphery protein can be "attached" to multiple different cores.

Because both problems are NP-hard (meaning they are computationally "expensive" to solve perfectly as the network grows), the authors developed two types of solutions:

  • Exact Algorithms: Using Integer Linear Programming (ILP) to find the mathematically perfect minimum number of edits. They used "forbidden subgraph" constraints (identifying small patterns that shouldn't exist in their models and forcing the solver to "edit" them away).
  • Heuristic Algorithms: Using Simulated Annealing to find high-quality solutions quickly for networks too large for the exact solver.

Datasets

The researchers evaluated their models on the S. cerevisiae (yeast) PPI network from the BioGRID database. To make the evaluation biologically meaningful, they focused on three specific functional subnetworks:

  • Cell Cycle
  • Transcription
  • Translation

They used the CYC2008 database (a hand-curated set of known yeast complexes) as the "ground truth" to see how well their algorithms performed. They also used Gene Ontology (GO) terms to measure the functional coherence of the cores they discovered.

Key Insights and Ideas

  • The "Shared Periphery" Advantage: The Monopolar model (ME) outperformed the Split Cluster model (SCE). This suggests that in real biological systems, many proteins act as "linkers" or transient attachments that serve multiple functional modules.
  • Cores are the Functional Heart: By analyzing GO terms, the authors found that proteins within the "cores" were significantly more likely to share the same biological function than proteins in the "periphery." This validates the core–attachment hypothesis.
  • Theory vs. Practice: Interestingly, while Monopolar Editing is theoretically "harder" to solve (it's NP-hard even to recognize if a graph fits the model), it was often faster to solve in practice than Split Cluster Editing because it required fewer edge modifications to fit the real-world data.
  • Global > Local: By optimizing the whole graph at once, the authors avoided the "local optima" traps that greedy seed-growing algorithms often fall into.

Key Results

  • Complex Detection: In the Cell Cycle network, the Monopolar (ME) model detected 20 complexes, outperforming SCE (15), the clustering algorithm SCAN (12), and the local-search algorithm LUO (15).
  • Accuracy: The ME model achieved high "coreness" percentages (often 89-93%), meaning the discovered cores mapped very closely to known biological complexes.
  • Efficiency: The Simulated Annealing heuristic was highly effective, often finding the optimal solution or coming within one edit of it, making the approach viable for larger networks.

Limitations and Future Work

  • The Clique Assumption: Both models assume cores are perfect cliques. In reality, some biological cores might be very dense but not perfectly connected. Relaxing this to "k-plexes" (nearly-complete graphs) could be more realistic but would significantly increase computational complexity.
  • Scalability: While the heuristics help, the underlying problems remain NP-hard. Applying this to the entire human interactome (tens of thousands of proteins) would require even more aggressive data reduction or faster approximation algorithms.
  • Edge Weights: The current model treats all interactions as equal (0 or 1). Future versions could incorporate edge weights to represent the "confidence" or "strength" of a protein interaction.

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},
}

Loading related content...

Figure