Abstract
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% from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson [Goemans, M., Williamson, D., 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (6), 1115-1145]. 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 161-178 |
| Number of pages | 18 |
| Journal | BioSystems |
| Volume | 90 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jul 1 2007 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Statistics and Probability
- Modeling and Simulation
- Biochemistry, Genetics and Molecular Biology(all)
- Applied Mathematics
Keywords
- Approximation algorithms
- Biological networks
- Monotone dynamical systems
- Semidefinite programming
- Sign-consistent subgraphs
Cite this
}
Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. / DasGupta, Bhaskar; Enciso, German Andres; Sontag, Eduardo; Zhang, Yi.
In: BioSystems, Vol. 90, No. 1, 01.07.2007, p. 161-178.Research output: Contribution to journal › Article
TY - JOUR
T1 - Algorithmic and complexity results for decompositions of biological networks into monotone subsystems
AU - DasGupta, Bhaskar
AU - Enciso, German Andres
AU - Sontag, Eduardo
AU - Zhang, Yi
PY - 2007/7/1
Y1 - 2007/7/1
N2 - 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% from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson [Goemans, M., Williamson, D., 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (6), 1115-1145]. 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.
AB - 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% from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson [Goemans, M., Williamson, D., 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (6), 1115-1145]. 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.
KW - Approximation algorithms
KW - Biological networks
KW - Monotone dynamical systems
KW - Semidefinite programming
KW - Sign-consistent subgraphs
UR - http://www.scopus.com/inward/record.url?scp=34447125063&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34447125063&partnerID=8YFLogxK
U2 - 10.1016/j.biosystems.2006.08.001
DO - 10.1016/j.biosystems.2006.08.001
M3 - Article
C2 - 17188805
AN - SCOPUS:34447125063
VL - 90
SP - 161
EP - 178
JO - BioSystems
JF - BioSystems
SN - 0303-2647
IS - 1
ER -