  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.
