nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Optimising Attractor Computation in Boolean Automata Networks

verfasst von : Kévin Perrot, Pacôme Perrotin, Sylvain Sené

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper details a method for optimising the size of Boolean automata networks in order to compute their attractors under the parallel update schedule. This method relies on the formalism of modules introduced recently that allows for (de)composing such networks. We discuss the practicality of this method by exploring examples. We also propose results that nail the complexity of most parts of the process, while the complexity of one part of the problem is left open.

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

Vorheriges Kapitel Succinct Representations for (Non)Deterministic Finite Automata

Nächstes Kapitel On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata

Aracena, J.: Maximum number of fixed points in regulatory Boolean networks. Bull. Math. Biol. 70, 1398–1409 (2008). https://doi.org/10.1007/s11538-008-9304-7MathSciNetCrossRefMATH

Aracena, J., Richard, A., Salinas, L.: Number of fixed points and disjoint cycles in monotone Boolean networks. SIAM J. Discr. Math. 31, 1702–1725 (2017)MathSciNetCrossRef

Bridoux, F., Durbec, N., Perrot, K., Richard, A.: Complexity of maximum fixed point problem in Boolean networks. In: Manea, F., Martin, B., Paulusma, D., Primiero, G. (eds.) CiE 2019. LNCS, vol. 11558, pp. 132–143. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22996-2_12CrossRef

Bridoux, F., Gaze-Maillot, C., Perrot, K., Sené, S.: Complexity of limit-cycle problems in Boolean networks (2020, submitted) arXiv:2001.07391

Davidich, M.I., Bornholdt, S.: Boolean network model predicts cell cycle sequence of fission yeast. PLoS One 3, e1672 (2008)CrossRef

Demongeot, J., Goles, E., Morvan, M., Noual, M., Sené, S.: Attraction basins as gauges of robustness against boundary conditions in biological complex systems. PLoS One 5, e11793 (2010)CrossRef

Demongeot, J., Noual, M., Sené, S.: Combinatorics of Boolean automata circuits dynamics. Discrete Appl. Math. 160, 398–415 (2012)MathSciNetCrossRef

Floreen, P., Orponen, P.: Counting stable states and sizes of attraction domains in Hopfield nets is hard. In: Proceedings of IJCNN 1989, pp. 395–399. IEEE (1989)

Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006). https://doi.org/10.1007/11685654_12CrossRef

10.

Goles, E., Salinas, L.: Comparison between parallel and serial dynamics of Boolean networks. Theor. Comput. Sci. 396, 247–253 (2008)MathSciNetCrossRef

11.

Ilango, R., Loff, B., Oliveira, I.C.: NP-hardness of circuit minimization for multi-output functions. In: Proceedings of ECCC 2020, pp. TR20-021 (2020)

12.

Kabanets, V., Cai, J.: Circuit minimization problem. In: Proceedings of STOC 2000, pp. 73–79. ACM (2000)

13.

Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol. 22, 437–467 (1969)MathSciNetCrossRef

14.

Meggido, N., Papadimitriou, C.: A note on total functions, existence theorems, and computational complexity. Technical report, IBM (1989)

15.

Mendoza, L., Alvarez-Buylla, E.R.: Dynamics of the genetic regulatory network for Arabidopsis thaliana flower morphogenesis. J. Theor. Biol. 193, 307–319 (1998)CrossRef

16.

Noual, M.: Dynamics of circuits and intersecting circuits. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 433–444. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28332-1_37CrossRefMATH

17.

Noûs, C., Perrot, K., Sené, S., Venturini, L.: #P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method. In: Proceedings of CiE 2020 (2020, accepted), arXiv:2004.02129

18.

Orponen, P.: Neural networks and complexity theory. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 50–61. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55808-X_5CrossRef

19.

Perrot, K., Perrotin, P., Sené, S.: A framework for (De)composing with Boolean automata networks. In: Durand-Lose, J., Verlan, S. (eds.) MCU 2018. LNCS, vol. 10881, pp. 121–136. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92402-1_7CrossRef

20.

Perrot, K., Perrotin, P., Sené, S.: On the complexity of acyclic modules in automata networks. In: Chen, J., Feng, Q., Xu, J. (eds.) TAMC 2020. LNCS, vol. 12337, pp. 168–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59267-7_15. arXiv:1910.07299CrossRef

21.

Robert, F.: Discrete Iterations: A Metric Study. Springer, Heidelberg (1986). https://doi.org/10.1007/978-3-642-61607-5CrossRef

22.

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

Titel: Optimising Attractor Computation in Boolean Automata Networks
verfasst von: Kévin Perrot
Pacôme Perrotin
Sylvain Sené
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-68194-4

Electronic ISBN: 978-3-030-68195-1

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-68195-1_6

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"