×

Morphogenetic systems for resource bounded computation and modeling. (English) Zbl 1475.68125

Summary: A further exploration is presented of recent approaches to morphogenetic processes where geometry and form are fundamental primitives. Prior bottom-up approaches in morphogenetic modeling usually target a specific biological process aiming for optimal fidelity. We take a novel, more integrative and more abstract view of these phenomena and aim at properties such as (computational) universality, homeostasis, self-reproduction or self-healing, in both living and artificial evolving systems with explicit geometric 3D arrangements. We refine the recently introduced model of M systems (for morphogenetic systems) that leverages certain constructs in membrane computing and DNA self-assembly. The model is still based on local interactions of simple atomic components under explicit geometric constraints given by their shapes and spatial arrangements. We demonstrate two types of capabilities of the extended models. First, they are computationally universal in the Turing sense because they can simulate Turing machines very efficiently, with only a linear slowdown factor. Furthermore, they have the theoretical capability to probabilistically solve NP-hard problems in polynomial time. Second, more importantly, they unfold to exhibit certain macro-properties characteristic of living organisms (particularly, the ability of self-assembly of complex structures, self-reproduction and self-healing) as global properties observable at the macro-level, without explicit programming of these properties beyond simple rules of interaction. Besides providing a new theoretical background for this type of model, we provide quantitative evidence of these properties in a simple cell-like M system model. These results have been obtained using an M system simulator and visualizer that is available as open source software for further research in this area.

MSC:

