Adaptive Aggregation of Markov Chains: Quantitative Analysis of Chemical Reaction Networks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-07-16

AUTHORS

Alessandro Abate , Luboš Brim , Milan Češka , Marta Kwiatkowska

ABSTRACT

Quantitative analysis of Markov models typically proceeds through numerical methods or simulation-based evaluation. Since the state space of the models can often be large, exact or approximate state aggregation methods (such as lumping or bisimulation reduction) have been proposed to improve the scalability of the numerical schemes. However, none of the existing numerical techniques provides general, explicit bounds on the approximation error, a problem particularly relevant when the level of accuracy affects the soundness of verification results. We propose a novel numerical approach that combines the strengths of aggregation techniques (state-space reduction) with those of simulation-based approaches (automatic updates that adapt to the process dynamics). The key advantage of our scheme is that it provides rigorous precision guarantees under different measures. The new approach, which can be used in conjunction with time uniformisation techniques, is evaluated on two models of chemical reaction networks, a signalling pathway and a prokaryotic gene expression network: it demonstrates marked improvement in accuracy without performance degradation, particularly when compared to known state-space truncation techniques. More... »

PAGES

195-213

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-21690-4_12

DOI

http://dx.doi.org/10.1007/978-3-319-21690-4_12

DIMENSIONS

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


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/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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Abate", 
        "givenName": "Alessandro", 
        "id": "sg:person.012500146711.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012500146711.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brim", 
        "givenName": "Lubo\u0161", 
        "id": "sg:person.0645117057.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK", 
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "\u010ce\u0161ka", 
        "givenName": "Milan", 
        "id": "sg:person.016652663056.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016652663056.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "id": "sg:person.011375012273.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-07-16", 
    "datePublishedReg": "2015-07-16", 
    "description": "Quantitative analysis of Markov models typically proceeds through numerical methods or simulation-based evaluation. Since the state space of the models can often be large, exact or approximate state aggregation methods (such as lumping or bisimulation reduction) have been proposed to improve the scalability of the numerical schemes. However, none of the existing numerical techniques provides general, explicit bounds on the approximation error, a problem particularly relevant when the level of accuracy affects the soundness of verification results. We propose a novel numerical approach that combines the strengths of aggregation techniques (state-space reduction) with those of simulation-based approaches (automatic updates that adapt to the process dynamics). The key advantage of our scheme is that it provides rigorous precision guarantees under different measures. The new approach, which can be used in conjunction with time uniformisation techniques, is evaluated on two models of chemical reaction networks, a signalling pathway and a prokaryotic gene expression network: it demonstrates marked improvement in accuracy without performance degradation, particularly when compared to known state-space truncation techniques.", 
    "editor": [
      {
        "familyName": "Kroening", 
        "givenName": "Daniel", 
        "type": "Person"
      }, 
      {
        "familyName": "P\u0103s\u0103reanu", 
        "givenName": "Corina S.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-21690-4_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-21689-8", 
        "978-3-319-21690-4"
      ], 
      "name": "Computer Aided Verification", 
      "type": "Book"
    }, 
    "keywords": [
      "chemical reaction networks", 
      "reaction networks", 
      "state aggregation method", 
      "simulation-based approach", 
      "novel numerical approach", 
      "approximation error", 
      "explicit bounds", 
      "truncation technique", 
      "numerical scheme", 
      "Markov chain", 
      "state space", 
      "numerical method", 
      "numerical techniques", 
      "precision guarantees", 
      "numerical approach", 
      "simulation-based evaluation", 
      "Markov model", 
      "level of accuracy", 
      "aggregation method", 
      "aggregation techniques", 
      "gene expression networks", 
      "key advantage", 
      "scheme", 
      "new approach", 
      "performance degradation", 
      "network", 
      "bounds", 
      "model", 
      "approach", 
      "accuracy", 
      "verification results", 
      "guarantees", 
      "expression networks", 
      "space", 
      "problem", 
      "technique", 
      "error", 
      "adaptive aggregation", 
      "scalability", 
      "quantitative analysis", 
      "analysis", 
      "advantages", 
      "different measures", 
      "soundness", 
      "results", 
      "conjunction", 
      "measures", 
      "chain", 
      "improvement", 
      "evaluation", 
      "aggregation", 
      "strength", 
      "levels", 
      "degradation", 
      "pathway", 
      "method", 
      "approximate state aggregation methods", 
      "rigorous precision guarantees", 
      "time uniformisation techniques", 
      "uniformisation techniques", 
      "prokaryotic gene expression network", 
      "state-space truncation techniques"
    ], 
    "name": "Adaptive Aggregation of Markov Chains: Quantitative Analysis of Chemical Reaction Networks", 
    "pagination": "195-213", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044474057"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-21690-4_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-21690-4_12", 
      "https://app.dimensions.ai/details/publication/pub.1044474057"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_102.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-21690-4_12"
  }
]
 

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/978-3-319-21690-4_12'

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/978-3-319-21690-4_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21690-4_12'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21690-4_12'


 

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

