nach oben

Natural Computing

Erschienen in:

29.06.2023

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

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

Erschienen in: Natural Computing | Ausgabe 3/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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\).

Vorheriger Artikel Preface

Nächster Artikel Linear cuts in Boolean networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Complexity of limit cycles with block-sequential update schedules in conjunctive networks
verfasst von: Julio Aracena
Florian Bridoux
Luis Gómez
Lilian Salinas
Publikationsdatum: 29.06.2023
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2023
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-023-09947-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2023

Gauge-invariance in cellular automata

Enumeration of maximal cycles generated by orthogonal cellular automata

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

Cellular automata and substitutions in topological spaces defined via edit distances

Preface

Linear cuts in Boolean networks

Premium Partner