A Network Synthesis Model for Generating Protein Interaction Network Families

Sayed Mohammad Ebrahim Sahraeian, Byung-Jun YoonPLoS 2012 · DOI

TL;DR

This paper introduces a novel computational model to generate families of synthetic protein-protein interaction (PPI) networks that mimic the evolutionary relationships and properties of real biological networks. This model is crucial for creating robust benchmark datasets to rigorously evaluate and improve network alignment algorithms, a key tool for comparative biological network analysis.

What Problem Does This Paper Address?

Understanding biological systems increasingly relies on analyzing protein-protein interaction (PPI) networks. Comparing these networks across different species can reveal conserved functions and evolutionary insights. However, a major bottleneck in developing and evaluating comparative network analysis algorithms, particularly network alignment algorithms, is the lack of comprehensive and reliable benchmark datasets. Existing PPI data is often incomplete and noisy, making it difficult to establish a "gold standard" for testing these algorithms. Current evaluation methods often rely on indirect measures like functional annotations, which can be biased by sequence similarity, or anecdotal evidence. This paper aims to solve this by creating a model that generates realistic, evolutionarily related synthetic PPI network families, thereby providing a much-needed framework for rigorous algorithm assessment.

Methods

The core of this work is a Network Synthesis Model designed to generate families of evolutionarily related synthetic PPI networks. The process starts with a hypothetical phylogenetic tree that defines the evolutionary relationships between the desired networks.

  1. Ancestral Network Generation: A seed network is grown into a biologically realistic ancestral PPI network using established network growth models like DMC (Duplication-Mutation-Complementation), DMR (Duplication with Random Mutation), or CG (Crystal Growth). These models simulate how networks evolve through processes like gene duplication and divergence.
  2. Phylogenetic Tree Traversal: The model traverses the phylogenetic tree. At each internal node, the parent network is duplicated to create two child networks.
  3. Network Extension and Divergence: Each child network is then extended using one of the chosen network growth models (DMC, DMR, or CG). This step simulates the evolutionary divergence of descendant species.
  4. Functional and Sequence Similarity Inheritance: Crucially, the model incorporates mechanisms to model functional inheritance and sequence similarity divergence. When a new node is created (e.g., through duplication), its functional annotation is inherited with a certain probability, or it can acquire a new, unannotated function. Similarly, sequence similarity scores between proteins in different networks are generated based on a Gamma distribution, controlled by parameters that mimic evolutionary divergence. This ensures that the generated networks maintain realistic cross-network properties.

Datasets

The authors utilized PPI data from IsoBase for five organisms: C. elegans, D. melanogaster, H. sapiens, M. musculus, and S. cerevisiae. This data was integrated from BioGRID, DIP, and HPRD.

The primary contribution in terms of datasets is the creation of the NAPAbench (Network Alignment Performance Assessment benchmark). This benchmark consists of three suites of synthetic datasets:

  • Pairwise alignment datasets: Three pairs of networks generated using DMC, DMR, and CG, respectively.
  • 5-way alignment datasets: Three families of five networks each, generated using DMC, DMR, and CG.
  • 8-way alignment datasets: Three families of eight networks each, generated using DMC, DMR, and CG.

These datasets are designed to simulate varying degrees of evolutionary relatedness and network complexity, providing a diverse testing ground for network alignment algorithms.

Key Insights and Ideas

  • The critical need for realistic synthetic data: The paper strongly argues that the lack of good benchmarks is a major impediment to progress in comparative network analysis. Their model directly addresses this by generating networks that mimic real biological properties.
  • Evolutionary processes as a generative mechanism: By explicitly modeling phylogenetic relationships and using duplication-divergence models, the synthesis method captures the evolutionary history that shapes real PPI networks.
  • Bridging intra- and inter-network properties: The model doesn't just create networks that look like real ones internally; it also ensures that the relationships between networks (like sequence similarity and potential ortholog distribution) are biologically plausible. This is vital for testing alignment algorithms.
  • Sequence similarity alone is insufficient: The analysis of real PPI data and the model's parameters highlight that sequence similarity is a noisy indicator of functional orthology. This reinforces the need for network alignment algorithms that integrate topological information.
  • NAPAbench as a standardized evaluation tool: The creation of NAPAbench provides a concrete resource for the community to compare algorithms fairly and identify their strengths and weaknesses under controlled conditions.

