Top

Natural Computing

Published in:

01-06-2008

How crystals that sense and respond to their environments could evolve

Authors: Rebecca Schulman, Erik Winfree

Published in: Natural Computing | Issue 2/2008

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

search-config

AI-assisted search

Off

Abstract

An enduring mystery in biology is how a physical entity simple enough to have arisen spontaneously could have evolved into the complex life seen on Earth today. Cairns-Smith has proposed that life might have originated in clays which stored genomes consisting of an arrangement of crystal monomers that was replicated during growth. While a clay genome is simple enough to have conceivably arisen spontaneously, it is not obvious how it might have produced more complex forms as a result of evolution. Here, we examine this possibility in the tile assembly model, a generalized model of crystal growth that has been used to study the self-assembly of DNA tiles. We describe hypothetical crystals for which evolution of complex crystal sequences is driven by the scarceness of resources required for growth. We show how, under certain circumstances, crystal growth that performs computation can predict which resources are abundant. In such cases, crystals executing programs that make these predictions most accurately will grow fastest. Since crystals can perform universal computation, the complexity of computation that can be used to optimize growth is unbounded. To the extent that lessons derived from the tile assembly model might be applicable to mineral crystals, our results suggest that resource scarcity could conceivably have provided the evolutionary pressures necessary to produce complex clay genomes that sense and respond to changes in their environment.

previous article Combining self-healing and proofreading in self-assembly

next article Automating the DNA computer: solving n-Variable 3-SAT problems

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

In growth that proceeds downward, rather than upward, the tiles labelled resource tiles function as measurement tiles, and vice versa. Thus, both assemblies that can predict the resource tile types that are available from the measurement tiles, and those that can predict the measurement tile types that will be available from the current concentration of resource tiles will be selected for. Note, however, that gate types may be non-deterministic during downward growth, which could result in crystal growth stalling when a tile is incorporated that creates a binding site that matches no gate tile’s outputs. Therefore, consideration of downward growth rates is necessary for a complete evaluation of a crystal’s fitness; but we neglect it here to simplify the presentation.

This estimate assumes that since Δt ≫ s, at any particular time the resource and measurement tile concentrations are uncorrelated. So half the time, the resource and measurement tiles are compatible, and the crystal grows at a rate of D + 1 seconds per zig-zag; and half the time the resource and measurement tiles are not compatible, and the crystal essentially doesn’t grow.

Note that counters whose natural period is slightly less than the period of the environment will easily remain synchronized with the environment, even when there is variation in the arrival times of the tiles being added.

While zig-zag assemblies copy layers on both growth fronts, for the purposes of our argument, we will assume that computation on zig-zag assemblies proceeds in only one direction (upward). While this is not necessarily so for the tile sets we describe, growth can be restricted to one direction by using a transformed tile set (Winfree 2006) that uses extra tiles to prevent growth in the wrong direction.

In cases where a complete shape is necessary for selective advantage, it is also possible to use a construction where crystals can grow forward as well as backward, so that the parent crystal can grow back the piece of the shape that was lost during splitting (Winfree 2006).

Barish RD, Rothemund PWK, Winfree E (2005) Two computational primitives for algorithmic self-assembly: copying and counting. Nano Lett 5:2586–2592CrossRef

Bedau MA, McCaskill JS, Packard NH, Rasmussen S, Adami C, Green DG, Ikegami T, Kaneko K, Ray TS (2000) Open problems in artificial life. Artif Life 6(4):363–376CrossRef

Blum M (1967) A machine-independent theory of the complexity of recursive functions. J ACM 14:322–336MATHCrossRefMathSciNet

Bowden N, Terfort A, Carbeck J, Whitesides G (1997) Self-assembly of mesoscale objects into ordered two-dimensional arrays. Science 276:233–235CrossRef

Cairns-Smith AG (1966) The origin of life and the nature of the primitive gene. J Theor Biol 10:53–88CrossRef

Cairns-Smith AG (1982) Genetic takeover and the mineral origins of life. Cambridge University Press

Cairns-Smith AG, Hartman H (1986) Clay minerals and the origin of life. Cambridge University Press

Chen H-L, Goel A (2004) Error free self-assembly using error prone tiles. In DNA Computing 10, Berlin Heidelberg, Springer-Verlag

Chworos A, Severcan I, Koyfman AY, Weinkam P, Oroudjev E, Hansma HG, Jaeger L (2004) Building programmable jigsaw puzzles with RNA. Science 306:2068–2072CrossRef

Collins SR, Douglass A, Vale RD, Weissman JS (2004) Mechanism of prion propagation: amyloid growth occurs by monomer addition. PLoS Biol 2:e321CrossRef