68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Turing, A., The chemical basis of morphogenesis, Philos. Trans. R. Soc. Lond. B, 237, 7-72 (1950) · Zbl 1403.92034
[2] von Neumann, J.; Burks, A., Theory of Self-reproducing Automata (1966), University of Illinois Press: University of Illinois Press Urbana
[3] Codd, E., Cellular Automata (1968), Academic Press: Academic Press New York · Zbl 0213.18301
[4] Lindenmayer, A.; Prusinkiewicz, P., The Algorithmic Beauty of Plants (1991), Springer: Springer Berlin · Zbl 0850.92038
[5] R. Mech, P. Prusinkiewicz, Visual models of plants interacting with their environment, in: B. Blau, et al. (Eds.), Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, ACM, 1996, pp. 397-410.
[6] Tomita, M., Whole-cell simulation: a grand challenge of the 21st century, Trends Biotechnol., 19, 6, 205-210 (2001)
[7] (Păun, G.; Rozenberg, G.; Salomaa, A., The Oxford Handbook of Membrane Computing (2010), Oxford University Press: Oxford University Press Oxford) · Zbl 1237.68001
[8] Barbuti, R.; Maggiolo-Schettini, A.; Milazzo, P.; Pardini, G.; Tesei, L., Spatial P systems, Nat. Comput., 10, 1, 3-16 (2011) · Zbl 1213.68256
[9] Bernardini, F.; Brijder, R.; Rozenberg, G.; Zandron, C., Multiset-based self-assembly of graphs, Fundam. Inf., 75, 1-4, 49-75 (2007) · Zbl 1108.68085
[10] Bernardini, F.; Brijder, R.; Cavaliere, M.; Franco, G.; Hoogeboom, H. J.; Rozenberg, G., On aggregation in multiset-based self-assembly of graphs, Nat. Comput., 10, 1, 17-38 (2011) · Zbl 1213.68257
[11] Manca, V.; Pardini, G., Morphogenesis through moving membranes, Nat. Comput., 13, 3, 403-419 (2014)
[12] Cavaliere, M.; Mardare, R.; Sedwards, S., A multiset-based model of synchronizing agents: Computability and robustness, Theor. Comput. Sci., 391, 3, 216-238 (2008) · Zbl 1133.68019
[13] L. Cardelli, P. Gardner, Processes in space, in: F. Ferreira, B. Löwe, E. Mayordomo, L. Mendes Gomes (Eds.), Programs, Proofs, Processes: 6th Conference on Computability in Europe, CiE 2010, vol. 6158, Springer, Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 78-87. · Zbl 1286.68345
[14] K. Tangirala, D. Caragea, Generating features using burrows wheeler transformation for biological sequence classification, in: O. et al. Pastor (Ed.), Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms, SciTePress, 2014, pp. 196-203.
[15] Benson, E.; Mohammed, A.; Gardell, J.; Masich, S.; Czeizler, E.; Orponen, P.; Högberg, B., DNA rendering of polyhedral meshes at the nanoscale, Nature, 523, 7561, 441 (2015)
[16] Winfree, E., Self-healing tile sets, (Chen, G. R.J.; Jonoska, N., Nanotechnology: Science and Computation, Natural Computing Series (2006), Springer-Verlag), 55-66
[17] P. Sosík, V. Smolka, J. Drastík, T. Moore, M. Garzon, Morphogenetic and homeostatic self-assembled systems, in: M. J. Patitz, M. Stannett (Eds.), Unconventional Computation and Natural Computation: 16th Int. Conf., UCNC 2017, Vol. 10240 of Lecture Notes in Computer Science, Springer, Berlin, 2017, pp. 144-159. · Zbl 1486.68069
[18] Sosík, P.; Smolka, V.; Drastík, J.; Bradík, J.; Garzon, M., On the robust power of morphogenetic systems for time bounded computation, (Gheorghe, M., Membrane Computing, 18th International Conference, CMC18. Membrane Computing, 18th International Conference, CMC18, Lecture Notes in Computer Science, vol. 10725 (2018), Springer: Springer Berlin), 270-292 · Zbl 1497.68203
[19] Sosík, P.; Smolka, V.; Bradík, J.; Garzon, M., Modeling plant development with M systems, (Hinze, T.; Rozenberg, G.; Salomaa, A.; Zandron, C., Membrane Computing, 19th International Conference, CMC19. Membrane Computing, 19th International Conference, CMC19, Lecture Notes in Computer Science, vol. 11399 (2019), Springer International Publishing: Springer International Publishing Cham), 246-257 · Zbl 1522.68220
[20] N. Krasnogor, S. Gustafson, D. Pelta, J. Verdegay, Systems Self-Assembly: Multidisciplinary Snapshots, Studies in Multidisciplinarity, Elsevier Science, 2011.
[21] E. Winfree, Models of experimental self-assembly, Ph.D. thesis, Caltech, 1998.
[22] Ziegler, G., Lectures on Polytopes, Graduate Texts in Mathematics (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0823.52002
[23] Maxwell-Boltzmann distribution, Wikipedia (cit. 2017-1-29). https://en.wikipedia.org/wiki/Maxwell-Boltzmann_distribution.
[24] V. Smolka, J. Drastík, M. Garzon, P. Sosík, Cytos: morphogenetic (M) systems for modeling and experimentation, in: G. Păun (Ed.), Proceedings of the 20th International Conference on Membrane Computing, CMC 20, Editura Bibliostar, Ramnicu Valcea, 2019, pp. 475-496.
[25] Adleman, L. M., Molecular computation of solutions to combinatorial problems, Science, 266, 5187, 1021-1024 (1994)
[26] Braich, R. S.; Chelyapov, N.; Johnson, C.; Rothemund, P. W.K.; Adleman, L., Solution of a 20-variable 3-SAT problem on a DNA computer, Science, 296, 5567, 499-502 (2002)
[27] Head, T.; Rozenberg, G.; Bladergroen, R. S.; Breek, C.; Lommerse, P.; Spaink, H. P., Computing with DNA by operating on plasmids, Biosystems, 57, 2, 87-93 (2000)
[28] Zhang, D. Y.; Seelig, G., Dynamic DNA nanotechnology using strand-displacement reactions, Nat. Chem., 3, 2, 103 (2011)
[29] M. Amos, DNA computing, Unconventional Computing: A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition (2018) 307-325. · Zbl 1397.68004
[30] Benenson, Y.; Gil, B.; Ben-Dor, U.; Adar, R.; Shapiro, E., An autonomous molecular computer for logical control of gene expression, Nature, 429, 6990, 423 (2004)
[31] Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A., DNA solution of the maximal clique problem, Science, 278, 5337, 446-449 (1997)
[32] Karr, J. R.; Sanghvi, J. C.; Macklin, D. N.; Gutschow, M. V.; Jacobs, J. M.; Bolival, B.; Assad-Garcia, N.; Glass, J. I.; Covert, M. W., A whole-cell computational model predicts phenotype from genotype, Cell, 150, 2, 389-401 (2012)
[33] Păun, A.; Păun, G., The power of communication: P systems with symport/antiport, New Gen. Comput., 20, 3, 295-305 (2002) · Zbl 1024.68037
[34] Păun, A.; Popa, B., P systems with proteins on membranes, Fundam. Inf., 72, 4, 467-483 (2006) · Zbl 1099.68031
[35] Păun, G., P systems with active membranes: attacking NP-complete problems, J. Autom., Lang. Combinat., 6, 1, 75-90 (2001) · Zbl 0970.68066
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.