×

Special algorithm for stability analysis of multistable biological regulatory systems. (English) Zbl 1328.92028

Summary: We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations.

MSC:

92C42 Systems biology, networks
34D20 Stability of solutions to ordinary differential equations
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Anai, H.; Weispfenning, V., Reach set computations using real quantifier elimination, (2001), Springer Berlin, Heidelberg · Zbl 0985.68755
[2] Anai, H.; Yanami, H., Synrac: a Maple-package for solving real algebraic constraints, (Computational Science—ICCS, (2003), Springer Berlin, Heidelberg), 828-837 · Zbl 1033.68960
[3] Arnon, D. S.; Collins, G. E.; McCallum, S., An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space, J. Symb. Comput., 5, 1, 163-187, (1988) · Zbl 0648.68055
[4] Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43, 6, 1002-1045, (1996) · Zbl 0885.68070
[5] Basu, S.; Pollack, R.; Roy, M.-F., Computing roadmaps of semi-algebraic sets on a variety, J. Am. Math. Soc., 3, 1, 55-82, (1999) · Zbl 0933.14037
[6] Basu, S.; Pollack, R.; Roy, M.-F., Algorithms in real algebraic geometry, (2006), Springer-Verlag
[7] Bradford, R.; Davenport, J. H.; England, M.; McCallum, S.; Wilson, D., Cylindrical algebraic decompositions for Boolean combinations, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (2013), ACM), 125-132 · Zbl 1359.68327
[8] Brown, C. W., Improved projection for cylindrical algebraic decomposition, J. Symb. Comput., 32, 5, 447-465, (2001) · Zbl 0981.68186
[9] Brown, C. W., Simple CAD construction and its applications, J. Symb. Comput., 31, 5, 521-547, (2001) · Zbl 0976.65023
[10] Brown, C. W., QEPCAD B: a program for computing with semi-algebraic sets using cads, ACM SIGSAM Bull., 37, 4, 97-108, (2003) · Zbl 1083.68148
[11] Brown, C. W., Fast simplifications for Tarski formulas based on monomial inequalities, J. Symb. Comput., 47, 7, 859-882, (2012) · Zbl 1262.68189
[12] Brown, C. W., Constructing a single open cell in a cylindrical algebraic decomposition, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (2013), ACM), 133-140 · Zbl 1360.68924
[13] Brown, C. W.; McCallum, S., On using bi-equational constraints in CAD construction, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (2005), ACM), 76-83 · Zbl 1360.68925
[14] Brown, C. W.; Novotni, D.; Weber, A., Algorithmic methods for investigating equilibrium in epidemic modeling, J. Symb. Comput., 41, 11, 1157-1173, (2006) · Zbl 1120.92034
[15] Chen, C.; Davenport, J. H.; May, J. P.; Moreno Maza, M.; Xia, B.; Xiao, R., Triangular decomposition of semi-algebraic systems, J. Symb. Comput., 49, 3-26, (2013) · Zbl 1260.14070
[16] Cinquin, O.; Demongeot, J., Positive and negative feedback: striking a balance between necessary antagonists, J. Theor. Biol., 216, 2, 229-241, (2002)
[17] Cinquin, O.; Demongeot, J., High-dimensional switches and the modelling of cellular differentiation, J. Theor. Biol., 233, 3, 391-411, (2005)
[18] Cinquin, O.; Page, K. M., Generalized: switch-like competitive heterodimerization networks, Bull. Math. Biol., 69, 2, 483-494, (2007) · Zbl 1139.92303
[19] Collins, G. E., Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, (Lect. Notes Comput. Sci., vol. 33, (1975), Springer-Verlag Berlin), 134-183
[20] Collins, G. E.; Hong, H., Cylindrical algebraic decomposition for quantifier elimination, J. Symb. Comput., 12, 3, 299-328, (1991) · Zbl 0754.68063
[21] Davenport, J. H.; Heintz, J., Real quantifier elimination is doubly exponential, J. Symb. Comput., 5, 1, 29-35, (1988) · Zbl 0663.03015
[22] Dolzmann, A.; Seidl, A.; Sturm, T., Efficient projection orders for CAD, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (2004), ACM), 111-118 · Zbl 1134.68575
[23] Dolzmann, A.; Sturm, T., Redlog: computer algebra meets computer logic, ACM SIGSAM Bull., 31, 2, 2-9, (1997)
[24] Dorato, P.; Yang, W.; Abdallah, C., Robust multi-objective feedback design by quantifier elimination, J. Symb. Comput., 24, 2, 153-159, (1997) · Zbl 0938.93534
[25] González-Vega, L., Applying quantifier elimination to the Birkhoff interpolation problem, J. Symb. Comput., 22, 1, 83-103, (1996) · Zbl 0870.65007
[26] Grigoriev, D., Complexity of deciding Tarski algebra, J. Symb. Comput., 5, 1-2, 65-108, (1988) · Zbl 0689.03021
[27] Größlinger, A.; Griebl, M.; Lengauer, C., Quantifier elimination in automatic loop parallelization, J. Symb. Comput., 41, 11, 1206-1221, (2006) · Zbl 1124.68035
[28] Hong, H., An improvement of the projection operator in cylindrical algebraic decomposition, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (1990), ACM), 261-264
[29] Hong, H., Improvements in CAD-based quantifier elimination, (1990), The Ohio State University, PhD thesis
[30] Hong, H., Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (1992), ACM), 177-188 · Zbl 0919.03029
[31] Hong, H.; Liska, R.; Steinberg, S., Testing stability by quantifier elimination, J. Symb. Comput., 24, 2, 161-187, (1997) · Zbl 0886.65087
[32] Hong, H.; Liska, R.; Steinberg, S., Logic, quantifiers, computer algebra and stability, SIAM News, 30, 6, 10, (1997)
[33] Hong, H.; Safey El Din, M., Variant quantifier elimination, J. Symb. Comput., 47, 7, 883-901, (2012) · Zbl 1238.14001
[34] Jirstrand, M., Nonlinear control system design by quantifier elimination, J. Symb. Comput., 24, 2, 137-152, (1997) · Zbl 0882.93022
[35] Lazard, D., Quantifier elimination: optimal solution for two classical examples, J. Symb. Comput., 5, 1, 261-266, (1988) · Zbl 0647.03023
[36] Liska, R.; Steinberg, S., Applying quantifier elimination to stability analysis of difference schemes, Comput. J., 36, 5, 497-503, (1993) · Zbl 0780.68075
[37] McCallum, S., An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, J. Symb. Comput., 5, 1, 141-161, (1988) · Zbl 0648.68054
[38] McCallum, S., On projection in CAD-based quantifier elimination with equational constraints, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (1999), ACM), 145-149
[39] McCallum, S., On propagation of equational constraints in CAD-based quantifier elimination, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (2001), ACM), 223-230 · Zbl 1356.68287
[40] Niu, W., Qualitative analysis of biological systems using algebraic methods, (2012), Université Pierre et Marie Curie, PhD thesis
[41] Niu, W.; Wang, D., Algebraic approaches to stability analysis of biological systems, Math. Comput. Sci., 1, 3, 507-539, (2008) · Zbl 1138.68668
[42] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. part I: introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals, J. Symb. Comput., 13, 3, 255-299, (1992) · Zbl 0763.68042
[43] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. part II: the general decision problem. preliminaries for quantifier elimination, J. Symb. Comput., 13, 3, 301-327, (1992) · Zbl 0763.68043
[44] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. part III: quantifier elimination, J. Symb. Comput., 13, 3, 329-352, (1992) · Zbl 0798.68073
[45] She, Z.; Li, H.; Xue, B.; Zheng, Z.; Xia, B., Discovering polynomial Lyapunov functions for continuous dynamical systems, J. Symb. Comput., 58, 41-63, (2013) · Zbl 1338.37025
[46] She, Z.; Xia, B.; Xiao, R.; Zheng, Z., A semi-algebraic approach for asymptotic stability analysis, Nonlinear Anal. Hybrid Syst., 3, 4, 588-596, (2009) · Zbl 1217.93153
[47] Strzeboński, A. W., Solving algebraic inequalities, Math. J., 7, 4, 525-541, (2000)
[48] Strzeboński, A. W., Applications of algorithms for solving equations and inequalities in Mathematica, (Algorithmic Algebra and Logic, (2005)), 243-247
[49] Strzeboński, A. W., Cylindrical algebraic decomposition using validated numeratorics, J. Symb. Comput., 41, 9, 1021-1038, (2006) · Zbl 1124.68123
[50] Strzeboński, A. W., Cylindrical decomposition for systems transcendental in the first variable, J. Symb. Comput., 46, 11, 1284-1290, (2011) · Zbl 1236.14053
[51] Sturm, T.; Weber, A.; Abdel-Rahman, E. O.; Kahoui, M. E., Investigating algebraic and logical algorithms to solve Hopf bifurcation problems in algebraic biology, Math. Comput. Sci., 2, 3, 493-515, (2009) · Zbl 1205.37062
[52] Tarski, A., A decision method for elementary algebra and geometry, (1951), University of California Press · Zbl 0044.25102
[53] Wang, D.; Xia, B., Stability analysis of biological systems with real solution classification, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, (2005), ACM), 354-361 · Zbl 1360.92048
[54] Wang, D.; Xia, B., Algebraic analysis of stability for some biological systems, (Proceedings of the First International Conference on Algebraic Biology, (2005), Universal Academy Press), 75-83
[55] Weispfenning, V., Simulation and optimization by quantifier elimination, J. Symb. Comput., 24, 2, 189-208, (1997) · Zbl 0883.68075
[56] Xia, B., DISCOVERER: a tool for solving semi-algebraic systems, ACM Commun. Comput. Algebra, 41, 3, 102-103, (2007)
[57] Xia, B.; Yang, L.; Zhan, N., Program verification by reduction to semi-algebraic systems solving. leveraging applications of formal methods, Verif. Commun. Comput. Inform. Sci., 17, 277-291, (2008)
[58] Yang, L.; Hou, X.; Xia, B., A complete algorithm for automated discovering of a class of inequality-type theorems, Sci. China, Ser. F: Inform. Sci., 44, 6, 33-49, (2001) · Zbl 1125.68406
[59] Yang, L.; Xia, B., Automated proving and discovering inequalities, (2008), Science Press Beijing, (in Chinese)
[60] Ying, J. Q.; Xu, L.; Lin, Z., A computational method for determining strong stabilizability of n-D systems, J. Symb. Comput., 27, 5, 479-499, (1999) · Zbl 0936.93045
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.