Syntactic Markovian Bisimulation for Chemical Reaction Networks

Luca Cardelli, Mirco Tribastone, Max Tschaikowski, Andrea Vandin

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

Abstract

In chemical reaction networks (CRNs) with stochastic semantics based on continuous-time Markov chains (CTMCs), the typically large populations of species cause combinatorially large state spaces. This makes the analysis very difficult in practice and represents the major bottleneck for the applicability of minimization techniques based, for instance, on lumpability. In this paper we present syntactic Markovian bisimulation (SMB), a notion of bisimulation developed in the Larsen-Skou style of probabilistic bisimulation, defined over the structure of a CRN rather than over its underlying CTMC. SMB identifies a lumpable partition of the CTMC state space a priori, in the sense that it is an equivalence relation over species implying that two CTMC states are lumpable when they are invariant with respect to the total population of species within the same equivalence class. We develop an efficient partition-refinement algorithm which computes the largest SMB of a CRN in polynomial time in the number of species and reactions. We also provide an algorithm for obtaining a quotient network from an SMB that induces the lumped CTMC directly, thus avoiding the generation of the state space of the original CRN altogether. In practice, we show that SMB allows significant reductions in a number of models from the literature. Finally, we study SMB with respect to the deterministic semantics of CRNs based on ordinary differential equations (ODEs), where each equation gives the time-course evolution of the concentration of a species. SMB implies forward CRN bisimulation, a recently developed behavioral notion of equivalence for the ODE semantics, in an analogous sense: it yields a smaller ODE system that keeps track of the sums of the solutions for equivalent species.
Original languageEnglish
Title of host publicationModels, Algorithms, Logics and Tools - Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday
Number of pages18
PublisherSpringer
Publication date2017
Pages466-483
ISBN (Print)978-3-319-63120-2
DOIs
Publication statusPublished - 2017
Externally publishedYes
SeriesLecture Notes in Computer Science
Volume10460
ISSN0302-9743

Fingerprint Dive into the research topics of 'Syntactic Markovian Bisimulation for Chemical Reaction Networks'. Together they form a unique fingerprint.

Cite this