Cook M, Rothemund PWK, Winfree E (2004) Self-assembled circuit patterns. In: Chen J, Reif J (eds) DNA Computing 9, volume LNCS 2943. Springer-Verlag, Berlin Heidelberg, pp 91–107

Eigen M (1971) Self-organization of matter and evolution of biological macromolecules. Naturwissenschaften 58(10):465–523CrossRef

Ekani-Nkodo A, Kumar A, Fygenson DK (2004) Joining and scission in the self-assembly of nanotubes from DNA tiles. Phys Rev Lett 93:268301CrossRef

Fygenson DK, Flyvbjerg H, Sneppen K, Libchaber A, Leibler S (1995) Spontaneous nucleation of microtubules. Physical Review E 51:5058–5063CrossRef

Hanczyc MM, Fujikawa SM, Szostak JW (2003) Experimental models of primitive cellular compartments: encapsulation, growth, and division. Science 302:618–622CrossRef

Joyce GF (2004) Directed evolution of nucleic acid enzymes. Annu Rev Biochem 73:791–836CrossRef

Lagoudakis MG, LaBean TH (2000) 2-D DNA self-assembly for satisfiability. In: Winfree E, Gifford DK (eds) DNA based computers V, volume 54 of DIMACS. American Mathematical Society, Providence, RI, pp 141–154

Levin LA (1973) Universal sequential search problems. Probl Inf Transm 9:265–266

Mao C, LaBean TH, Reif JH, Seeman NC (2000) Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407(6803):493–496CrossRef

Pitsch S, Eschenmoser A, Gedulin B, Hui S, Arrhenius G (1995) Mineral induced formation of sugar phosphates. Orig Life Evol Biosph 25(4):297–334CrossRef

Reif JH, Sahu S, Yin P (2004) Compact error-resilient computational DNA tiling assemblies. In DNA Computing 10, Berlin Heidelberg, Springer-Verlag

Rothemund PWK (2000) Using lateral capillary forces to compute by self-assembly. Proc Natl Acad Sci 97:984–989CrossRef

Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2:424–436CrossRef

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares. In Symposium on Theory of Computing (STOC), pages 459–468 ACM,

Schulman R, Winfree E (2005) Self-replication and evolution of DNA crystals. In Advances in Artificial Life, 8th European Conference, volume 3630. Springer-Verlag, Berlin Heidelberg, pp 734–743

Sipser M (1997) Introduction to the theory of computation. PWS Publishing Company

Solomonoff RJ (1964) A formal theory of inductive inference: Part 1 and 2. Inf Control 7:(1–22)224–254CrossRefMathSciNet

Soloveichik D, Winfree E (2004) Complexity of self-assembled scale-invariant shapes. In: DNA Computing 10.Berlin Heidelberg, Springer-Verlag

Wang H (1962) An unsolvable problem on dominoes. Technical Report BL-30 (II-15), Harvard Computation Laboratory

Watanabe S (1961) 5-symbol 8-state and 5-symbol 6-state universal Turing machines. J ACM 8:476–483MATHCrossRef

Winfree E (1996) On the computational power of DNA annealing and ligation. In: Lipton RJ, Baum EB (eds) DNA based computers, volume 27 of DIMACS. American Mathematical Society, Providence, RI, pp 199–221

Winfree E (1998) Simulations of computing by self-assembly. Technical Report CS-TR:1998.22, Caltech

Winfree E (2006) Self-healing tile sets. In: Chen J, Jonoska N, Rozenberg G (eds) Nanotechnology: science and computation, Springer

Winfree E, Bekbolatov R (2004) Proofreading tile sets: Error-correction for algorithmic self-assembly. In: Chen J, Reif J (eds) DNA computing 9 volume LNCS 2943. Springer-Verlag, Berlin Heidelberg, pp 126–144

Winfree E, Liu F, Wenzler LA, Seeman NC (1998) Design and self-assembly of two-dimensional DNA crystals. Nature 394:539–544CrossRef

Wright MC, Joyce GF (1997) Continuous in vitro evolution of catalytic function. Science 276:614–617CrossRef

Yokobayashi Y, Weiss R, Arnold FH (2002) Directed evolution of a genetic circuit. Proc Nat Acad Sci USA 99:16587–16591CrossRef

Title: How crystals that sense and respond to their environments could evolve
Authors: Rebecca Schulman
Erik Winfree
Publication date: 01-06-2008
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2008
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-007-9046-8

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 2/2008

Foreword

Experimental implementation and analysis of a DNA computing readout method based on real-time PCR with TaqMan probes

Unravel four hairpins!

Automating the DNA computer: solving n-Variable 3-SAT problems

Spiking neural P systems with extended rules: universality and languages

On length-separating test tube systems

Premium Partner