Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws
In this paper we study the reachability problem of sub- and superconservative discrete state chemical reaction networks (d-CRNs). It is known that a subconservative network has bounded reachable state space, while that of a superconservative one is unbounded. The reachability problem of superconserv...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/1035974 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832563961694781440 |
|---|---|
| author | Gergely Szlobodnyik Gábor Szederkényi |
| author_facet | Gergely Szlobodnyik Gábor Szederkényi |
| author_sort | Gergely Szlobodnyik |
| collection | DOAJ |
| description | In this paper we study the reachability problem of sub- and superconservative discrete state chemical reaction networks (d-CRNs). It is known that a subconservative network has bounded reachable state space, while that of a superconservative one is unbounded. The reachability problem of superconservative reaction networks is traced back to the reachability of subconservative ones. We consider network structures composed of reactions having at most one input and one output species beyond the possible catalyzers. We give a proof that, assuming all the reactions are charged in the initial and target states, the reachability problems of sub- and superconservative reaction networks are equivalent to the existence of nonnegative integer solution of the corresponding d-CRN state equations. Using this result, the reachability problem is reformulated as an Integer Linear Programming (ILP) feasibility problem. Therefore, the number of feasible trajectories satisfying the reachability relation can be counted in polynomial time in the number of species and in the distance of initial and target states, assuming fixed number of reactions in the system. |
| format | Article |
| id | doaj-art-15f967b0f243441682cc34b8520edd99 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-15f967b0f243441682cc34b8520edd992025-02-03T01:12:09ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/10359741035974Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation LawsGergely Szlobodnyik0Gábor Szederkényi1Faculty of Information Technology and Bionics, Pázmány Péter Catholic University, Práter u. 50/a, H-1083 Budapest, HungaryFaculty of Information Technology and Bionics, Pázmány Péter Catholic University, Práter u. 50/a, H-1083 Budapest, HungaryIn this paper we study the reachability problem of sub- and superconservative discrete state chemical reaction networks (d-CRNs). It is known that a subconservative network has bounded reachable state space, while that of a superconservative one is unbounded. The reachability problem of superconservative reaction networks is traced back to the reachability of subconservative ones. We consider network structures composed of reactions having at most one input and one output species beyond the possible catalyzers. We give a proof that, assuming all the reactions are charged in the initial and target states, the reachability problems of sub- and superconservative reaction networks are equivalent to the existence of nonnegative integer solution of the corresponding d-CRN state equations. Using this result, the reachability problem is reformulated as an Integer Linear Programming (ILP) feasibility problem. Therefore, the number of feasible trajectories satisfying the reachability relation can be counted in polynomial time in the number of species and in the distance of initial and target states, assuming fixed number of reactions in the system.http://dx.doi.org/10.1155/2019/1035974 |
| spellingShingle | Gergely Szlobodnyik Gábor Szederkényi Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws Complexity |
| title | Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws |
| title_full | Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws |
| title_fullStr | Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws |
| title_full_unstemmed | Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws |
| title_short | Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws |
| title_sort | reachability analysis of low order discrete state reaction networks obeying conservation laws |
| url | http://dx.doi.org/10.1155/2019/1035974 |
| work_keys_str_mv | AT gergelyszlobodnyik reachabilityanalysisofloworderdiscretestatereactionnetworksobeyingconservationlaws AT gaborszederkenyi reachabilityanalysisofloworderdiscretestatereactionnetworksobeyingconservationlaws |