Simultaneous reconstruction of multiple signaling pathways via the prize-collecting steiner forest problem

Nurcan Tuncbag, Alfredo Braunstein, Andrea Pagnani, Shao Shan Carol Huang, Jennifer Chayes, Christian Borgs, Riccardo Zecchina, Ernest Fraenkel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Signaling networks are essential for cells to control processes such as growth 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. We overcome these problems and use "omic" data to simultaneously reconstruct 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.

Original languageEnglish (US)
Title of host publicationResearch in Computational Molecular Biology - 16th Annual International Conference, RECOMB 2012, Proceedings
Pages287-301
Number of pages15
DOIs
StatePublished - 2012
Event16th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2012 - Barcelona, Spain
Duration: Apr 21 2012Apr 24 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7262 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2012
CountrySpain
CityBarcelona
Period4/21/124/24/12

Keywords

  • Prize-collecting Steiner forest
  • multiple network reconstruction
  • signaling pathways

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Simultaneous reconstruction of multiple signaling pathways via the prize-collecting steiner forest problem'. Together they form a unique fingerprint.

Cite this