BACK TO INDEX

Publications of Eduardo D. Sontag jointly with Y. Zhang
Articles in journal or book chapters
  1. B. DasGupta, G.A. Enciso, E.D. Sontag, and Y. Zhang. Algorithmic and complexity aspects of decompositions of biological networks into monotone subsystems. BioSystems, 90:161-178, 2007. [PDF] [doi:http://dx.doi.org/10.1016/j.biosystems.2006.08.001] Keyword(s): monotone systems, systems biology, biochemical networks.
    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. The algorithm was implemented and tested on a Drosophila segmentation network and an Epidermal Growth Factor Receptor pathway model.


  2. B. Dasgupta, G.A. Enciso, E.D. Sontag, and Y. Zhang. Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. In C. Ālvarez and M. Serna, editors, Lecture Notes in Computer Science: Experimental Algorithms: 5th International Workshop, WEA 2006, pages 253-264. Springer-Verlag, 2006. Note: (Cala Galdana, Menorca, Spain, May 24-27, 2006). Keyword(s): systems biology, biochemical networks, monotone systems, theory of computing and complexity.



BACK TO INDEX




Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.




Last modified: Thu Nov 23 10:40:56 2017
Author: sontag.


This document was translated from BibTEX by bibtex2html