Reachability analysis of discrete state reaction networks with conservation laws

2019. 02. 28. 12:00
Szlobodnyik Gergely, Szederkényi Gábor

In this talk a computational solution is presented for the reachability problem of discrete state chemical reaction networks (d-CRNs), namely whether there exists a valid state transition (reaction) sequence between a prescribed initial and a target state. Considering sub-and superconservative network structures, we characterize the reachable set of the d-CRN with well-defined simplexes. Upper bounds are also derived for the possible length of cycle-free state transition sequences. We show that the reachability and the related coverability problem in the case of sub-and superconservative d-CRNs can be decided in the form an integer programming feasibility problem of well-decoupled time complexity. The proposed computation model is also employed for determining feasible series of reactions between given (sets of) states. We also provide conditions upon which the reachability problem is equivalent to the existence of a non-negative integer solution of the corresponding state equation characterizing the possible state transitions. Our findings are illustrated on a discrete state compartmental epidemiological model obeying a conservation law.

[1] G. Szlobodnyik, G. Szederkény, M. Johnston, "Reachability analysis of subconservative discrete chemical reaction networks", MATCH Commun. Math. Comput. Chem., 81(3), pp. 705-736., 2019.
[2] T. G. Kurtz, "The Relationship between Stochastic and Deterministic Models for Chemical Reactions", The Journal of Chemical Physics, 57(7), pp. 2976-2978., 1972.
[3] M. D. Johnston, "A Computational Approach to Extinction Events in Chemical Reaction Networks with Discrete State Spaces", Mathematical Biosciences, 294., 2017., 130-142.
[4] A. J. Barvinok, "A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed", Math. Oper. Res., 19., pp. 769–779., 1994.

Az előadás nyelve akkor angol, ha van külföldi résztvevő.

Az előadás a Formális reakciókinetikai szeminárium előadása.