Pattern Discovery in Protein Networks Reveals High-Confidence Predictions of Novel Interactions

Hazem Radwan Ahmed, Janice I. GlasgowAAAI 2014 · DOI

TL;DR

This paper introduces a novel computational framework, 3PI, that leverages Particle Swarm Optimization (PSO) to discover patterns in protein interaction networks. By combining network topology and protein domain information, 3PI effectively predicts new, high-confidence protein-protein interactions (PPIs), complementing existing prediction methods and uncovering previously unknown biological connections.

What Problem Does This Paper Address?

Understanding how proteins interact within a cell is fundamental to deciphering biological processes. Protein-Protein Interactions (PPIs) are crucial for virtually all cellular functions. However, our current knowledge of PPIs is far from complete, estimated to contain a significant number of false positives and false negatives. Experimental methods for identifying PPIs are costly and labor-intensive, while computational methods, though more efficient, often struggle with the sheer scale and complexity of proteomic networks. Existing computational approaches often rely on extensive training data or complex feature engineering. This paper aims to address the challenge of efficiently and accurately predicting novel, high-confidence PPIs by discovering meaningful patterns within existing, albeit incomplete, PPI networks.

Methods

The core of the proposed method, 3PI, lies in its novel application of Particle Swarm Optimization (PSO) for pattern discovery in protein interaction networks.

  • PSO-based Pattern Discovery: Instead of traditional exhaustive searches, 3PI uses a PSO algorithm to efficiently explore vast search spaces of potential interaction patterns. The algorithm searches for "topologically-similar patterns" by comparing windows within adjacency matrices representing protein interactions. A key innovation is the use of a multi-start variant of PSO with a restart mechanism (based on a "swarm-wide performance" condition) to overcome the common issue of premature convergence and getting trapped in local optima.
  • Integration of Network Topology and Protein Domains: The PSO algorithm identifies patterns based on the proximity and connectivity of proteins within the network. This is further enhanced by incorporating protein domain information. The method focuses on patterns where proteins are "close" in the network (at most 3 edges apart), hypothesizing that such proximity suggests functional relatedness.
  • Knowledge Transfer: Once topologically similar patterns are discovered and enriched for common protein domains (using DAVID and InterPro), a "knowledge transfer" process is employed. This process predicts that if two sets of proteins (A and B) are enriched in similar domains and are neighbors of an interacting protein pair (P1, P2), then members of A are likely to interact with members of B, and vice versa.

Datasets

The paper utilizes existing biological databases for its analysis and validation:

  • Interologous Interaction Database (I2D): Specifically, the latest version of Human I2D 2.0 (released in 2012) was used to identify "hub" and "bottleneck" proteins for case studies.
  • Publically Available Interaction Databases: These include BioGrid, BIND, IntAct, HPRD, and MINT, used for validating predicted PPIs.
  • Gene Expression Datasets: Used to assess the co-expression of genes corresponding to predicted interacting protein pairs.

The paper does not introduce a new benchmark dataset but rather leverages existing resources to validate its predictions.

Key Insights and Ideas

  • PSO as an efficient pattern discovery tool: The paper demonstrates that PSO, a bio-inspired optimization technique, can be effectively applied to the computationally challenging task of finding patterns in large, sparse protein interaction networks, outperforming brute-force methods.
  • The power of "close proximity" patterns: The insight that proteins within a short network distance (<= 3 edges) are more likely to be functionally related and interact is a crucial driver for the method's success. This "local" pattern discovery is more tractable and biologically relevant than global network analysis.
  • Knowledge transfer from patterns to predictions: The core idea of transferring predicted interactions based on shared domain enrichment within these discovered patterns is a novel approach to generating high-confidence PPI predictions.
  • Complementarity of methods: The results suggest that pattern discovery-based methods, like 3PI, can complement existing, feature-rich prediction methods (like FpClass) by identifying interactions that might be missed by other approaches.

Key Results

  • High-confidence predictions: Over 50% of the predicted PPIs overlapped with publically available interaction databases.
  • Strong agreement with existing methods: Approximately 80% of the predictions were found among the Top 1% of predictions from the FpClass method, indicating high confidence.
  • Biological relevance: Predicted interacting genes were significantly co-expressed across different tissues.
  • Novel discoveries: The method successfully predicted interactions that were not identified by FpClass or readily available in curated databases, some of which were later experimentally supported by literature.
  • Efficiency: The PSO-based pattern discovery was shown to be efficient, discovering patterns with over 100 common contacts in less than 1000 iterations, a feat that random search failed to achieve.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the human interactome is still far from complete, meaning the current PPI networks used for pattern discovery are inherently noisy and incomplete.
  • While the method aims to reduce false positives, some predictions may still receive lower confidence scores from other methods.
  • Future Work:
    • Conducting more in-depth analysis and fine-tuning of each step in the methodology.
  • Developing an online tool to suggest novel potential interaction partners for interfacing protein pairs.
  • Applying the method on a large proteome scale to build a more complete and accurate interactome.

Summary updated

BibTeX
@inproceedings{ahmed2014pattern,
  author = {Hazem Radwan Ahmed and Janice I. Glasgow},
  title = {{Pattern Discovery in Protein Networks Reveals High-Confidence Predictions of Novel Interactions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i2.19035},
}
Figure