Key Results

  • The proposed network synthesis model successfully generates synthetic PPI networks whose internal properties (degree distribution, clustering coefficient) and cross-network properties (potential ortholog distribution, sequence similarity scores) closely resemble those of real PPI networks.
  • The NAPAbench benchmark was created, comprising pairwise, 5-way, and 8-way alignment datasets generated using DMC, DMR, and CG models.
  • Performance evaluation of five network alignment algorithms (IsoRank, IsoRankN, NetworkBLAST-M, Græmlin, and MI-GRAAL) on NAPAbench revealed distinct performance profiles:
  • NetworkBLAST-M showed high specificity and consistency in pairwise alignments but degraded in multi-way alignments.
  • IsoRankN generally performed best in multi-way alignments (5-way and 8-way) in terms of specificity, sensitivity (CN), and consistency (MNE), demonstrating better coverage of equivalence classes spanning multiple species.
  • Græmlin showed moderate performance but was often outperformed by IsoRankN in multi-way scenarios.
  • The study also analyzed the impact of sequence similarity bias on algorithm performance, showing that IsoRank, IsoRankN, and Græmlin are more sensitive to this bias than NetworkBLAST-M and MI-GRAAL.
  • Computational complexity varied, with NetworkBLAST-M and Græmlin (excluding training) being the fastest, while IsoRankN and MI-GRAAL were more computationally intensive.

Limitations and Future Work

  • Parameter tuning: The authors acknowledge that setting parameters like Pfo (functional inheritance probability) and λmax (sequence divergence extent) for the synthesis model is practically difficult and relies on existing studies. Future work could explore more data-driven methods for parameter estimation.
  • Network growth model selection: While the paper compares DMC, DMR, and CG, the choice of which model to use for generating ancestral or descendant networks can influence the resulting network properties. The paper suggests that DMC and CG might capture hierarchical modularity better than DMR.
  • Future work: The authors suggest that the proposed model can be extended to incorporate other network evolution models and various similarity measures, further enhancing its realism and applicability. The NAPAbench datasets are intended to be a living resource for ongoing algorithm development and evaluation.

Summary updated

Abstract

In this work, we introduce a novel network synthesis model that can generate families of evolutionarily related synthetic protein-protein interaction (PPI) networks. Given an ancestral network, the proposed model generates the network family according to a hypothetical phylogenetic tree, where the descendant networks are obtained through duplication and divergence of their ancestors, followed by network growth using network evolution models. We demonstrate that this network synthesis model can effectively create synthetic networks whose internal and cross-network properties closely resemble those of real PPI networks. The proposed model can serve as an effective framework for generating comprehensive benchmark datasets that can be used for reliable performance assessment of comparative network analysis algorithms. Using this model, we constructed a large-scale network alignment benchmark, called NAPAbench, and evaluated the performance of several representative network alignment algorithms. Our analysis clearly shows the relative performance of the leading network algorithms, with their respective advantages and disadvantages. The algorithm and source code of the network synthesis model and the network alignment benchmark NAPAbench are publicly available at http://www.ece.tamu.edu/bjyoon/NAPAbench/.
BibTeX
@inproceedings{sahraeian2012network,
  author = {Sayed Mohammad Ebrahim Sahraeian and Byung-Jun Yoon},
  title = {{A Network Synthesis Model for Generating Protein Interaction Network Families}},
  booktitle = {PLoS},
  year = {2012},
  doi = {10.1371/journal.pone.0041474},
}
Figure