Top

Natural Computing

Published in:

29-06-2023

Complexity of limit cycles with block-sequential update schedules in conjunctive networks

Authors: Julio Aracena, Florian Bridoux, Luis Gómez, Lilian Salinas

Published in: Natural Computing | Issue 3/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we deal with the following decision problem: given a conjunctive Boolean network defined by its interaction digraph, does it have a limit cycle of a given length k? We prove that this problem is NP-complete in general if k is a parameter of the problem and is in P if the interaction digraph is strongly connected. The case where k is fixed, but the interaction digraph is not strongly connected, remains open. Furthermore, we study some variations of the decision problem: given a conjunctive Boolean network, does there exist a block-sequential (resp. sequential) update schedule such that there is a limit cycle of length k? We prove that these problems are NP-complete for any fixed constant \(k \ge 2\).

previous article Preface

next article Linear cuts in Boolean networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Aledo JA, Martinez S, Pelayo FL, Valverde JC (2012) Parallel discrete dynamical systems on maxterm and minterm Boolean functions. Math Comput Model 55:666–671MathSciNetMATH

Aracena J, Demongeot J, Fanchon E, Montalva M (2013) On the number of different dynamics in Boolean networks with deterministic update schedules. Math Biosci 242:188–194MathSciNetMATH

Aracena J, Demongeot J, Goles E (2004) Fixed points and maximal independent sets in AND-OR networks. Discrete Appl Math 138:277–288MathSciNetMATH

Aracena J, Fanchon E, Montalva M, Noual M (2011) Combinatorics on update digraphs in Boolean networks. Discrete Appl Math 159:401–409MathSciNetMATH

Aracena J, Goles E, Moreira A, Salinas L (2009) On the robustness of update schedules in Boolean networks. Biosystems 97:1–8

Aracena J, Gómez L, Salinas L (2013) Limit cycles and update digraphs in Boolean networks. Discrete Appl Math 161:1–2MathSciNetMATH

Aracena J, Richard A, Salinas L (2017) Fixed points in conjunctive networks and maximal independent sets in graph contractions. J Comput Syst Sci 88:145–163MathSciNetMATH

Atkin A, Bernstein D (2004) Prime sieves using binary quadratic forms. Math Comput 73:1023–1030MathSciNetMATH

Berman A, Plemmons RJ (1994) Nonnegative matrices in the mathematical sciences. Society for Industrial and Applied Mathematics (SIAM), PhiladelphiaMATH

Bridoux F, Gaze-Maillot C, Perrot K, Sené S (2021) Complexity of limit-cycle problems in Boolean networks. In: Bures T, Dondi R, Gamper J, Guerrini G, Jurdzinski T, Pahl C, Sikora F, Wong PWH (eds) SOFSEM 2021: theory and practice of computer science—47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021, Proceedings. Springer, pp 135–146. https://doi.org/10.1007/978-3-030-67731-2_10

Brualdi RA, Ryser HJ et al (1991) Combinatorial matrix theory, vol 39. Springer, ChamMATH

Colón-Reyes O, Laubenbacher R, Pareigis B (2005) Boolean monomial dynamical systems. Ann Comb 8:425–439MathSciNetMATH

De Jong H (2002) Modeling and simulation of genetic regulatory systems: a literature review. J Comput Biol 9:67–103MathSciNet

Demongeot J, Elena A, Sené S (2008) Robustness in regulatory networks: a multi-disciplinary approach. Acta Biotheor 56:27–49

Gadouleau M (2021) Dynamical properties of disjunctive Boolean networks (invited talk). In: Castillo-Ramirez A, Guillon P, Perrot K (eds) 27th IFIP WG 1.5 international workshop on cellular automata and discrete complex systems, AUTOMATA 2021, July 12–14, 2021, Aix-Marseille University, France, Schloss Dagstuhl–Leibniz–Zentrum für Informatik, pp 1:1–1:15. https://doi.org/10.4230/OASIcs.AUTOMATA.2021.1

Gadouleau M, Richard A, Fanchon E (2016) Reduction and fixed points of Boolean networks and linear network coding solvability. IEEE Trans Inf Theory 62:2504–2519MathSciNetMATH

Gadouleau M, Riis S (2011) Graph-theoretical constructions for graph entropy and network coding based communications. IEEE Trans Inf Theory 57:6703–6717MathSciNetMATH

Gao Z, Chen X, Başar T (2018) Stability structures of conjunctive Boolean networks. Automatica 89:8–20MathSciNetMATH

Goles E (1985) Dynamics on positive automata networks, Theor. Comp. Sciences, to appear

Goles E, Hernández G (2000) Dynamical behavior of Kauffman networks with AND-OR gates. J Biol Syst 8:151–175

Goles E, Martinez S (2013) Neural and automata networks: dynamical behavior and applications, vol 58. Springer Science & Business Media, ChamMATH

Goles E, Montalva M, Ruz GA (2013) Deconstruction and dynamical robustness of regulatory networks: application to the yeast cell cycle networks. Bull Math Biol 75:939–966MathSciNetMATH

