Exploiting bounded signal flow for graph orientation based on cause-effect pairs.

Algorithms Mol Biol

Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany.

Published: August 2011

AI Article Synopsis

  • The study addresses the challenge of directing edges in an undirected network to maximize the routing of signal flows between sender-receiver pairs, which has implications for understanding cellular processes.
  • Recognizing that the problem is NP-hard, the research focuses on parameterized algorithmics, revealing relationships between maximum signal flow and various parameters, leading to both tractable cases and a notable complexity split between solvable and NP-hard situations.
  • The findings suggest that certain special cases relevant to biological applications can be solved optimally, highlighting how parameterized analysis enhances both understanding of the problem's complexity and the development of practical solutions.

Article Abstract

Background: We consider the following problem: Given an undirected network and a set of sender-receiver pairs, direct all edges such that the maximum number of "signal flows" defined by the pairs can be routed respecting edge directions. This problem has applications in understanding protein interaction based cell regulation mechanisms. Since this problem is NP-hard, research so far concentrated on polynomial-time approximation algorithms and tractable special cases.

Results: We take the viewpoint of parameterized algorithmics and examine several parameters related to the maximum signal flow over vertices or edges. We provide several fixed-parameter tractability results, and in one case a sharp complexity dichotomy between a linear-time solvable case and a slightly more general NP-hard case. We examine the value of these parameters for several real-world network instances.

Conclusions: Several biologically relevant special cases of the NP-hard problem can be solved to optimality. In this way, parameterized analysis yields both deeper insight into the computational complexity and practical solving strategies.

Download full-text PDF

Source
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3189099PMC
http://dx.doi.org/10.1186/1748-7188-6-21DOI Listing

Publication Analysis

Top Keywords

signal flow
8
examine parameters
8
exploiting bounded
4
bounded signal
4
flow graph
4
graph orientation
4
orientation based
4
based cause-effect
4
cause-effect pairs
4
pairs background
4

Similar Publications

Want AI Summaries of new PubMed Abstracts delivered to your In-box?

Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!