A computational approach to the structural analysis of uncertain kinetic systems. (English) Zbl 1498.92346

Summary: A computation-oriented representation of uncertain kinetic systems is introduced and analysed in this paper. It is assumed that the monomial coefficients of the ODEs belong to a polytopic set, which defines a set of dynamical systems for an uncertain model. An optimization-based computation model is proposed for the structural analysis of uncertain models. It is shown that the so-called dense realization containing the maximal number of reactions (directed edges) is computable in polynomial time, and it forms a superstructure among all the possible reaction graphs corresponding to an uncertain kinetic model, assuming a fixed set of complexes. The set of core reactions present in all reaction graphs of an uncertain model is also studied. Most importantly, an algorithm is proposed to compute all possible reaction graph structures for an uncertain kinetic model.


92E20 Classical flows, reactions, etc. in chemistry
34B45 Boundary value problems on graphs and networks for ordinary differential equations
Full Text: DOI arXiv


[1] Érdi, P.; Tóth, J., Mathematical Models of Chemical Reactions. Theory and Applications of Deterministic and Stochastic Models (1989), Manchester University Press, Princeton University Press: Manchester University Press, Princeton University Press Manchester, Princeton · Zbl 0696.92027
[2] Haddad, W. M.; Chellaboina, V. S.; Hui, Q., Nonnegative and Compartmental Dynamical Systems (2010), Princeton University Press · Zbl 1184.93001
[3] Chellaboina, V.; Bhat, S. P.; Haddad, W. M.; Bernstein, D. S., Modeling and analysis of mass-action kinetics – nonnegativity, realizability, reducibility, and semistability, IEEE Control Syst. Mag., 29, 60-78 (2009) · Zbl 1395.93098
[4] Takeuchi, Y., Global Dynamical Properties of Lotka-Volterra Systems (1996), World Scientific: World Scientific Singapore · Zbl 0844.34006
[5] Chen, W. W.; Niepel, M.; Sorger, P. K., Classic and contemporary approaches to modeling biochemical reactions, Geners Dev., 24, 1861-1875 (2012)
[6] Szederkényi, G.; Banga, J. R.; Alonso, A. A., Inference of complex biological networks: Distinguishability issues and optimization-based solutions, BMC Syst. Biol., 5, 177 (2011)
[7] Chis, O. T.; Villaverde, A. F.; Banga, J. R.; Balsa-Canto, E., On the relationship between sloppiness and identifiability, Math. Biosci., 282, 147-161 (2016) · Zbl 1352.92059
[8] Chis, O. T.; Banga, J. R.; Balsa-Canto, E., Structural identifiability of systems biology models: A critical comparison of methods, PLoS One, 6, 11, e27755 (2011)
[9] Feinberg, M., Chemical reaction network structure and the stability of complex isothermal reactors -I. The deficiency zero and deficiency one theorems, Chem. Eng. Sci., 42, 10, 2229-2268 (1987)
[10] Sontag, E., Structure and stability of certain chemical networks and applications to the kinetic proofreading model of T-cell receptor signal transduction, IEEE Trans. Automat. Control, 46, 1028-1047 (2001) · Zbl 1049.92020
[11] Shinar, G.; Feinberg, M., Structural sources of robustness in biochemical reaction networks, Science, 327, 1389-1391 (2010)
[12] Anderson, D. F., A proof of the global attractor conjecture in the single linkage class case, SIAM J. Appl. Math., 71, 1487-1508 (2011) · Zbl 1227.92013
[14] Briggs, W., Uncertainty: The Soul of Modeling, Probability & Statistics (2016), Springer · Zbl 1362.62007
[15] (Guy, T. V.; Karny, M.; Wolpert, D. H., Decision Making: Uncertainty, Imperfection, Deliberation and Scalability (2015), Springer) · Zbl 1309.91007
[16] Harrison, G. W., Compartmental models with uncertain flow rates, Math. Biosci., 43, 131-139 (1979) · Zbl 0397.92004
[17] Liebermeister, W.; Klipp, E., Biochemical networks with uncertain parameters, IEE Proc. Syst. Biol., 152, 97-107 (2005)
[18] Nagy, T.; Turányi, T., Uncertainty of Arrhenius parameters, Int. J. Chem. Kinet., 43, 359-378 (2011)
[19] Schillings, C.; Sunnaker, M.; Stelling, J.; Schwab, C., Efficient characterization of parametric uncertainty of complex biochemical networks, PLoS Comput. Biol., 11, 8, e1004457 (2015)
[20] Weinmann, A., Uncertain Models and Robust Control (1991), Springer-Verlag
[21] Boyd, S.; El-Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in Systems and Control Theory (1994), SIAM Books: SIAM Books Philadelphia, PA · Zbl 0816.93004
[22] Wu, J. -L., Robust stabilization for single-input polytopic nonlinear systems, IEEE Trans. Automat. Control (2006) · Zbl 1366.93592
[23] Llaneras, F.; Picó, J., An interval approach for dealing with flux distributions and elementary modes activity patterns, J. Theoret. Biol., 246, 290-308 (2007) · Zbl 1451.92150
[24] Lipták, G.; Szederkényi, G.; Hangos, K. M., Kinetic feedback design for polynomial systems, J. Process Control, 41, 56-66 (2016)
[25] Badri, V.; Yazdanpanah, M. J.; Tavazoei, M. S., On stability and trajectory boundedness of Lotka-Volterra systems with polytopic uncertainty, IEEE Trans. Automat. Control (2017), Pages available online. http://dx.doi.org/10.1109/TAC.2017.2663839 · Zbl 1390.93596
[26] Horn, F.; Jackson, R., General mass action kinetics, Arch. Ration. Mech. Anal., 47, 81-116 (1972)
[27] Schnell, S.; Chappell, M. J.; Evans, N. D.; Roussel, M. R., The mechanism distinguishability problem in biochemical kinetics: The single-enzyme, single-substrate reaction as a case study, Comptes Rendus Biol., 329, 51-61 (2006)
[28] Craciun, G.; Pantea, C., Identifiability of chemical reaction networks, J. Math. Chem., 44, 244-259 (2008) · Zbl 1145.92040
[29] Hárs, V.; Tóth, J., (Farkas, M.; Hatvani, L., Qualitative Theory of Differential Equations. Qualitative Theory of Differential Equations, Coll. Math. Soc. J. Bolyai, vol. 30 (1981), North-Holland: North-Holland Amsterdam), 363-379
[30] Johnston, M. D.; Siegel, D., Linear conjugacy of chemical reaction networks, J. Math. Chem., 49, 1263-1282 (2011) · Zbl 1303.92153
[31] Szederkényi, G., Computing sparse and dense realizations of reaction kinetic systems, J. Math. Chem., 47, 551-568 (2010) · Zbl 1198.92052
[32] Johnston, M. D.; Siegel, D.; Szederkényi, G., A linear programming approach to weak reversibility and linear conjugacy of chemical reaction networks, J. Math. Chem., 50, 274-288 (2012) · Zbl 1238.92077
[33] Szederkényi, G.; Hangos, K. M., Finding complex balanced and detailed balanced realizations of chemical reaction networks, J. Math. Chem., 49, 1163-1179 (2011) · Zbl 1218.80017
[34] Johnston, M. D.; Siegel, D.; Szederkényi, G., Computing weakly reversible linearly conjugate chemical reaction networks with minimal deficiency, Math. Biosci., 241, 88-98 (2013) · Zbl 1263.92058
[35] Lipták, G.; Szederkényi, G.; Hangos, K. M., Computing zero deficiency realizations of kinetic systems, Systems Control Lett., 81, 24-30 (2015) · Zbl 1330.93095
[36] Ács, B.; Szederkényi, G.; Tuza, Zs; Tuza, Z. A., Computing all possible graph structures describing linearly conjugate realizations of kinetic systems, Comput. Phys. Comm., 204, 11-20 (2016) · Zbl 1375.92081
[37] Ács, B.; Szederkényi, G.; Csercsik, D., A new efficient algorithm for determining all structurally different realizations of kinetic systems, MATCH Commun. Math. Comput. Chem., 77, 299-320 (2017)
[38] Walter, E.; Pronzato, L., On the identifiability and distinguishability of nonlinear parametric models, Math. Comput. Simulation, 42, 125-134 (1996) · Zbl 0862.62056
[39] Ljung, L.; Glad, T., On global identifiability of arbitrary model parametrizations, Automatica, 30, 265-276 (1994) · Zbl 0795.93026
[40] Walter, E.; Pronzato, L., Identification of Parametric Models (1997), Springer
[41] Ljung, L., System Identification - Theory for the User (1999), Prentice Hall
[42] Sedoglavic, A., Méthodes seminumŕiques en algèbre différentielle; applications à létude des propriétés structurelles de systèmes différentiels algébriques en automatique (Septembre 2001), École Polytechnique, (Docteur En Sciences)
[43] Sedoglavic, A., A probabilistic algorithm to test local algebraic observability in polynomial time, J. Symbolic Comput., 33, 735-755 (2002) · Zbl 1055.93011
[44] Villaverde, A. F.; Barreiro, A.; Papachristodoulou, A., Structural identifiability of dynamic systems biology models, PLoS Comput. Biol. (2016)
[45] Meshkat, N.; Eisenberg, M.; DiStefano, J. J., An algorithm for finding globally identifiable parameter combinations of nonlinear ode models using gröbner bases, Math. Biosci., 222, 2, 61-72 (2009) · Zbl 1179.93066
[46] Meshkat, N.; Kuo, Ch. E.; DiStefano III, J., On finding and using identifiable parameter combinations in nonlinear dynamic systems biology models and combos: A novel web implementation, PLoS One, 9, 10, e110261 (2014)
[47] Meshkat, N.; Sullivant, S., Identifiable reparametrizations of linear compartment models, J. Symbolic Comput., 63, 46-67 (2014) · Zbl 1302.93077
[50] Johnston, M. D.; Siegel, D.; Szederkényi, G., Dynamical equivalence and linear conjugacy of chemical reaction networks: New results and methods, MATCH Commun. Math. Comput. Chem., 68, 443-468 (2012) · Zbl 1289.92104
[51] Feinberg, M., (Lectures on Chemical Reaction Networks. Lectures on Chemical Reaction Networks, Notes of lectures given at the Mathematics Research Center (1979), University of Wisconsin)
[52] Ács, B.; Szederkényi, G.; Tuza, Z. A.; Tuza, Z., Computing linearly conjugate weakly reversible kinetic structures using optimization and graph theory, MATCH Commun. Math. Comput. Chem., 74, 481-504 (2015) · Zbl 1403.92353
[54] Szederkényi, G.; Hangos, K. M.; Péni, T., Maximal and minimal realizations of reaction kinetic systems: Computation and properties, MATCH Commun. Math. Comput. Chem., 65, 309-332 (2011)
[55] Shinar, G.; Rabinowitz, J. D.; Alon, U., Robustness in glyoxylate bypass regulation, PLoS Comput. Biol., 5, 3, e1000297 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.