title: Simultaneous reconstruction of multiple signaling pathways via the prize-collecting steiner forest problem.
abstract: Signaling and regulatory networks are essential for cells to control processes such as growth, differentiation, and response to stimuli. Although many "omic" data sources are available to probe signaling pathways, these data are typically sparse and noisy. Thus, it has been difficult to use these data to discover the cause of the diseases and to propose new therapeutic strategies. We overcome these problems and use "omic" data to reconstruct simultaneously multiple pathways that are altered in a particular condition by solving the prize-collecting Steiner forest problem. To evaluate this approach, we use the well-characterized yeast pheromone response. We then apply the method to human glioblastoma data, searching for a forest of trees, each of which is rooted in a different cell-surface receptor. This approach discovers both overlapping and independent signaling pathways that are enriched in functionally and clinically relevant proteins, which could provide the basis for new therapeutic strategies. Although the algorithm was not provided with any information about the phosphorylation status of receptors, it identifies a small set of clinically relevant receptors among hundreds present in the interactome.
authors: Department of Biological Engineering, Massachusetts Institute of Technology, Cambridge, MA, USA.
authors: Nurcan
authors: N
authors: Tuncbag
authors: Alfredo
authors: A
authors: Braunstein
authors: Andrea
authors: A
authors: Pagnani
authors: Shao-Shan Carol
authors: SS
authors: Huang
authors: Jennifer
authors: J
authors: Chayes
authors: Christian
authors: C
authors: Borgs
authors: Riccardo
authors: R
authors: Zecchina
authors: Ernest
authors: E
authors: Fraenkel
mesh_terms: D000465:Algorithms; D001932:Brain Neoplasms / Q000235:genetics*; D002450:Cell Communication; D020869:Gene Expression Profiling; D053263:Gene Regulatory Networks; D005909:Glioblastoma / Q000235:genetics*; D006801:Humans; D008954:Models, Biological; D009363:Neoplasm Proteins / Q000235:genetics*; D010597:Pharmacogenetics; D010675:Pheromones / Q000235:genetics*; D025941:Protein Interaction Mapping / Q000706:statistics & numerical data; D011956:Receptors, Cell Surface / Q000235:genetics*; D012441:Saccharomyces cerevisiae / Q000235:genetics*; D015398:Signal Transduction
chemical_list: D009363:Neoplasm Proteins; D010675:Pheromones; D011956:Receptors, Cell Surface
references: Cancer Res. 2009 Feb 1;69(3):1212-20
references: 19176395
references: PLoS Comput Biol. 2009 Apr;5(4):e1000350
references: 19503817
references: Nat Genet. 2009 Mar;41(3):316-23
references: 19234470
references: Sci Signal. 2009 May 26;2(72):re3
references: 19471024
references: J Biol Chem. 2004 Apr 9;279(15):15183-95
references: 14739279
references: Mol Cell Proteomics. 2005 Mar;4(3):310-27
references: 15665377
references: Nat Biotechnol. 2006 Apr;24(4):427-33
references: 16601728
references: Phys Rev Lett. 2008 Jul 18;101(3):037208
references: 18764290
references: EMBO J. 1996 Jan 2;15(1):83-91
references: 8598209
references: Methods Enzymol. 2002;350:329-46
references: 12073322
references: Nucleic Acids Res. 2009 Jan;37(Database issue):D412-6
references: 18940858
references: Cell. 2010 Dec 10;143(6):1005-17
references: 21129771
references: Mol Cell Biol. 2001 Oct;21(19):6515-28
references: 11533240
references: Cancer Res. 1998 Dec 1;58(23):5275-9
references: 9850047
references: J Cell Physiol. 2007 Dec;213(3):649-53
references: 17886260
references: Oncogene. 2003 Feb 6;22(5):722-33
references: 12569364
references: Proc Natl Acad Sci U S A. 2007 Jul 31;104(31):12867-72
references: 17646646
references: PLoS Comput Biol. 2011 Mar;7(3):e1001095
references: 21390271
references: Growth Factors. 2004 Jun;22(2):89-95
references: 15253384
references: Gene. 2004 Apr 14;330:101-14
references: 15087129
references: Cancer Res. 2002 Jan 1;62(1):200-7
references: 11782378
references: Bioinformatics. 2007 Jul 1;23(13):i359-66
references: 17646318
references: Genes Dev. 1998 Sep 1;12(17):2673-83
references: 9732266
references: Nucleic Acids Res. 2011 Jul;39(Web Server issue):W424-9
references: 21576238
references: BMC Bioinformatics. 2010 Jun 29;11:355
references: 20587029
references: J Clin Invest. 2008 Sep;118(9):3109-22
references: 18677408
references: Sci STKE. 2003 Jun 17;2003(187):RE9
references: 12815191
references: Bioinformatics. 2008 Jul 1;24(13):i223-31
references: 18586718
references: Mol Cell Biol. 1997 Nov;17(11):6517-25
references: 9343415
references: Mol Syst Biol. 2008;4:162
references: 18319721
references: Genome Res. 2003 Nov;13(11):2498-504
references: 14597658
references: Science. 2010 May 21;328(5981):1043-6
references: 20489023
references: PLoS Comput Biol. 2010 Jan 15;6(1):e1000641
references: 20090828
references: Genes Dev. 2001 Aug 1;15(15):1913-25
references: 11485986
references: Bioinformatics. 2005 Aug 15;21(16):3448-9
references: 15972284
references: Proc Natl Acad Sci U S A. 2011 Jan 11;108(2):882-7
references: 21187432
references: J Steroid Biochem Mol Biol. 2002 Dec;83(1-5):211-7
references: 12650718
references: Sci Signal. 2009 Jul 28;2(81):ra40
references: 19638617
references: Science. 2004 Feb 6;303(5659):799-805
references: 14764868
references: J Comput Biol. 2004;11(2-3):243-62
references: 15285891
references: Nature. 2008 Oct 23;455(7216):1061-8
references: 18772890
references: Proc Natl Acad Sci U S A. 2011 Jun 14;108(24):9951-6
references: 21628563
references: Novartis Found Symp. 2004;262:235-43; discussion 243-6, 265-8
references: 15562833
references: Neoplasia. 2000 May-Jun;2(3):242-50
references: 10935510
references: J Biol Chem. 2002 Oct 4;277(40):37612-8
references: 12145299