Biology – Quantitative Biology – Molecular Networks
Scientific paper
2005-09-27
Biology
Quantitative Biology
Molecular Networks
34 pages, 5 Postscript figures
Scientific paper
A useful approach to the mathematical analysis of large-scale biological networks is based upon their decompositions into monotone dynamical systems. This paper deals with two computational problems associated to finding decompositions which are optimal in an appropriate sense. In graph-theoretic language, the problems can be recast in terms of maximal sign-consistent subgraphs. The theoretical results include polynomial-time approximation algorithms as well as constant-ratio inapproximability results. One of the algorithms, which has a worst-case guarantee of 87.9 percent from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson. The algorithm was implemented and tested on a Drosophila segmentation network and an Epidermal Growth Factor Receptor pathway model, and it was found to perform close to optimally.
DasGupta Bhaskar
Enciso German Andres
Sontag Eduardo
Zhang Yi
No associations
LandOfFree
Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-239134