Cited By
View all- Salem SOzcaglar CChen JZaki MPandey GRangwala HKarypis G(2013)MFMSProceedings of the 12th International Workshop on Data Mining in Bioinformatics10.1145/2500863.2500869(51-57)Online publication date: 11-Aug-2013
Reverse engineering molecular hypergraphs
Pages 68 - 75
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 multi-way interactions among molecules, which occur very often within cells. Hypergraphs may be better representations for such interactions, since hyperedges can naturally represent relationships among multiple molecules.
Here we propose using hypergraphs to capture the uncertainty that is inherent in reverse engineering gene-gene networks from systems biology datasets. Some subsets of nodes may induce highly varying subgraphs across an ensemble of high-scoring 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 datasets with high precision and recall. We apply our techniques to a published dataset of pathway structures inferred from quantitative genetic interaction data in S. cerevisiae related to the unfolded protein response in the endoplasmic reticulum (ER). Our approach discovers several hyperedges that capture the uncertain connectivity of genes in specific pathways and complexes related to the ER.
Our work demonstrates that molecular interaction hypergraphs are powerful representations for capturing uncertainty in network structure. The hyperedges we discover directly suggest groups of genes for which further experiments may be required in order to precisely discover interaction patterns.
References
[1]
A. Battle, M. C. Jonikas, P. Walter, J. S. Weissman, and D. Koller. Automated identification of pathways from quantitative genetic interaction data. Molecular Systems Biology, 6(1):379, 2010.
[2]
A. Bernard, D. S. Vaughn, and A. J. Hartemink. Reconstructing the Topology of Protein Complexes. In Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology (RECOMB'07), pages 32--46. Springer, 2007.
[3]
G. F. Berriz, J. E. Beaver, C. Cenik, M. Tasan, and F. P. Roth. Next generation software for functional trend analysis. Bioinformatics, 25(22):3043--3044, 2009.
[4]
T. Christensen, A. Oliveira, and J. Nielsen. Reconstruction and logical modeling of glucose repression signaling pathways in Saccharomyces cerevisiae. BMC Systems Biology, 3(1):7, 2009.
[5]
E. Conibear and T. Stevens. Vps52p, Vps53p, and Vps54p form a novel multisubunit complex required for protein sorting at the yeast late golgi. Molecular Biology of the Cell, 11(1):305--323, 2000.
[6]
E. Demir et al. The BioPAX community standard for pathway data sharing. Nature Biotechnology, 28(9):935--942, 2010.
[7]
J. Dutkowski and T. Ideker. Protein Networks as Logic Functions in Development and Cancer. PLoS Comput. Biol., 7(9):e1002180, 2011.
[8]
N. Friedman and D. Koller. Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks. Machine learning, 50(1):95--125, 2003.
[9]
L. S. Heath and A. A. Sioson. Semantics of multimodal network models. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(2):271--280, 2009.
[10]
C. Huttenhower, E. M. Haley, M. A. Hibbs, V. Dumeaux, D. R. Barrett, H. A. Coller, and O. G. Troyanskaya. Exploring the human genome with functional maps. Genome Res, 19(6):1093--106, 2009.
[11]
T. Ideker and R. Sharan. Protein networks in disease. Genome Res., 18(4):644--652, 2008.
[12]
M. C. Jonikas, S. R. Collins, V. Denic, E. Oh, E. M. Quan, V. Schmid, J. Weibezahn, B. Schwappach, P. Walter, J. S. Weissman, and M. Schuldiner. Comprehensive characterization of genes required for protein folding in the endoplasmic reticulum. Science, 323(5922):1693--1697, 2009.
[13]
S. Klamt, U.-U. Haus, and F. Theis. Hypergraphs and cellular networks. PLoS Comput. Biol., 5(5):e1000385, 2009.
[14]
W. Li, C. Liu, T. Zhang, H. Li, M. Waterman, and X. Zhou. Integrative analysis of many weighted co-expression networks using tensor computation. PLoS Computational Biology, 7(6):e1001106, 2011.
[15]
J. Long and C. Hartman. ODES: an overlapping dense sub-graph algorithm. Bioinformatics, 26(21):2788--2789, 2010.
[16]
F. Markowetz and R. Spang. Inferring cellular networks - a review. BMC Bioinformatics, 8(Suppl 6):S5, 2007.
[17]
A. Mithani, G. M. Preston, and J. Hein. Rahnuma: hypergraph-based tool for metabolic pathway prediction and network comparison. Bioinformatics, 25(14):1831--1832, 2009.
[18]
D. Pe'er. Bayesian network analysis of signaling networks: a primer. Science's STKE: Signal Transduction Knowledge Environment., 2005(281):pl4, 2005.
[19]
E. Ramadan, A. Tarafdar, and A. Pothen. A hypergraph model for the yeast protein complex network. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, pages 189--196. IEEE, 2004.
[20]
C. F. Schaefer, K. Anthony, S. Krupa, J. Buchoff, M. Day, T. Hannay, and K. H. Buetow. PID: the Pathway Interaction Database. Nucleic Acids Res, 37(Database issue):D674--9, 2009.
[21]
S.-E. Schelhorn, J. Mestre, M. Albrecht, and E. Zotenko. Inferring physical protein contacts from large-scale purification data of protein complexes. Molecular & Cellular Proteomics, 10(6):M110.004929, 2011.
[22]
M. Schuldiner, J. Metz, V. Schmid, V. Denic, M. Rakwalska, H. Schmitt, B. Schwappach, and J. Weissman. The GET complex mediates insertion of tail-anchored proteins into the ER membrane. Cell, 134(4):634--645, 2008.
[23]
R. Sharan and T. Ideker. Modeling cellular machinery through biological network comparison. Nat Biotechnol, 24(4):427--33, 2006.
[24]
C. Stark, B.-J. J. Breitkreutz, A. Chatr-Aryamontri, L. Boucher, R. Oughtred, M. S. Livstone, J. Nixon, K. Van Auken, X. Wang, X. Shi, T. Reguly, J. M. Rust, A. Winter, K. Dolinski, and M. Tyers. The BioGRID interaction database: 2011 update. Nucleic Acids Research, 39(Database issue):D698--D704, 2011.
[25]
I. Ulitsky, A. Krishnamurthy, R. M. Karp, and R. Shamir. DEGAS: De Novo Discovery of Dysregulated Pathways in Human Diseases. PLoS ONE, 5(10):e13367, 2010.
[26]
K. Wang, M. Saito, B. C. Bisikirska, M. J. Alvarez, W. K. Lim, P. Rajbhandari, Q. Shen, I. Nemenman, K. Basso, A. A. Margolin, U. Klein, R. Dalla-Favera, and A. Califano. Genome-wide identification of post-translational modulators of transcription factor activity in human B cells. Nature Biotechnology, 27(9):829--837, 2009.
[27]
W. Zhou and L. Nakhleh. Properties of metabolic graphs: biological organization or representation artifacts? BMC Bioinformatics, 12(1):132, 2011.
Index Terms
- Reverse engineering molecular hypergraphs
Recommendations
Reverse Engineering Molecular Hypergraphs
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 ...
Reverse Engineering Gene Networks: A Comparative Study at Genome-scale
ACM-BCB '17: Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health InformaticsMotivation: Reverse engineering gene networks from expression data is a widelymstudied problem, for which numerous mathematical models have been developed. Network reconstruction methods can be used to study specific pathways, or can be applied at the ...
Using Qualitative Probability in Reverse-Engineering Gene Regulatory Networks
This paper demonstrates the use of qualitative probabilistic networks (QPNs) to aid Dynamic Bayesian Networks (DBNs) in the process of learning the structure of gene regulatory networks from microarray gene expression data. We present a study which ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2012
725 pages
ISBN:9781450316705
DOI:10.1145/2382936
- General Chair:
- Sanjay Ranka,
- Program Chairs:
- Tamer Kahveci,
- Mona Singh
Copyright © 2012 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 October 2012
Check for updates
Qualifiers
- Research-article
Funding Sources
Conference
BCB' 12
Sponsor:
BCB' 12: ACM International Conference on Bioinformatics, Computational Biology and Biomedicine
October 7 - 10, 2012
Florida, Orlando
Acceptance Rates
BCB '12 Paper Acceptance Rate 33 of 159 submissions, 21%;
Overall Acceptance Rate 254 of 885 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 194Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Jan 2025
Other Metrics
Citations
Cited By
View all- Salem SOzcaglar CChen JZaki MPandey GRangwala HKarypis G(2013)MFMSProceedings of the 12th International Workshop on Data Mining in Bioinformatics10.1145/2500863.2500869(51-57)Online publication date: 11-Aug-2013
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in