Goles E, Montealegre P (2014) Computational complexity of threshold automata networks under different updating schemes. Theor Comput Sci 559:3–19MathSciNetMATH

Goles E, Noual M (2012) Disjunctive networks and update schedules. Adv Appl Math 48:646–662MathSciNetMATH

Gómez L (2015) Dynamics of discrete networks with deterministic updates schedules. Application to genetic regulatory networks. Ph.D. thesis in mathematical engineering. Universidad de Concepción. Concepción, Chile

Gummow BM, Scheys JO, Cancelli VR, Hammer GD (2006) Reciprocal regulation of a glucocorticoid receptor-steroidogenic factor-1 transcription complex on the Dax-1 promoter by glucocorticoids and adrenocorticotropic hormone in the adrenal cortex. Mol Endocrinol 20:2711–2723

Hopfield JJ (1982) Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci 79:2554–2558MathSciNetMATH

Jarrah AS, Laubenbacher R, Veliz-Cuba A (2010) The dynamics of conjunctive and disjunctive Boolean network models. Bull Math Biol 72:1425–1447MathSciNetMATH

Jarrah AS, Laubenbacher R, Veliz-Cuba A (2010) The dynamics of conjunctive and disjunctive Boolean networks. Bull Math Biol 72:1425–1447MathSciNetMATH

Kauffman SA (1969) Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol 22:437–467MathSciNet

Macauley M, Mortveit HS (2009) Cycle equivalence of graph dynamical systems. Nonlinearity 22:421MathSciNetMATH

McCulloch WS, Pitts W (1943) A logical calculus of the ideas immanent in nervous activity. Bull Math Biophys 5:115–133MathSciNetMATH

Mortveit HS (2012) Limit cycle structure for block-sequential threshold systems. In: Sirakoulis GC, Bandini S (eds) Cellular automata, vol 7495. Springer, Berlin Heidelberg, pp 672–678. https://doi.org/10.1007/978-3-642-33350-7_69

Nguyen DH, D’haeseleer P (2006) Deciphering principles of transcription regulation in eukaryotic genomes. Mol Syst Biol 2:2006.0012

Papadimitriou CH (1994) Computational complexity. Addison-Wesley, BostonMATH

Park I, Lee KH, Lee D (2010) Inference of combinatorial Boolean rules of synergistic gene sets from cancer microarray datasets. Bioinformatics 26:1506–1512

Poindron A (2021) A general model of binary opinions updating. Math Soc Sci 109:52–76MathSciNetMATH

Poljak S, Sura M (1983) On periodical behaviour in societies with symmetric influences. Combinatorica 3:119–121MathSciNetMATH

Riis S (2007) Information flows, graphs and their guessing numbers. Electron J Comb 14:R44–R44

Robert F (1986) Discrete iterations: a metric study. Springer-Verlag, Berlin

Robert F (1995) Les systemes dynamiques discrets, vol 19. Springer Science & Business Media, ChamMATH

Robin G (1983) Estimation de la fonction de Tschebyshef theta sur le \(k\)-ieme nombre premier et grandes valeurs de la fonction \(w(n)\), nombre de diviseurs premiers de \(n\). Acta Arith 42:367–389

Ruz GA, Timmermann T, Barrera J, Goles E (2014) Neutral space analysis for a Boolean network model of the fission yeast cell cycle network. Biol Res 47:64

Salinas L, Gómez L, Aracena J (2022) Existence and non existence of limit cycles in Boolean networks. In: Adamatzky A (ed) Automata and complexity: essays presented to eric goles on the occasion of his 70th birthday. Springer, Cham, pp 233–252. https://doi.org/10.1007/978-3-030-92551-2_15

Schutter BD, Moor BD (2000) On the sequence of consecutive powers of a matrix in a Boolean algebra. SIAM J Matrix Anal Appl 21:328–354MathSciNetMATH

Shis DL, Bennett MR (2013) Library of synthetic transcriptional AND gates built with split T7 RNA polymerase mutants. Proc Natl Acad Sci 110:5028–5033

Thomas R (1973) Boolean formalization of genetic control circuits. J Theor Biol 42:563–585

Thomas R, d’Ari R (1990) Biological feedback. CRC Press, Boca RatonMATH

Thomas R, Kaufman M (2001) Multistationarity, the basis of cell differentiation and memory. I. Structural conditions of multistationarity and other nontrivial behavior. Chaos Interdiscip J Nonlinear Sci 11:170–179MathSciNetMATH

Title: Complexity of limit cycles with block-sequential update schedules in conjunctive networks
Authors: Julio Aracena
Florian Bridoux
Luis Gómez
Lilian Salinas
Publication date: 29-06-2023
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2023
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-023-09947-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2023

Linear cuts in Boolean networks

Cellular automata and substitutions in topological spaces defined via edit distances

Associating parallel automata network dynamics and strictly one-way cellular automata

Gauge-invariance in cellular automata

An exploration of reversible septenary number-conserving cellular automata: a survey of known methods

Multiobjective evolutionary algorithm IDEA and k-means clustering for modeling multidimenional medical data based on fuzzy cognitive maps

Premium Partner