A constraint solving approach to model reduction by tropical equilibration

Algorithms for Molecular Biology

Sylvain Soliman¹  François Fages¹  Ovidiu Radulescu² 

[1] Inria, Domaine de Voluceau, Rocquencourt 78150, France

[2] University of Montpellier 2, Place Eugene Bataillon, Montpellier 34095, France

关键词: Constraint programming;    Tropical equilibration;    Tropical algebra;    Model reduction;    Systems biology;   

Others  :  1083782
DOI  :  10.1186/s13015-014-0024-2

 received in 2014-04-04, accepted in 2014-11-04,  发布年份 2014

【 摘 要 】

Model reduction is a central topic in systems biology and dynamical systems theory, for reducing the complexity of detailed models, finding important parameters, and developing multi-scale models for instance. While singular perturbation theory is a standard mathematical tool to analyze the different time scales of a dynamical system and decompose the system accordingly, tropical methods provide a simple algebraic framework to perform these analyses systematically in polynomial systems. The crux of these methods is in the computation of tropical equilibrations. In this paper we show that constraint-based methods, using reified constraints for expressing the equilibration conditions, make it possible to numerically solve non-linear tropical equilibration problems, out of reach of standard computation methods. We illustrate this approach first with the detailed reduction of a simple biochemical mechanism, the Michaelis-Menten enzymatic reaction model, and second, with large-scale performance figures obtained on the http://biomodels.net webcite repository.

【 授权许可】

   
2014 Soliman et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

【 参考文献 】

• [1]Grigoriev D, Vorobjov N: Solving systems of polynomial inequalities in subexponential time. J Symbolic Computat 1988, 5:37-64.
• [2]Grigoriev D: Complexity of quantifier elimination in the theory of ordinary differential equations. Lect Notes Comput Sci 1989, 18:11-25.
• [3]Pantea C, Gupta A, Rawlings JB, Craciun G: The QSSA in chemical kinetics: as taught and as practiced. In Discrete and Topological Models in Molecular Biology. Berlin: Springer; 2014:419–442.
• [4]Gorban A, Karlin I: Invariant manifolds for physical and chemical kinetics. Lect Notes Phys 2005, 660:1-491.
• [5]Lam S, Goussis D: The CSP method for simplifying kinetics. Int J Chem Kinet 1994, 26(4):461-486.
• [6]Maas U, Pope SB: Simplifying chemical kinetics: intrinsic low-dimensional manifolds in composition space. Combustion Flame 1992, 88(3):239-264.
• [7]Gay S, Soliman S, Fages F: A graphical method for reducing and relating models in systems biology. Bioinformatics 2010, 26(18):i575-i581. [Special issue ECCB’10]
• [8]Radulescu O, Gorban AN, Zinovyev A, Noel V: Reduction of dynamical biochemical reactions networks in computational biology. Front Genet 2012, 3:131. [http://www.frontiersin.org/bioinformatics_and_computational_biology/10.3389/fgene.2012.00131/abstract]
• [9]Sturmfels B: Solving systems of polynomial equations, Volume 97, American Mathematical Soc: Providence; 2002.
• [10]Walker RJ: Algebraic curves, New York: Springer; 1978.
• [11]Einsiedler M, Kapranov M, Lind D: Non-archimedean amoebas and tropical varieties. J für die reine und angewandte Mathematik (Crelles J) 2006, 2006(601):139-157.
• [12]Noel V, Grigoriev D, Vakulenko S, Radulescu O: Tropical geometries and dynamics of biochemical networks application to hybrid cell cycle models. Electron Notes Theor Comput Sci 2012, 284:75-91.
• [13]Noel V, Grigoriev D, Vakulenko S, Radulescu O: Tropicalization and tropical equilibration of chemical reactions. In Tropical and Idempotent Mathematics and Applications, Volume 616 of Contemporary Mathematics. Edited by Litvinov G, Sergeev S: American Mathematical Society; 2014:261–277.
• [14]Grigoriev D: Complexity of solving tropical linear systems. Comput Complexity 2013, 22:71-88.
• [15]Theobald T: On the frontiers of polynomial computations in tropical geometry. J Symbolic Comput 2006, 41(12):1360-1375.
• [16]le Novère N, Bornstein B, Broicher A, Courtot M, Donizelli M, Dharuri H, Li L, Sauro H, Schilstra M, Shapiro B, Snoep JL, Hucka M: BioModels Database: a free, centralized database of curated, published, quantitative kinetic models of biochemical and cellular systems. Nucleic Acid Res 2006, 1(34):D689-D691.
• [17]Cohen G, Gaubert S, Quadrat J: Max-plus algebra and system theory: where we are and where to go now. Ann Rev Control 1999, 23:207-219.
• [18]Viro O: From the sixteenth Hilbert problem to tropical geometry. Jpn J Math 2008, 3(2):185-214.
• [19]Gorban AN, Radulescu O, Zinovyev AY: Asymptotology of chemical reaction networks. Chem Eng Sci 2010, 65(7):2310-2324. [International Symposium on Mathematics in Chemical Kinetics and Engineering]
• [20]Mackworth AK: Consistency in networks of relations. Artif Intell 1977, 8:99-118.
• [21]Meseguer P: Constraint satisfaction problems: an overview. A.I. Commun 1989, 2:3-17.
• [22]Kumar V: Algorithms for constraint- satisfaction problems: a survey. A.I. Mag 1992, 13:32-44.
• [23]Soliman S: Invariants and other structural properties of biochemical models as a constraint satisfaction problem. Algorithms Mol Biol 2012, 7(15):15. BioMed Central Full Text
• [24]Wielemaker J, Schrijvers T, Triska M, Lager T: SWI-Prolog. Theory Prac Logic Program 2012, 12(1-2):67-96.
• [25][http://www.swi-prolog.org/pldoc/refman/] webcite Wielemaker J: SWI-Prolog 6.3.15 Reference Manual; 1990. []
• [26]Radulescu O, Gorban A, Zinovyev A, Noel V: Reduction of dynamical biochemical reaction networks in computational biology. Front Bioinformatics Comput Biol 2012, 3:131.
• [27]Beldiceanu N, Carlsson M, Demassey S, Petit T: Global constraints catalog. Tech. Rep. T2005-6, Swedish Institute of Computer Science 2005.
• [28]Freuder EC, Wallace RJ: Partial constraint satisfaction. Artif Intell 1992, 58:21-70.