Complexity of maximum fixed point problem in Boolean networks. (English) Zbl 1434.37013
Manea, Florin (ed.) et al., Computing with foresight and industry. 15th conference on computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11558, 132-143 (2019).
Summary: A Boolean network (BN) with \(n\) components is a discrete dynamical system described by the successive iterations of a function \(f:\{\mathtt{0},\mathtt{1}\}^n\rightarrow\{\mathtt{0},\mathtt{1}\}^n\). This model finds applications in biology, where fixed points play a central role. For example in genetic regulation they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components: component \(i\) has a positive (resp. negative) influence on component \(j\), meaning that \(j\) tends to mimic (resp. negate) \(i\). The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to multiple BNs. The present work opens a new perspective on the well-established study of fixed points in BNs. Biologists discover the SID of a BN they do not know, and may ask: given that SID, can it correspond to a BN having at least \(k\) fixed points? Depending on the input, this problem is in \(\mathrm{P}\) or complete for \(\mathrm{NP},\mathrm{NP}^\mathrm{\#P}\) or NEXPTIME.
For the entire collection see [Zbl 1428.68037].
For the entire collection see [Zbl 1428.68037].
MSC:
| 37C25 | Fixed points and periodic points of dynamical systems; fixed-point index theory; local dynamics |
| 37E25 | Dynamical systems involving maps of trees and graphs |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | The Online Encyclopedia of Integer Sequences, founded in 1964 by N. J. A. Sloane. Sequence A006126. https://oeis.org/A006126 |
| [2] | Akutsu, T., Miyano, S., Kuhara, S.: Identification of genetic networks from a small number of gene expression patterns under the boolean network model. In: Biocomputing’99, pp. 17-28. World Scientific (1999) |
| [3] | Albert, R.; Ben-Naim, E.; Frauenfelder, H.; Toroczkai, Z., Boolean modeling of genetic regulatory networks, Complex Networks, 459-481, 2004, Heidelberg: Springer, Heidelberg · Zbl 1079.92029 · doi:10.1007/978-3-540-44485-5_21 |
| [4] | Aracena, J., Maximum number of fixed points in regulatory Boolean networks, Bull. Math. Biol., 70, 5, 1398-1409, 2008 · Zbl 1144.92323 · doi:10.1007/s11538-008-9304-7 |
| [5] | 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 · doi:10.1016/S0166-218X(03)00461-X |
| [6] | 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 · doi:10.1016/j.jcss.2014.04.025 |
| [7] | 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 · doi:10.1137/16M1060868 |
| [8] | Boros, E.; Ibaraki, T.; Makino, K., Error-free and best-fit extensions of partially defined Boolean functions, Inf. Comput., 140, 2, 254-283, 1998 · Zbl 0892.68091 · doi:10.1006/inco.1997.2687 |
| [9] | Crama, Y.; Hammer, PL, Boolean Functions: Theory, Algorithms, and Applications, 2011, Cambridge: Cambridge University Press, Cambridge · Zbl 1237.06001 · doi:10.1017/CBO9780511852008 |
| [10] | 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 · doi:10.1016/0022-0000(92)90048-N |
| [11] | 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 · doi:10.1137/140988358 |
| [12] | 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 · doi:10.1109/TIT.2011.2155618 |
| [13] | Goles, E.; Salinas, L., Sequential operator for filtering cycles in Boolean networks, Adv. Appl. Math., 45, 3, 346-358, 2010 · Zbl 1205.68178 · doi:10.1016/j.aam.2010.03.002 |
| [14] | Kauffman, SA, Metabolic stability and epigenesis in randomly connected nets, J. Theor. Biol., 22, 437-467, 1969 · doi:10.1016/0022-5193(69)90015-0 |
| [15] | Kauffman, SA, Origins of Order Self-Organization and Selection in Evolution, 1993, Oxford: Oxford University Press, Oxford |
| [16] | Kaufman, M.; Soulé, C.; Thomas, R., A new necessary condition on interaction graphs for multistationarity, J. Theoret. Biol., 248, 4, 675-685, 2007 · Zbl 1451.92146 · doi:10.1016/j.jtbi.2007.06.016 |
| [17] | Kosub, S., Dichotomy results for fixed-point existence problems for Boolean dynamical systems, Math. Comput. Sci., 1, 3, 487-505, 2008 · Zbl 1138.68034 · doi:10.1007/s11786-007-0038-y |
| [18] | Le Novère, N., Quantitative and logic modelling of molecular and gene networks, Nat. Rev. Genet., 16, 146-158, 2015 · doi:10.1038/nrg3885 |
| [19] | Littman, ML; Goldsmith, J.; Mundhenk, M., The computational complexity of probabilistic planning, J. Artif. Intell. Res., 9, 1-36, 1998 · Zbl 0903.68100 · doi:10.1613/jair.505 |
| [20] | McCuaig, W., Pólya’s permanent problem, Electron. J. Comb., 11, 1, 79, 2004 · Zbl 1062.05066 · doi:10.37236/1832 |
| [21] | Montalva, M.; Aracena, J.; Gajardo, A., On the complexity of feedback set problems in signed digraphs, Electron. Not. Discrete Math., 30, 249-254, 2008 · Zbl 1341.05112 · doi:10.1016/j.endm.2008.01.043 |
| [22] | Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994) · Zbl 0833.68049 |
| [23] | Paulevé, L.; Richard, A., Topological fixed points in Boolean networks, Comptes Rendus de l’Académie des Sci.-Ser. I-Math., 348, 15-16, 825-828, 2010 · Zbl 1194.94209 · doi:10.1016/j.crma.2010.07.014 |
| [24] | 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 · doi:10.1016/j.aam.2007.11.003 |
| [25] | Richard, A., Positive and negative cycles in Boolean networks, J. Theor. Biol., 463, 67-76, 2019 · Zbl 1406.92252 · doi:10.1016/j.jtbi.2018.11.028 |
| [26] | Robert, F., Discrete Iterations: A Metric Study, 198, 1986, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-61607-5 |
| [27] | Robertson, N.; Seymour, P.; Thomas, R., Permanents, pfaffian orientations, and even directed circuits, Ann. Math., 150, 3, 929-975, 1999 · Zbl 0947.05066 · doi:10.2307/121059 |
| [28] | Soulé, C., Mathematical approaches to differentiation and gene regulation, C.R. Paris Biol., 329, 13-20, 2006 · doi:10.1016/j.crvi.2005.10.002 |
| [29] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160, 1972 · Zbl 0251.05107 · doi:10.1137/0201010 |
| [30] | Thomas, R., Boolean formalization of genetic control circuits, J. Theor. Biol., 42, 3, 563-585, 1973 · doi:10.1016/0022-5193(73)90247-6 |
| [31] | Thomas, R.; d’Ari, R., Biological Feedback, 1990, Boca Raton: CRC Press, Boca Raton · Zbl 0743.92003 |
| [32] | Thomas, R., Kaufman, M.: Multistationarity, the basis of cell differentiation and memory. II. Logical analysis of regulatory networks in terms of feedback circuits. Chaos Interdisc. 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.
