Algorithmic and complexity results for decompositions of biological networks into monotone subsystems

Bhaskar DasGupta, German Andres Enciso, Eduardo Sontag, Yi Zhang

Research output: Contribution to journalArticle

46 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)161-178
Number of pages18
JournalBioSystems
Volume90
Issue number1
DOIs
StatePublished - Jul 1 2007

Fingerprint

Biological Networks
Approximation algorithms
Approximation Algorithms
Monotone
Subsystem
Monotone Dynamical System
Decomposition
Semidefinite Programming Relaxation
Decompose
Inapproximability
Growth Factors
Satisfiability Problem
Semidefinite Programming
Drosophilidae
Mathematical Analysis
Epidermal Growth Factor Receptor
Receptor
Polynomial-time Algorithm
Subgraph
Pathway

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

DasGupta, Bhaskar ; Enciso, German Andres ; Sontag, Eduardo ; Zhang, Yi. / Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. In: BioSystems. 2007 ; Vol. 90, No. 1. pp. 161-178.
@article{925ba8d912064c65b51457c1ed103f14,
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 [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.",
keywords = "Approximation algorithms, Biological networks, Monotone dynamical systems, Semidefinite programming, Sign-consistent subgraphs",
author = "Bhaskar DasGupta and Enciso, {German Andres} and Eduardo Sontag and Yi Zhang",
year = "2007",
month = "7",
day = "1",
doi = "10.1016/j.biosystems.2006.08.001",
language = "English (US)",
volume = "90",
pages = "161--178",
journal = "BioSystems",
issn = "0303-2647",
publisher = "Elsevier Ireland Ltd",
number = "1",

}

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 journalArticle

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 -