k-Partite cliques of protein interactions: A novel subgraph topology for functional coherence analysis on PPI networks

Qian Liu, Yi‐Ping Phoebe Chen, Jinyan LiJournal of Theoretical Biology 2013 · DOI

TL;DR

This paper introduces "k-partite protein cliques" as a novel subgraph topology to better understand protein-protein interaction (PPI) networks and predict protein functions. By transforming PPI networks into k-partite graphs and developing a mining algorithm (MaCMik), they identify these cliques, which reveal functionally coherent groups of proteins, even when these groups aren't densely connected.

What Problem Does This Paper Address?

Predicting protein function is a crucial task in post-genomic biology. While many approaches exist, including analyzing protein interaction networks (PPIs), existing methods often struggle. Dense subgraphs, a common focus, sometimes yield worse prediction performance than simpler neighbor-counting methods. This suggests that PPI networks possess complex local topological structures that are not fully captured by current approaches. The authors aim to uncover a more nuanced topological feature that reflects functional coherence within PPI networks, going beyond simple density.

Methods

The core of this work is the introduction of k-partite protein cliques as a new subgraph topology. To find these, the authors propose a two-step process:

  1. Constructing K-partite Graphs: A given PPI network is transformed into a K-partite graph. This involves partitioning proteins into K sets (partites) such that edges (interactions) primarily exist between these sets, not within them. The construction heuristic prioritizes proteins with more partners and partites with more proteins.
  2. Mining Maximal k-partite Cliques (MaCMik Algorithm): A novel algorithm, MaCMik, is developed to mine these k-partite cliques from the constructed K-partite graphs. MaCMik employs a divide-and-conquer strategy, recursively building higher-order cliques from lower-order ones. A key component is a "consensus technique" used to merge results and handle potential conflicts when combining partite information. The algorithm specifically focuses on detecting maximal bicliques, tricliques, and quadricliques.

Datasets

The primary dataset used for evaluation is the DIP (Database of Interacting Proteins) yeast PPI network (January 31, 2013 release). This network contains 4,892 proteins and 21,851 non-self-interactions. This network was transformed into a 12-partite graph for analysis.

Key Insights and Ideas

  • Beyond Density: The paper highlights that functional coherence in PPI networks isn't solely tied to dense subgraphs. K-partite cliques can capture functionally related proteins even if their direct interactions aren't exhaustive.
  • Partite Coherence: The individual "partites" within a k-partite protein clique often exhibit high functional coherence themselves, suggesting they represent biologically relevant functional groups.
  • Size Matters (for Coherence): Smaller k-partite cliques (3-6 proteins) show a strong tendency to share functions, aligning with findings that these might represent quasi-cliques in general graphs.
  • Rank-Higher is Better (for Coherence): Higher-order k-partite cliques (e.g., quadricliques vs. tricliques) tend to exhibit greater functional coherence.
  • Indirect Neighbors are Key: The findings support the idea that indirect protein interactions (captured by k-partite structures) are crucial for understanding functional relationships, often more so than direct interactions alone.

Key Results

The MaCMik algorithm was applied to the yeast PPI network, resulting in the detection of:

  • 15,740 maximal bicliques
  • 76,409 maximal tricliques
  • 53,462 maximal quadricliques

Analysis of these cliques revealed:

  • Most proteins within the same maximal k-partite cliques share common functions.
  • Functional coherence generally increases with the "rank" of the clique (biclique < triclique < quadriclique).
  • Smaller cliques (3-6 proteins) show higher functional coherence and may correspond to biologically relevant functional groups.
  • Partites within k-partite cliques often show higher functional coherence than the entire clique, and these partites themselves can be biologically relevant.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • False Positives/Negatives: PPI networks inherently contain noise (false positives and negatives). While k-partite cliques are less susceptible to false positives than dense subgraphs, false negatives can still lead to missing cliques.
  • Computational Complexity: Detecting higher-order k-partite cliques (beyond bicliques, tricliques, and quadricliques) becomes computationally expensive.
  • Future Work:
    • Statistical Evaluation: Pinpointing the most biologically relevant functional groups from k-partite clique subgraphs.
  • K-partite Quasi-Cliques: Relaxing the strict all-versus-all interaction constraint to better handle false negative interactions.
  • Scoring Method: Incorporating interaction reliability (based on experimental evidence and detection times) to mitigate false positive effects.
  • Function Prediction Framework: Developing a framework to predict protein functions using k-partite cliques.
  • Web Server: Creating a user-friendly web server for the proposed method.

Summary updated

BibTeX
@article{liu2013k,
  author = {Qian Liu and Yi‐Ping Phoebe Chen and Jinyan Li},
  title = {{k-Partite cliques of protein interactions: A novel subgraph topology for functional coherence analysis on PPI networks}},
  journal = {Journal of Theoretical Biology},
  year = {2013},
  doi = {10.1016/j.jtbi.2013.09.013},
}
Figure