@inproceedings{9a5d89e0c0a64699b69b27455ee8ad69,
title = "Algorithmic and complexity results for decompositions of biological networks into monotone subsystems",
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 [14]. The algorithm was implemented and tested on a Drosophila segmentation network [7] and an Epidermal Growth Factor Receptor pathway model [25], and it was found to perform close to optimally.",
author = "Bhaskar DasGupta and Enciso, {German A.} and Eduardo Sontag and Yi Zhang",
year = "2006",
language = "English (US)",
isbn = "3540345973",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "253--264",
booktitle = "Experimental Algorithms - 5th International Workshop, WEA 2006, Proceedings",
address = "Germany",
note = "5th International Workshop on Experimental Algorithms, WEA 2006 ; Conference date: 24-05-2006 Through 27-05-2006",
}