Reverse Engineering Molecular Hypergraphs
- 13 June 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 10 (5) , 1113-1124
Abstract
Analysis of molecular interaction networks is pervasive in systems biology. This research relies almost entirely on graphs for modeling interactions. However, edges in graphs cannot represent multiway interactions among molecules, which occur very often within cells. Hypergraphs may be better representations for networks having such interactions, since hyperedges can naturally represent relationships among multiple molecules. Here, we propose using hypergraphs to capture the uncertainty inherent in reverse engineering gene-gene networks. Some subsets of nodes may induce highly varying subgraphs across an ensemble of networks inferred by a reverse engineering algorithm. We provide a novel formulation of hyperedges to capture this uncertainty in network topology. We propose a clustering-based approach to discover hyperedges. We show that our approach can recover hyperedges planted in synthetic data sets with high precision and recall, even for moderate amount of noise. We apply our techniques to a data set of pathways inferred from genetic interaction data in S. cerevisiae related to the unfolded protein response. Our approach discovers several hyperedges that capture the uncertain connectivity of genes in relevant protein complexes, suggesting that further experiments may be required to precisely discern their interaction patterns. We also show that these complexes are not discovered by an algorithm that computes frequent and dense subgraphs.Keywords
This publication has 30 references indexed in Scilit:
- Protein Networks as Logic Functions in Development and CancerPLOS Computational Biology, 2011
- Integrative Analysis of Many Weighted Co-Expression Networks Using Tensor ComputationPLOS Computational Biology, 2011
- The BioPAX community standard for pathway data sharingNature Biotechnology, 2010
- Hypergraphs and Cellular NetworksPLOS Computational Biology, 2009
- Rahnuma: hypergraph-based tool for metabolic pathway prediction and network comparisonBioinformatics, 2009
- Comprehensive Characterization of Genes Required for Protein Folding in the Endoplasmic ReticulumScience, 2009
- Exploring the human genome with functional mapsGenome Research, 2009
- Reconstruction and logical modeling of glucose repression signaling pathways in Saccharomyces cerevisiaeBMC Systems Biology, 2009
- Inferring cellular networks – a reviewBMC Bioinformatics, 2007
- Being Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian NetworksMachine Learning, 2003