152 TRIPLES      23 PREDICATES      87 URIs      80 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-21690-4_12 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N332845c436344c3abb4181984492c3c3
4 schema:datePublished 2015-07-16
5 schema:datePublishedReg 2015-07-16
6 schema:description Quantitative analysis of Markov models typically proceeds through numerical methods or simulation-based evaluation. Since the state space of the models can often be large, exact or approximate state aggregation methods (such as lumping or bisimulation reduction) have been proposed to improve the scalability of the numerical schemes. However, none of the existing numerical techniques provides general, explicit bounds on the approximation error, a problem particularly relevant when the level of accuracy affects the soundness of verification results. We propose a novel numerical approach that combines the strengths of aggregation techniques (state-space reduction) with those of simulation-based approaches (automatic updates that adapt to the process dynamics). The key advantage of our scheme is that it provides rigorous precision guarantees under different measures. The new approach, which can be used in conjunction with time uniformisation techniques, is evaluated on two models of chemical reaction networks, a signalling pathway and a prokaryotic gene expression network: it demonstrates marked improvement in accuracy without performance degradation, particularly when compared to known state-space truncation techniques.
7 schema:editor N407f31436e5b4dbaa096211c7ec46196
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3d2e26ce8afc4c1c8ed0f23ab12dd695
12 schema:keywords Markov chain
13 Markov model
14 accuracy
15 adaptive aggregation
16 advantages
17 aggregation
18 aggregation method
19 aggregation techniques
20 analysis
21 approach
22 approximate state aggregation methods
23 approximation error
24 bounds
25 chain
26 chemical reaction networks
27 conjunction
28 degradation
29 different measures
30 error
31 evaluation
32 explicit bounds
33 expression networks
34 gene expression networks
35 guarantees
36 improvement
37 key advantage
38 level of accuracy
39 levels
40 measures
41 method
42 model
43 network
44 new approach
45 novel numerical approach
46 numerical approach
47 numerical method
48 numerical scheme
49 numerical techniques
50 pathway
51 performance degradation
52 precision guarantees
53 problem
54 prokaryotic gene expression network
55 quantitative analysis
56 reaction networks
57 results
58 rigorous precision guarantees
59 scalability
60 scheme
61 simulation-based approach
62 simulation-based evaluation
63 soundness
64 space
65 state aggregation method
66 state space
67 state-space truncation techniques
68 strength
69 technique
70 time uniformisation techniques
71 truncation technique
72 uniformisation techniques
73 verification results
74 schema:name Adaptive Aggregation of Markov Chains: Quantitative Analysis of Chemical Reaction Networks
75 schema:pagination 195-213
76 schema:productId N3eccc0d1cc994283af621f87170abb05
77 N9a9fd3ad30574cc7b847ebe0e9777014
78 schema:publisher Nbb17b65c02c44210ac703fb533016f41
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044474057
80 https://doi.org/10.1007/978-3-319-21690-4_12
81 schema:sdDatePublished 2021-11-01T18:45
82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
83 schema:sdPublisher N58daca90b963458db5e8e38a91ae338f
84 schema:url https://doi.org/10.1007/978-3-319-21690-4_12
85 sgo:license sg:explorer/license/
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N004db5fba3bc4394800a36fc0bc4811a rdf:first sg:person.0645117057.83
89 rdf:rest Nd5e47fce49dc4aacafe89145fbac0019
90 N059619ba1e824bc3925366ea9f743782 schema:familyName Păsăreanu
91 schema:givenName Corina S.
92 rdf:type schema:Person
93 N0c3950a9409546f7a427e3841a0af03b schema:familyName Kroening
94 schema:givenName Daniel
95 rdf:type schema:Person
96 N332845c436344c3abb4181984492c3c3 rdf:first sg:person.012500146711.49
97 rdf:rest N004db5fba3bc4394800a36fc0bc4811a
98 N362ecb8364974f79a43d20044ed56ffd rdf:first N059619ba1e824bc3925366ea9f743782
99 rdf:rest rdf:nil
100 N3d2e26ce8afc4c1c8ed0f23ab12dd695 schema:isbn 978-3-319-21689-8
101 978-3-319-21690-4
102 schema:name Computer Aided Verification
103 rdf:type schema:Book
104 N3eccc0d1cc994283af621f87170abb05 schema:name dimensions_id
105 schema:value pub.1044474057
106 rdf:type schema:PropertyValue
107 N407f31436e5b4dbaa096211c7ec46196 rdf:first N0c3950a9409546f7a427e3841a0af03b
108 rdf:rest N362ecb8364974f79a43d20044ed56ffd
109 N58daca90b963458db5e8e38a91ae338f schema:name Springer Nature - SN SciGraph project
110 rdf:type schema:Organization
111 N9a9fd3ad30574cc7b847ebe0e9777014 schema:name doi
112 schema:value 10.1007/978-3-319-21690-4_12
113 rdf:type schema:PropertyValue
114 Nbb17b65c02c44210ac703fb533016f41 schema:name Springer Nature
115 rdf:type schema:Organisation
116 Nd5e47fce49dc4aacafe89145fbac0019 rdf:first sg:person.016652663056.36
117 rdf:rest Nfcf053fa51554711bb68b5b6bf675722
118 Nfcf053fa51554711bb68b5b6bf675722 rdf:first sg:person.011375012273.39
119 rdf:rest rdf:nil
120 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
121 schema:name Information and Computing Sciences
122 rdf:type schema:DefinedTerm
123 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
124 schema:name Artificial Intelligence and Image Processing
125 rdf:type schema:DefinedTerm
126 sg:person.011375012273.39 schema:affiliation grid-institutes:grid.4991.5
127 schema:familyName Kwiatkowska
128 schema:givenName Marta
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39
130 rdf:type schema:Person
131 sg:person.012500146711.49 schema:affiliation grid-institutes:grid.4991.5
132 schema:familyName Abate
133 schema:givenName Alessandro
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012500146711.49
135 rdf:type schema:Person
136 sg:person.016652663056.36 schema:affiliation grid-institutes:grid.10267.32
137 schema:familyName Češka
138 schema:givenName Milan
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016652663056.36
140 rdf:type schema:Person
141 sg:person.0645117057.83 schema:affiliation grid-institutes:grid.10267.32
142 schema:familyName Brim
143 schema:givenName Luboš
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83
145 rdf:type schema:Person
146 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Brno, Czech Republic
147 schema:name Department of Computer Science, University of Oxford, Oxford, UK
148 Faculty of Informatics, Masaryk University, Brno, Czech Republic
149 rdf:type schema:Organization
150 grid-institutes:grid.4991.5 schema:alternateName Department of Computer Science, University of Oxford, Oxford, UK
151 schema:name Department of Computer Science, University of Oxford, Oxford, UK
152 rdf:type schema:Organization
 




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


...