A minimum-labeling approach for reconstructing protein networks across multiple conditions

Algorithms for Molecular Biology

Arnon Mazza³  Irit Gat-Viks²  Hesso Farhan¹  Roded Sharan³ 

[1] Biotechnology Institute Thurgau, University of Konstanz, Unterseestrasse 47, CH-8280 Kreuzlingen, Switzerland

[2] Department of Cell Research and Immunology, Tel Aviv University, 69978 Tel Aviv, Israel

[3] Blavatnik School of Computer Science, Tel Aviv University, 69978 Tel Aviv, Israel

关键词: Integer linear programming;    Graph algorithms;    Protein-protein interaction networks;   

Others  :  793054
DOI  :  10.1186/1748-7188-9-1

 received in 2013-11-30, accepted in 2014-01-22,  发布年份 2014

【 摘 要 】

Background

The sheer amounts of biological data that are generated in recent years have driven the development of network analysis tools to facilitate the interpretation and representation of these data. A fundamental challenge in this domain is the reconstruction of a protein-protein subnetwork that underlies a process of interest from a genome-wide screen of associated genes. Despite intense work in this area, current algorithmic approaches are largely limited to analyzing a single screen and are, thus, unable to account for information on condition-specific genes, or reveal the dynamics (over time or condition) of the process in question.

Results

We propose a novel formulation for the problem of network reconstruction from multiple-condition data and devise an efficient integer program solution for it. We apply our algorithm to analyze the response to influenza infection and ER export regulation in humans. By comparing to an extant, single-condition tool we demonstrate the power of our new approach in integrating data from multiple conditions in a compact and coherent manner, capturing the dynamics of the underlying processes.

【 授权许可】

   
2014 Mazza et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

【 参考文献 】

• [1]Beisser D, Klau G, Dandekar T, Mueller T, Dittrich M: BioNet an R-package for the functional analysis of biological networks. Bioinformatics 2010, 26:1129-1130.
• [2]Huang S, Fraenkel E: Integrating proteomic, transcriptional, and interactome data reveals hidden components of signaling and regulatory networks. Sci Signal 2009, 2(81):40.
• [3]Lotem E, Riva L, Su L, Gitler A, Cashikar A, King O, Auluck P, Geddie M, Valastyan J, Karger D, Lindquist S, Fraenkel E: Bridging high-throughput genetic and transcriptional data reveals cellular responses to alpha-synuclein toxicity. Nature Genet 2009, 41:316-323.
• [4]Yosef N, Zalckvar E, Rubinstein A, Homilius M, Atias N, Vardi L, Berman I, Zur H, Kimchi A, Ruppin E, Sharan R: ANAT a tool for constructing and analyzing functional protein networks. Sci Signal 2011, 4(196):1. doi:10.1126/scisignal.2001935
• [5]Garey M, Johnson D: Computers and Intractability A Guide to the Theory of NP-Completeness San Francisco: W.H. Freeman & Co.. 1979.
• [6]Shapira S, Viks I, Shum B, Dricot A, Degrace M, Liguo W, Gupta P, Hao T, Silver S, Root D, Hill D, Regev A, Hacohen N: A physical and regulatory map of host-influenza interactions reveals pathways in H1N1 infection. Cell 2009, 139(7):1255-1267.
• [7]Engelhardt O, Sirma H, Pandolfi P, Haller O: Mx1 GTPase accumulates in distinct nuclear domains and inhibits influenza a virus in cells that lack promyelocytic leukaemia protein nuclear bodies. J Gen Virol 2004, 85(8):2315-2326.
• [8]Wagner S, Beli P, Weinert B, Nielsen M, Cox J, Mann M, Choudhary C: A proteome-wide, quantitative survey of in vivo ubiquitylation sites reveals widespread regulatory roles. Mol Cell Proteomics 2011., 10(10) doi:10.1074/mcp.M111.013284
• [9]Watson P, Townley A, Koka P, Palmer K, Stephens D: Sec16 defines endoplasmic reticulum exit sites and is required for secretory cargo export in mammalian cells. Traffic 2006, 7(12):1678-1687.
• [10]Farhan H, Wendeler M, Mitrovic S, Fava E, Silberberg Y, Sharan R, Zerial M, Hauri H: MAPK signaling to the early secretory pathway revealed by kinase/phosphatase functional screening. J Cell Biol 2010, 189:997-1011.
• [11]Simpson J, Joggerst B, Laketa V, Verissimo F, Cetin C, Erfle H, Bexiga M, Singan V, Hériché J, Neumann B, Mateos A, Blake J, Bechtel S, Benes V, Wiemann S, Ellenberg J, Pepperkok R: Genome-wide RNAi screening identifies human proteins with a regulatory function in the early secretory pathway. Nat Cell Biol 2012, 14(7):764-774.
• [12]Ishihara N, Hamasaki M, Yokota S, Suzuki K, Kamada Y, Kihara A, Yoshimori T, Noda T, Ohsumi Y: Autophagosome requires specific early sec proteins for its formation and NSF/SNARE for vacuolar fusion. Mol Biol Cell 2001, 12(11):3690-3702.
• [13]Mizushima N: The role of the Atg1/ULK1 complex in autophagy regulation. Curr Opin Cell Biol 2010, 22(2):132-139.
• [14]Hamasaki M, Furuta N, Matsuda A, Nezu A, Yamamoto A, Fujita N, Oomori H, Noda T, Haraguchi T, Hiraoka Y, Amano A, Yoshimori T: Autophagosomes form at ER-mitochondria contact sites. Nature 2013, 495(7441):389-393.
• [15]Itakura E, Mizushima N: Syntaxin 17 the autophagosomal SNARE. Autophagy 2013, 9(6):917-919.