Complexity of fixed point counting problems in Boolean networks. (English) Zbl 1483.68240
Summary: A Boolean network (BN) with \(n\) components is a discrete dynamical system described by the successive iterations of a function \(f : \{ 0,1\}^n \to \{ 0,1\}^n\). This model finds applications in biology, where fixed points play a central role. For example, in genetic regulations, they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components. The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to a large number of BNs. The present work opens a new perspective on the well-established study of fixed points in BNs. When biologists discover the SID of a BN they do not know, they may ask: given that SID, can it correspond to a BN having at least/at most \(k\) fixed points? Depending on the input, we prove that these problems are in \(\mathsf{P}\) or complete for \(\mathsf{NP}\), \(\mathsf{NP}^{\mathsf{NP}}\), \(\mathsf{NP}^{\#\mathsf{P}}\) or \(\mathsf{NEXPTIME}\).
MSC:
| 68R05 | Combinatorics in computer science |
| 37B10 | Symbolic dynamics |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
Software:
OEISOnline Encyclopedia of Integer Sequences:
Number of hierarchical models on n labeled factors or variables with linear terms forced. Also number of antichain covers of a labeled n-set.References:
| [1] | The online encyclopedia of integer sequences, founded in 1964 by N. J. A. Sloane. Sequence A006126 |
| [2] | Akmal, S.; Williams, R. R., MAJORITY-3SAT (and related problems) in polynomial time (2021), CoRR |
| [3] | Albert, R., Boolean modeling of genetic regulatory networks, (Complex Networks. Complex Networks, Lecture Notes in Physics, vol. 650 (2004)), 459-481 · Zbl 1079.92029 |
| [4] | Alon, N., Asynchronous threshold networks, Graphs Comb., 1, 1, 305-310 (1985) · Zbl 0619.05024 |
| [5] | Aracena, J., Maximum number of fixed points in regulatory Boolean networks, Bull. Math. Biol., 70, 5, 1398-1409 (2008) · Zbl 1144.92323 |
| [6] | Aracena, J.; Demongeot, J.; Goles, E., Fixed points and maximal independent sets in AND-OR networks, Discrete Appl. Math., 138, 1, 277-288 (2004) · Zbl 1076.68047 |
| [7] | Aracena, J.; Demongeot, J.; Goles, E., Fixed points and maximal independent sets in and-or networks, Discrete Appl. Math., 138, 3, 277-288 (2004) · Zbl 1076.68047 |
| [8] | Aracena, J.; Goles, E.; Moreira, A.; Salinas, L., On the robustness of update schedules in Boolean networks, Biosystems, 97, 1, 1-8 (2009) |
| [9] | Aracena, J.; Richard, A.; Salinas, L., Maximum number of fixed points in AND-OR-NOT networks, J. Comput. Syst. Sci., 80, 7, 1175-1190 (2014) · Zbl 1311.68100 |
| [10] | Aracena, J.; Richard, A.; Salinas, L., Number of fixed points and disjoint cycles in monotone Boolean networks, SIAM J. Discrete Math., 31, 3, 1702-1725 (2017) · Zbl 1368.05136 |
| [11] | Bridoux, F.; Durbec, N.; Perrot, K.; Richard, A., Complexity of maximum fixed point problem in Boolean networks, (Proceedings of CiE’2019. Proceedings of CiE’2019, LNCS, vol. 11558 (2019)), 132-143 · Zbl 1434.37013 |
| [12] | Bridoux, F.; Gaze-Maillot, C.; Perrot, K.; Sené, S., Complexity of limit-cycle problems in Boolean networks, (Proceedings of SOFSEM’2021. Proceedings of SOFSEM’2021, LNCS, vol. 12607 (2021)), 135-146 · Zbl 1490.68117 |
| [13] | Chatain, T.; Haar, S.; Kolčák, J.; Paulevé, L.; Thakkar, A., Concurrency in Boolean networks, Nat. Comput., 19, 1, 91-109 (2020) · Zbl 1530.68190 |
| [14] | DasGupta, B.; Enciso, G. A.; Sontag, E.; Zhang, Y., Algorithmic and complexity results for decompositions of biological networks into monotone subsystems, Biosystems, 90, 1, 161-178 (2007) |
| [15] | Demongeot, J.; Noual, M.; Sené, S., Combinatorics of Boolean automata circuits dynamics, Discrete Appl. Math., 160, 4-5, 398-415 (2012) · Zbl 1238.37035 |
| [16] | Feder, T., A new fixed point approach for stable networks and stable marriages, J. Comput. Syst. Sci., 45, 2, 233-284 (1992) · Zbl 0772.68052 |
| [17] | Floréen, P.; Orponen, P., Attraction radii in binary Hopfield nets are hard to compute, Neural Comput., 5, 5, 812-821 (1993) |
| [18] | Gadouleau, M.; Richard, A.; Fanchon, E., Reduction and fixed points of Boolean networks and linear network coding solvability, IEEE Trans. Inf. Theory, 62, 5, 2504-2519 (2016) · Zbl 1359.94949 |
| [19] | Gadouleau, M.; Richard, A.; Riis, S., Fixed points of Boolean networks, guessing graphs, and coding theory, SIAM J. Discrete Math., 29, 4, 2312-2335 (2015) · Zbl 1354.37047 |
| [20] | Gadouleau, M.; Riis, S., Graph-theoretical constructions for graph entropy and network coding based communications, IEEE Trans. Inf. Theory, 57, 10, 6703-6717 (2011) · Zbl 1365.94557 |
| [21] | Goles, E.; Servet, M., Neural and Automata Networks: Dynamical Behavior and Applications (1990), Kluwer Academic Publishers · Zbl 1103.37302 |
| [22] | Just, W.; Enciso, G., Extremely chaotic Boolean networks (2008) |
| [23] | Just, W.; Malicki, M., Cooperative Boolean systems with generically long attractors I, J. Differ. Equ. Appl., 19, 5, 772-795 (2013) · Zbl 1266.93006 |
| [24] | Just, W.; Malicki, M., Cooperative Boolean systems with generically long attractors II, Adv. Differ. Equ., 19, 1, 268-291 (2013) · Zbl 1375.94181 |
| [25] | Kauffman, S. A., Metabolic stability and epigenesis in randomly connected nets, J. Theor. Biol., 22, 437-467 (1969) |
| [26] | Kauffman, S. A., Origins of Order Self-Organization and Selection in Evolution (1993), Oxford University Press |
| [27] | Kaufman, M.; Soulé, C.; Thomas, R., A new necessary condition on interaction graphs for multistationarity, J. Theor. Biol., 248, 4, 675-685 (2007) · Zbl 1451.92146 |
| [28] | Kosub, S., Dichotomy results for fixed-point existence problems for Boolean dynamical systems, Math. Comput. Sci., 1, 3, 487-505 (2008) · Zbl 1138.68034 |
| [29] | Le Novère, N., Quantitative and logic modelling of molecular and gene networks, Nat. Rev. Genet., 16, 146-158 (2015) |
| [30] | Li, S.-Y.; Yeung, R.; Cai, N., Linear network coding, IEEE Trans. Inf. Theory, 49, 2, 371-381 (2003) · Zbl 1063.94004 |
| [31] | Littman, M. L.; Goldsmith, J.; Mundhenk, M., The computational complexity of probabilistic planning, J. Artif. Intell. Res., 9, 1-36 (1998) · Zbl 0903.68100 |
| [32] | McCuaig, W., Pólya’s permanent problem, Electron. J. Comb., 11, 1, 79 (2004) · Zbl 1062.05066 |
| [33] | Melliti, T.; Regnault, D.; Richard, A.; Sené, S., Asynchronous simulation of Boolean networks by monotone Boolean networks, (Proceedings of ACRI’18. Proceedings of ACRI’18, LNCS, vol. 9863 (2016)), 182-191 · Zbl 1391.37010 |
| [34] | Montalva, M.; Aracena, J.; Gajardo, A., On the complexity of feedback set problems in signed digraphs, Electron. Notes Discrete Math., 30, 249-254 (2008) · Zbl 1341.05112 |
| [35] | Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049 |
| [36] | Paulevé, L.; Richard, A., Topological fixed points in Boolean networks, C. R. Acad. Sci., Ser. 1 Math., 348, 15-16, 825-828 (2010) · Zbl 1194.94209 |
| [37] | Paulevé, L.; Sené, S., Non-deterministic updates of Boolean networks, (Proceedings of AUTOMATA’2021. Proceedings of AUTOMATA’2021, OASIcs, vol. 90 (2021)), Article 10 pp. |
| [38] | Paulevé, L.; Kolčák, J.; Chatain, T.; Haar, S., Reconciling qualitative, abstract, and scalable modeling of biological networks, Nat. Commun., 11, 4256 (2020) |
| [39] | Remy, E.; Ruet, P.; Thieffry, D., Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework, Adv. Appl. Math., 41, 3, 335-350 (2008) · Zbl 1169.05333 |
| [40] | Richard, A., An extension of a combinatorial fixed point theorem of Shih and Dong, Adv. Appl. Math., 41, 4, 620-627 (2008) · Zbl 1185.05027 |
| [41] | Richard, A., Fixed points and connections between positive and negative cycles in Boolean networks, Discrete Appl. Math. (2018) · Zbl 1387.05244 |
| [42] | Richard, A., Positive and negative cycles in Boolean networks, J. Theor. Biol., 463, 67-76 (2019) · Zbl 1406.92252 |
| [43] | Robert, F., Discrete Iterations: a Metric Study, Series in Computational Math., vol. 6 (1986), Springer · Zbl 0639.39005 |
| [44] | Robert, Y.; Tchuente, M., Connection-graph and iteration-graph of monotone Boolean functions, Discrete Appl. Math., 11, 3, 245-253 (1985) |
| [45] | Robertson, N.; Seymour, P.; Thomas, R., Permanents, Pfaffian orientations, and even directed circuits, Ann. Math., 150, 3, 929-975 (1999) · Zbl 0947.05066 |
| [46] | Soulé, C., Mathematical approaches to differentiation and gene regulation, C. R. Paris Biol., 329, 13-20 (2006) |
| [47] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107 |
| [48] | Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math., 5, 2, 285-309 (1955) · Zbl 0064.26004 |
| [49] | Thomas, R., Boolean formalization of genetic control circuits, J. Theor. Biol., 42, 3, 563-585 (1973) |
| [50] | Thomas, R.; d’Ari, R., Biological Feedback (1990), CRC Press · Zbl 0743.92003 |
| [51] | Thomas, R.; Kaufman, M., Multistationarity, the basis of cell differentiation and memory. II. Logical analysis of regulatory networks in terms of feedback circuits, Chaos Interdis. J. Nonlinear Sci., 11, 1, 180-195 (2001) · Zbl 0997.92012 |
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.
