×

Computing difference abstractions of linear equation systems. (English) Zbl 1518.92070

Summary: Abstract interpretation was proposed for predicting changes of reaction networks with partial kinetic information in systems biology. This requires to compute the set of difference abstractions of a system of linear equations under nonlinear constraints. We present the first practical algorithm that can compute the difference abstractions of linear equation systems exactly. We also present a new heuristics based on minimal support consequences for overapproximating the set of difference abstractions. Our algorithms rely on elementary modes, first-order definitions, and finite domain constraint programming. We implemented our algorithms and applied them to change prediction in systems biology. It turns out experimentally that the new heuristics is often exact in practice, while outperforming the exact algorithm.

MSC:

92C42 Systems biology, networks
92C40 Biochemistry, molecular biology
92C45 Kinetics in biochemical problems (pharmacokinetics, enzyme kinetics, etc.)
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Allart, Emilie; Niehren, Joachim; Versari, Cristian, Computing difference abstractions of metabolic networks under kinetic constraints, (Bortolussi, Luca; Sanguinetti, Guido, Computational Methods in Systems Biology - 17th International Conference. Computational Methods in Systems Biology - 17th International Conference, CMSB 2019, Trieste, Italy, September 18-20, 2019, Proceedings. Computational Methods in Systems Biology - 17th International Conference. Computational Methods in Systems Biology - 17th International Conference, CMSB 2019, Trieste, Italy, September 18-20, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11773 (2019), Springer), 266-285 · Zbl 1422.92064
[2] Orth, Jeffrey D.; Thiele, Ines; Palsson, Bernhard O., What is flux balance analysis?, Nat. Biotechnol., 28, 3, 245-248 (2010)
[3] Papin, Jason A.; Stelling, Joerg; Price, Nathan D.; Klamt, Steffen; Schuster, Stefan; Palsson, Bernhard O., Comparison of network-based pathway analysis methods, Trends Biotechnol., 22, 8, 400-405 (2004)
[4] Feinberg, Martin, Chemical reaction network structure and the stability of complex isothermal reactors, Chem. Eng. Sci., 42, 10, 2229-2268 (1987)
[5] Calzone, Laurence; Fages, Francois; Soliman, Sylvain, BIOCHAM: an environment for modeling biological systems and formalizing experimental knowledge, Bioinformatics, 22, 14, 1805-1807 (July 2006)
[6] Hoops, Stefan; Sahle, Sven; Gauges, Ralph; Lee, Christine; Pahle, Jürgen; Simus, Natalia; Singhal, Mudita; Xu, Liang; Mendes, Pedro; Kummer, Ursula, Copasi—a complex pathway simulator, Bioinformatics, 22, 24, 3067-3074 (2006)
[7] Fages, François; Gay, Steven; Soliman, Sylvain, Inferring reaction systems from ordinary differential equations, Theor. Comput. Sci., 599, 64-78 (2015) · Zbl 1337.92089
[8] Niehren, Joachim; Versari, Cristian; John, Mathias; Coutte, François; Jacques, Philippe, Predicting changes of reaction networks with partial kinetic information, Biosystems, 149, 113-124 (July 2016)
[9] Coutte, François; Niehren, Joachim; Dhali, Debarun; John, Mathias; Versari, Cristian; Jacques, Philippe, Modeling leucine’s metabolic pathway and knockout prediction improving the production of surfactin, a biosurfactant from Bacillus subtilis, Biotechnol. J., 10, 8, 1216-1234 (August 2015)
[10] John, Mathias; Nebut, Mirabelle; Niehren, Joachim, Knockout prediction for reaction networks with partial kinetic information, (14th International Conference on Verification, Model Checking, and Abstract Interpretation. 14th International Conference on Verification, Model Checking, and Abstract Interpretation, Rom, Italy (January 2013)) · Zbl 1435.92024
[11] Marriott, Kim; Stuckey, Peter J.; Wallace, Mark, Constraint logic programming, (Rossi, Francesca; van Beek, Peter; Walsh, Toby, Handbook of Constraint Programming. Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2 (2006), Elsevier), 409-452 · Zbl 1175.90011
[12] Nethercote, Nicholas; Stuckey, Peter J.; Becket, Ralph; Brand, Sebastian; Duck, Gregory J.; Minizinc, Guido Tack, Towards a standard CP modelling language, (Bessiere, Christian, Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007. Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings. Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007. Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4741 (2007), Springer), 529-543
[13] Gagneur, Julien; Klamt, Steffen, Computation of elementary modes: a unifying framework and the new binary approach, BMC Bioinform., 5, 1, 1 (2004)
[14] Zanghellini, Jürgen; Ruckerbauer, David E.; Hanscho, Michael; Jungreuthmayer, Christian, Elementary flux modes in a nutshell: properties, calculation and applications, Biotechnol. J., 1009-1016 (2013)
[15] Allart, Emilie; Niehren, Joachim; Versari, Cristian, Reaction Networks to Boolean Networks (May 2021), preprint
[16] Karmarkar, Narendra, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-396 (1984) · Zbl 0557.90065
[17] Lotz, K.; Hartmann, A.; Grafahrend-Belau, E.; Schreiber, B. H.; Junker, F., Elementary flux modes, flux balance analysis, and their application to plant metabolism, (Plant Metabolism. Plant Metabolism, Methods in Molecular Biology (2014)), (Methods and Protocols)
[18] Maranas, Costas D.; Zomorrodi, Ali R., Flux Balance Analysis and LP Problems, 53-80 (2016), Wiley-Blackwell, chapter 3
[19] Facchetti, Giuseppe; Altafini, Claudio, Partial inhibition and bilevel optimization in flux balance analysis, BMC Bioinform., 344 (2013)
[20] Cousot, Patrick; Cousot, Radhia, Systematic design of program analysis frameworks, (POPL (1979)), 269-282 · Zbl 0413.06004
[21] Fages, François; Soliman, Sylvain, Abstract interpretation and types for systems biology, Theor. Comput. Sci., 403, 1, 52-70 (2008) · Zbl 1155.68049
[22] Danos, Vincent; Feret, Jérôme; Fontana, Walter; Harmer, Russell; Krivine, Jean, Abstracting the differential semantics of rule-based models: exact and automated model reduction, (LICS (2010), IEEE Computer Society), 362-381
[23] Schuster, Stefan; Dandekar, Thomas; Fell, David A., Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering, Trends Biotechnol., 17, 2, 53-60 (1999)
[24] Forbus, Kenneth D., Qualitative reasoning, (Tucker, Allen B., The Computer Science and Engineering Handbook (1997), CRC Press), 715-733 · Zbl 0917.68001
[25] Avis, David, A revised implementation of the reverse search vertex enumeration algorithm, (Polytopes—Combinatorics and Computation (2000), Springer), 177-198 · Zbl 0960.68171
[26] Terzer, Marco; Stelling, Jörg, Large-scale computation of elementary flux modes with bit pattern trees, Bioinformatics, 24, 19, 2229-2235 (2008)
[27] Fukuda, Komei; Prodon, Alain, Double description method revisited, (Franco-Japanese and Franco-Chinese Conference on Combinatorics and Computer Science (1995), Springer), 91-111
[28] Troffaes, M., pycddlib-a python wrapper for komei fukudals cddlib (2018)
[29] BioComputing, Biocomputing’s network-graph tool, 2018-07-10
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.