Abstract
Chemical reactions and diffusion can produce a wide variety of static or transient spatial patterns in the concentrations of chemical species. Little is known, however, about what dynamical patterns of concentrations can be reliably programmed into such reaction-diffusion systems. Here we show that given simple, periodic inputs, chemical reactions and diffusion can reliably emulate the dynamics of a deterministic cellular automaton, and can therefore be programmed to produce a wide range of complex, discrete dynamics. We describe a modular reaction-diffusion program that orchestrates each of the fundamental operations of a cellular automaton: storage of cell state, communication between neighboring cells, and calculation of cells’ subsequent states. Starting from a pattern that encodes an automaton’s initial state, the concentration of a “state” species evolves in space and time according to the automaton’s specified rules. To show that the reaction-diffusion program we describe produces the target dynamics, we simulate the reaction-diffusion network for two simple 1-dimensional cellular automata using coupled partial differential equations. Reaction-diffusion based cellular automata could potentially be built in vitro using networks of DNA molecules that interact via branch migration processes and could in principle perform universal computation, storing their state as a pattern of molecular concentrations, or deliver spatiotemporal instructions encoded in concentrations to direct the behavior of intelligent materials.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Murray, J.D.: Mathematical Biology II: Spatial Models and Biomedical Applications, 3rd edn. Springer, New York (2003)
Greenfield, D., et al.: Self-organization of the Escherichia coli chemotaxis network imaged with super-resolution light microscopy. PLoS Biol. 7 (2009)
Baker, M.D., Wolanin, P.M., Stock, J.B.: Signal transduction in bacterial chemotaxis. Bioessay 28(1), 9–22 (2006)
Gács, P.: Reliable cellular automata with self-organization. J. Stat. Phys. 103, 45–267 (2001)
Gács, P., Reif, J.: A simple three-dimensional real-time reliable cellular array. J. Comput. Syst. Sci. 36, 125–147 (1988)
Cook, M.: Universality in elementary cellular automata. Complex Systems 15, 1–40 (2004)
Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 132–143. Springer, Heidelberg (2006)
von Neumann, J.A.W., Burks, E.: The Theory of Self-Reproducing Automata. University of Illinois Press, Urbana (1966)
Codd, E.F.: Cellular automata. Academic Press, Inc., San Diego (1968)
Langton, C.G.: Self-reproduction in cellular automata. Physica D 10(1), 135–144 (1984)
Sayama, H.: A new structurally dissolvable self-reproducing loop evolving in a simple cellular automata space. Artificial Life 5(4), 343–365 (1999)
Turing, A.M.: The chemical basis of morphogenesis. Phil. T. Roy. Soc. B 237, 37–72 (1952)
Tóth, Á., Showalter, K.: Logic gates in excitable media. The Journal of Chemical Physics 103, 2058–2066 (1995)
Steinbock, O., Kettunen, P., Showalter, K.: Chemical wave logic gates. The Journal of Physical Chemistry 100, 18970–18975 (1996)
Bánsági, T., Vanag, V.K., Epstein, I.R.: Tomography of reaction-diffusion microemulsions reveals three-dimensional Turing patterns. Science 331, 1309–1312 (2011)
Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. P. Natl. Acad. Sci. 107, 5393–5398 (2010)
Chen, Y., et al.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8, 755–762 (2013)
Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement. Science 332, 1196–1201 (2011)
Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314, 1585–1588 (2006)
Qian, L., Winfree, E.: A simple DNA gate motif for synthesizing large-scale circuits. J. R. Soc. Interface 8, 1281–1297 (2011)
Smith, D.E., Perkins, T.T., Chu, S.: Dynamical scaling of DNA diffusion coefficients. Macromolecules 29, 1372–1373 (1996)
Allen, P.B., Chen, X., Ellington, A.D.: Spatial control of DNA reaction networks by DNA sequence. Molecules 17, 13390–13402 (2012)
Chirieleison, S.M., Allen, P.B., Simpson, Z.B., Ellington, A.D., Chen, X.: Pattern transformation with DNA circuits. Nature Chem. 5, 1000–1005 (2013)
Scalise, D., Schulman, R.: Designing modular reaction-diffusion programs for complex pattern formation. Technology 2, 55–66 (2014)
Ruiza, S.A., Chen, C.S.: Microcontact printing: A tool to pattern. Soft Matter 3, 168–177 (2007)
Du, Y., Lo, E., Ali, S., Khademhosseini, A.: Directed assembly of cell-laden microgels for fabrication of 3D tissue constructs. P. Natl. Acad. Sci. 105, 9522–9527 (2008)
Nehaniv, C.L.: Asynchronous automata networks can emulate any synchronous automata network. International Journal of Algebra and Computation 14, 719–739 (2004)
Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16. LNCS, vol. 6518, pp. 123–140. Springer, Heidelberg (2011)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Natural Computing 7, 615–633 (2008)
Peterson, J.L.: Petri net theory and the modeling of systems. Prentice Hall, Englewood Cliffs (1981)
Lindenmayer, A.: Mathematical models for cellular interactions in development I. filaments with one-sided inputs. J. Theor. Biol. 18, 280–299 (1968)
Wu, A., Rosenfeld, A.: Cellular graph automata. I. basic concepts, graph property measurement, closure properties. Information and Control 42, 305–329 (1979)
Tomita, K., Kurokawa, H., Murata, S.: Graph automata: natural expression of self-reproduction. Physica D: Nonlinear Phenomena 171, 197–210 (2002)
Zhang, D.Y., Winfree, E.: Control of DNA strand displacement kinetics using toehold exchange. J. Am. Chem. Soc. 131, 17303–17314 (2009)
Lukacs, G.L., Haggie, P., Seksek, O., Lechardeur, D., Verkman, N.F.A.: Size-dependent DNA mobility in cytoplasm and nucleus. J. Biol. Chem. 275 (2000)
Stellwagen, E., Lu, Y., Stellwagen, N.: Unified description of electrophoresis and diffusion for DNA and other polyions. Biochemistry 42 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Scalise, D., Schulman, R. (2014). Emulating Cellular Automata in Chemical Reaction-Diffusion Networks. In: Murata, S., Kobayashi, S. (eds) DNA Computing and Molecular Programming. DNA 2014. Lecture Notes in Computer Science, vol 8727. Springer, Cham. https://doi.org/10.1007/978-3-319-11295-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-11295-4_5
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11294-7
Online ISBN: 978-3-319-11295-4
eBook Packages: Computer ScienceComputer Science (R0)