Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Bhaskar DasGupta , German A. Enciso , Eduardo Sontag , Yi Zhang

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. More... »

PAGES

253-264

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11764298_23

DOI

http://dx.doi.org/10.1007/11764298_23

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1013605920


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of IL at Chicago, 60607, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.170205.1", 
          "name": [
            "Department of Computer Science, University of IL at Chicago, 60607, Chicago, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Mathematical Biosciences Institute, 250 Mathematics Building, 231 W 18th Ave, 43210, Columbus, OH, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Mathematical Biosciences Institute, 250 Mathematics Building, 231 W 18th Ave, 43210, Columbus, OH, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Enciso", 
        "givenName": "German A.", 
        "id": "sg:person.0575631410.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0575631410.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sontag", 
        "givenName": "Eduardo", 
        "id": "sg:person.0714217520.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0714217520.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of IL at Chicago, 60607, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.170205.1", 
          "name": [
            "Department of Computer Science, University of IL at Chicago, 60607, Chicago, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Yi", 
        "id": "sg:person.0643604113.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0643604113.71"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "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.", 
    "editor": [
      {
        "familyName": "\u00c0lvarez", 
        "givenName": "Carme", 
        "type": "Person"
      }, 
      {
        "familyName": "Serna", 
        "givenName": "Mar\u00eda", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11764298_23", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-34597-8", 
        "978-3-540-34598-5"
      ], 
      "name": "Experimental Algorithms", 
      "type": "Book"
    }, 
    "keywords": [
      "monotone dynamical systems", 
      "polynomial-time approximation algorithm", 
      "semidefinite programming (SDP) relaxation approach", 
      "biological networks", 
      "graph-theoretic language", 
      "large-scale biological networks", 
      "worst-case guarantees", 
      "Drosophila segmentation network", 
      "segmentation network", 
      "dynamical systems", 
      "monotone subsystems", 
      "mathematical analysis", 
      "Goemans-Williamson", 
      "computational problems", 
      "complexity results", 
      "theoretical results", 
      "relaxation approach", 
      "appropriate sense", 
      "approximation algorithm", 
      "inapproximability results", 
      "algorithm", 
      "network", 
      "algorithmics", 
      "problem", 
      "guarantees", 
      "optimality", 
      "decomposition", 
      "subgraphs", 
      "pathway model", 
      "language", 
      "subsystems", 
      "approach", 
      "system", 
      "model", 
      "results", 
      "terms", 
      "sense", 
      "useful approach", 
      "analysis", 
      "paper"
    ], 
    "name": "Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems", 
    "pagination": "253-264", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013605920"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11764298_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11764298_23", 
      "https://app.dimensions.ai/details/publication/pub.1013605920"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_444.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11764298_23"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11764298_23'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11764298_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11764298_23'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11764298_23'


 

This table displays all metadata directly associated to this object as RDF triples.

143 TRIPLES      22 PREDICATES      68 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11764298_23 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 anzsrc-for:0102
4 anzsrc-for:08
5 anzsrc-for:0802
6 schema:author Nc53171dc77bb41a7a0b30b7eecfa7f88
7 schema:datePublished 2006
8 schema:datePublishedReg 2006-01-01
9 schema:description 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.
10 schema:editor N000b129cbcb941009b88fdb48a3adbed
11 schema:genre chapter
12 schema:isAccessibleForFree true
13 schema:isPartOf N5f74ec2f89e34af8baebd598f6537330
14 schema:keywords Drosophila segmentation network
15 Goemans-Williamson
16 algorithm
17 algorithmics
18 analysis
19 approach
20 appropriate sense
21 approximation algorithm
22 biological networks
23 complexity results
24 computational problems
25 decomposition
26 dynamical systems
27 graph-theoretic language
28 guarantees
29 inapproximability results
30 language
31 large-scale biological networks
32 mathematical analysis
33 model
34 monotone dynamical systems
35 monotone subsystems
36 network
37 optimality
38 paper
39 pathway model
40 polynomial-time approximation algorithm
41 problem
42 relaxation approach
43 results
44 segmentation network
45 semidefinite programming (SDP) relaxation approach
46 sense
47 subgraphs
48 subsystems
49 system
50 terms
51 theoretical results
52 useful approach
53 worst-case guarantees
54 schema:name Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems
55 schema:pagination 253-264
56 schema:productId N7fd18863f7754c24b1b6c461337898b7
57 Nad4f241d5ee148b7bd36d3cca26f2489
58 schema:publisher N93056c0d91db460880cccdcebd06f72d
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013605920
60 https://doi.org/10.1007/11764298_23
61 schema:sdDatePublished 2022-12-01T06:54
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N876873e1b5604886934a5038108075a0
64 schema:url https://doi.org/10.1007/11764298_23
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N000b129cbcb941009b88fdb48a3adbed rdf:first N46a1178c218140fa8581c091d2e55d48
69 rdf:rest N56344012f4af4c5898a3f43cde056020
70 N46a1178c218140fa8581c091d2e55d48 schema:familyName Àlvarez
71 schema:givenName Carme
72 rdf:type schema:Person
73 N56344012f4af4c5898a3f43cde056020 rdf:first Nec3410bfe0fc4149bc6f53ec7353fd6f
74 rdf:rest rdf:nil
75 N5f74ec2f89e34af8baebd598f6537330 schema:isbn 978-3-540-34597-8
76 978-3-540-34598-5
77 schema:name Experimental Algorithms
78 rdf:type schema:Book
79 N7fd18863f7754c24b1b6c461337898b7 schema:name doi
80 schema:value 10.1007/11764298_23
81 rdf:type schema:PropertyValue
82 N8730503ef1c745cab126608ce958b8de rdf:first sg:person.0714217520.83
83 rdf:rest Nf52a5a0c49fd45db815c3f8837a575a5
84 N876873e1b5604886934a5038108075a0 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 N93056c0d91db460880cccdcebd06f72d schema:name Springer Nature
87 rdf:type schema:Organisation
88 Nad4f241d5ee148b7bd36d3cca26f2489 schema:name dimensions_id
89 schema:value pub.1013605920
90 rdf:type schema:PropertyValue
91 Nc53171dc77bb41a7a0b30b7eecfa7f88 rdf:first sg:person.0763403270.10
92 rdf:rest Ned2b5e892912408f94942129fe12dabc
93 Nec3410bfe0fc4149bc6f53ec7353fd6f schema:familyName Serna
94 schema:givenName María
95 rdf:type schema:Person
96 Ned2b5e892912408f94942129fe12dabc rdf:first sg:person.0575631410.00
97 rdf:rest N8730503ef1c745cab126608ce958b8de
98 Nf52a5a0c49fd45db815c3f8837a575a5 rdf:first sg:person.0643604113.71
99 rdf:rest rdf:nil
100 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
101 schema:name Mathematical Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
104 schema:name Pure Mathematics
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
107 schema:name Applied Mathematics
108 rdf:type schema:DefinedTerm
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
113 schema:name Computation Theory and Mathematics
114 rdf:type schema:DefinedTerm
115 sg:person.0575631410.00 schema:affiliation grid-institutes:None
116 schema:familyName Enciso
117 schema:givenName German A.
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0575631410.00
119 rdf:type schema:Person
120 sg:person.0643604113.71 schema:affiliation grid-institutes:grid.170205.1
121 schema:familyName Zhang
122 schema:givenName Yi
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0643604113.71
124 rdf:type schema:Person
125 sg:person.0714217520.83 schema:affiliation grid-institutes:grid.430387.b
126 schema:familyName Sontag
127 schema:givenName Eduardo
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0714217520.83
129 rdf:type schema:Person
130 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.170205.1
131 schema:familyName DasGupta
132 schema:givenName Bhaskar
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
134 rdf:type schema:Person
135 grid-institutes:None schema:alternateName Mathematical Biosciences Institute, 250 Mathematics Building, 231 W 18th Ave, 43210, Columbus, OH, USA
136 schema:name Mathematical Biosciences Institute, 250 Mathematics Building, 231 W 18th Ave, 43210, Columbus, OH, USA
137 rdf:type schema:Organization
138 grid-institutes:grid.170205.1 schema:alternateName Department of Computer Science, University of IL at Chicago, 60607, Chicago, IL, USA
139 schema:name Department of Computer Science, University of IL at Chicago, 60607, Chicago, IL, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
142 schema:name Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
143 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...