Usefulness and limitations of dK random graph models to predict interactions and functional homogeneity in biological networks under a pseudo-likelihood parameter estimation approach

Wenhui Wang, Juan Nunez-Iglesias, Yihui Luan, Fengzhu Sun

Introduction

Biological networks, such as protein-protein interaction (PPI) and gene coexpression networks, are characterized by non-random topological properties, including "heavy-tail" degree distributions and high clustering. To understand these systems, researchers employ "null models"—randomly generated graphs that preserve specific network features. This study investigates the dK-series, a hierarchy of models designed to capture increasingly complex structural properties, to determine if higher-order biological realism translates to better predictive power for interactions and functional gene modules.

The dK-Series Hierarchy

The dK-series provides a systematic way to model network topology by preserving local properties:

  • 0K: Preserves average edge density.
  • 1K: Preserves the degree distribution.
  • 2K: Preserves degree-degree correlations (assortativity).
  • 3K: Preserves triplet topologies, including clustering and triangles.
The eight possible configurations of three-node subgraphs used to define the 3K model.

Methodology

Because calculating exact probabilities for 2K and 3K structures is computationally intensive, the authors introduced a pseudo-likelihood parameter estimation approach. They utilized logistic regression to estimate interaction probabilities and a pseudo-likelihood ratio score to identify functional modules. These modules were then validated against the Gene Ontology (GO) database using yeast (S. cerevisiae) PPI and coexpression datasets.

Results: Edge Prediction and Module Identification

The 2K "Sweet Spot" for Edges

For predicting individual protein interactions, the 2K model emerged as the most effective. By capturing the tendency of nodes to connect to others with similar degrees, it significantly outperformed simpler models. However, a notable "complexity trap" was observed with the 3K model.

ROC curves for edge prediction in the MIPS PPI network. While 2K improves over 1K, the 3K model shows a significant drop in performance due to estimation noise.

Diminishing Returns in Module Identification

Surprisingly, higher-order models did not offer a significant advantage in identifying functional modules. In PPI networks, the 1K, 2K, and 3K models performed almost identically. In gene coexpression networks, the simplest model (0K) actually provided the best predictive power, suggesting that simple connection density is a more reliable biological signal in that context than complex topology.

Discussion and Conclusion

The study reveals a clear trade-off between model complexity and predictive accuracy. While 2K and 3K models can generate random graphs that statistically resemble real networks, the 3K model often suffers from the "curse of dimensionality." The sheer number of possible triplet configurations leads to estimation noise that can overwhelm the biological signal.

Ultimately, while 2K models are highly effective for edge prediction, simpler models are often sufficient—and sometimes superior—for identifying higher-level functional organization in biological systems. Future work may refine these estimation techniques to better leverage higher-order correlations in larger, more complex datasets.

Summary updated

Abstract

Many aspects of biological functions can be modeled by biological networks, such as protein interaction networks, metabolic networks, and gene coexpression networks. Studying the statistical properties of these networks in turn allows us to infer biological function. Complex statistical network models can potentially more accurately describe the networks, but it is not clear whether such complex models are better suited to find biologically meaningful subnetworks. Recent studies have shown that the degree distribution of the nodes is not an adequate statistic in many molecular networks. We sought to extend this statistic with 2nd and 3rd order degree correlations and developed a pseudo-likelihood approach to estimate the parameters. The approach was used to analyze the MIPS and BIOGRID yeast protein interaction networks, and two yeast coexpression networks. We showed that 2nd order degree correlation information gave better predictions of gene interactions in both protein interaction and gene coexpression networks. However, in the biologically important task of predicting functionally homogeneous modules, degree correlation information performs marginally better in the case of the MIPS and BIOGRID protein interaction networks, but worse in the case of gene coexpression networks. Our use of dK models showed that incorporation of degree correlations could increase predictive power in some contexts, albeit sometimes marginally, but, in all contexts, the use of third-order degree correlations decreased accuracy. However, it is possible that other parameter estimation methods, such as maximum likelihood, will show the usefulness of incorporating 2nd and 3rd degree correlations in predicting functionally homogeneous modules.
BibTeX
@article{wang2009usefulness,
  author = {Wenhui Wang and Juan Nunez-Iglesias and Yihui Luan and Fengzhu Sun},
  title = {{Usefulness and limitations of dK random graph models to predict interactions and functional homogeneity in biological networks under a pseudo-likelihood parameter estimation approach}},
  journal = {BMC Bioinformatics},
  year = {2009},
  doi = {10.1186/1471-2105-10-277},
}
Figure