Hypothesis generation in signaling networks

Derek A. Ruths, Luay Nakhleh, M. Sriram Iyengar, Shrikanth A.G. Reddy, Prahlad T. Ram

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Biological signaling networks comprise the chemical processes by which cells detect and respond to changes in their environment. Such networks have been implicated in the regulation of important cellular activities, including cellular reproduction, mobility, and death. Though technological and scientific advances have facilitated the rapid accumulation of information about signaling networks, utilizing these massive information resources has become infeasible except through computational methods and computer-based tools. To date, visualization and simulation tools have received significant emphasis. In this paper, we present a graph-theoretic formalization of biological signaling network models that are in wide but informal use, and formulate two problems on the graph: the Constrained Downstream and Minimum Knockout Problems. Solutions to these problems yield qualitative tools for generating hypotheses about the networks, which can then be experimentally tested in a laboratory setting. Using established graph algorithms, we provide a solution to the Constrained Downstream Problem. We also show that the Minimum Knockout Problem is NP-Hard, propose a heuristic, and assess its performance. In tests on the Epidermal Growth Factor Receptor (EGFR) network, we find that our heuristic reports the correct solution to the problem in seconds. Source code for the implementations of both solutions is available from the authors upon request.

Original languageEnglish (US)
Pages (from-to)1546-1557
Number of pages12
JournalJournal of Computational Biology
Issue number9
StatePublished - Nov 2006
Externally publishedYes


  • Algorithms
  • Biology
  • Computational molecular biology
  • Evolution
  • Genomics
  • Phylogenetic trees

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Hypothesis generation in signaling networks'. Together they form a unique fingerprint.

Cite this