ISCID News Editor
Moderator
Member # 1417
|
posted 07. December 2004 02:50
PLoS Biology, December 7 2004
Using Biology to Create Complex Patterns
DOI: 10.1371/journal.pbio.0020448
[Another excellent synopsis courtesy of PLoS. See references to the full paper at bottom - ISCID News Editor]
Published December 7, 2004
Copyright: © 2004 Public Library of Science. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Citation: (2004) Using Biology to Create Complex Patterns. PLoS Biol 2(12): e448.
In his seminal exploration of the properties of living organisms, What Is Life?, Erwin Schroedinger concluded that life depends in large part on storing and processing information. For genetic material to carry the diverse instructions required for living processes, he proposed, it must be stored in an aperiodic crystal. Just nine years later, it was clear that DNA is indeed an aperiodic crystal and that genetic information is conveyed through this irregular pattern. Much like computers, biological systems are programmed to follow a precise set of rules, or algorithms ^, to store information and solve problems. These biological algorithms direct all manner of biochemical processes to create complex patterns and structures by chemically modifying and assembling individual components.
Of course, cells use biochemical circuits not electronic circuits. Single tubulin ^ proteins, for example, follow precise rules of chemistry and physics to spontaneously self-assemble, or polymerize, into the microtubules essential for cell transport and motility. The proteins' binding interactions effect rules that specify how the pieces fit together to form the resulting structure. They also specify when and how tubulins assemble from a nucleation complex—a molecular algorithm governing the logic of polymerization. These complex structures self-assemble with remarkably few mistakes. Though considered quite simple, little is understood about the principles that govern programmable structural order underlying this type of spontaneous self-assembly.
[ISCID Editor's Note: All cell proteins, including the protiens that constitute tubulin, are ribosomally synthesised based on the information in RNA, which is derived from the genetic information in DNA via DNA polymerase transcription. The process described here is the spontaneous self assembly of the multiple tubulin proteins so produced (ribosomally), to comprise the 13 bound tubulin filaments of a microtubule ^. To learn about some of the reasons why 'little is understood about the principles that govern programmable structural order underlying this type of spontaneous self-assembly' and the 'precise rules of chemistry and physics' that guide this self assembly, refer to the entry for chirality ^ in the ISCID Encyclopedia of Science and Philosophy. The molecular subunits of Ribosomes themselves also self assemble.]
In crystals, the simplest example of spontaneous self-assembly, subunits of the whole are arranged in a repeating pattern that extends indefinitely in all directions. If you know the position of one unit in the pattern, you can tell the exact position of every other unit. In a new study, Rothemund and colleagues use DNA to show that crystal growth can be programmed to create specific aperiodic patterns. Inspired by a model of crystal growth as a computational process, they have programmed DNA molecules to act as molecular building blocks, arranging themselves according to local rules that in turn create a complex global pattern. The resulting two-dimensional structures, which self-assemble from knotted DNA complexes (called tiles), grow to create a fractal ^ pattern known as a Sierpinski triangle ^. These DNA structures—neither periodic (as in quartz), nor random (as in glass), nor pseudorandom (as in quasicrystals with “forbidden” five-fold symmetries)—demonstrate a form of self organization in crystalline materials determined by programmable growth rules, and are hence dubbed “algorithmic crystals.”
How can such growth algorithms be encoded in biological molecules? The rules of chemical base-pairing follow regular, predictable patterns, allowing the authors to use DNA to determine the tiles' binding interactions.
Desired binding interactions between tiles were programmed by endowing each tile with single-stranded “sticky ends” whose sequence was complementary to the sticky ends of tiles it should stick to. Each tile was either white (0) or black (1): a black tile can fit at any site where the two neighboring tiles are opposite colors, while a white tile can fit at any site where the two neighboring tiles are the same color. Logically, the new tile's color is the exclusive-or ( XOR ^ ) of the tiles in the previous layer.
That such logical layer-by-layer iteration of XOR computations will produce the Sierpinski triangle is well known. What's remarkable is that DNA molecules can be programmed to grow according to this logic. With this programmable algorithmic crystal, Rothemund and colleagues demonstrate a method for designing DNA molecules capable of implementing any pattern of abstract logical tiles. What's more, the authors argue, any algorithmic crystal growth process can, in principle, be experimentally investigated using DNA self-assembly.
[ISCID Editor's Note: DNA is synthesised by replication involving the unwinding and separation of the two RNA strands into leading and lagging strands by DNA Helicase, and the synthesis of those two strands into new DNA copies via DNA polymerase III and I and other components such as primase, which sequence/bind new nucleotides onto the separated strands. The 'self assembly' referred to here is contextual.]
So how is algorithmic self-assembly related to biology? Like the algorithmic crystals, many of the self-assembled structures in biology are ordered but aperiodic. The hope is that the theoretical insights of computer science—well-honed for describing, analyzing, and programming computational systems—can direct investigations of biochemical self-assembly and information processing. And with a method for demonstrating how simple chemical and physical elements can create complex organization, Rothemund and colleagues have added a concrete experimental framework to bolster that work. (For more on DNA and complexity, see “The Emergence of Complexity: Lessons from DNA” by Chengde Mao.)
Read the original synopsis at PLoS Biology
FROM/ON THE RESEARCH PAPER:
Algorithmic Self-Assembly of DNA Sierpinski Triangles
Paul W. K. Rothemund, Nick Papadakis, Erik Winfree
Abstract
Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we report the molecular realization, using two-dimensional self-assembly of DNA tiles, of a cellular automaton whose update rule computes the binary function XOR and thus fabricates a fractal pattern—a Sierpinski triangle—as it grows. To achieve this, abstract tiles were translated into DNA tiles based on double-crossover motifs. Serving as input for the computation, long single-stranded DNA molecules were used to nucleate growth of tiles into algorithmic crystals. For both of two independent molecular realizations, atomic force microscopy revealed recognizable Sierpinski triangles containing 100–200 correct tiles. Error rates during assembly appear to range from 1% to 10%. Although imperfect, the growth of Sierpinski triangles demonstrates all the necessary mechanisms for the molecular implementation of arbitrary cellular automata ^ . This shows that engineered DNA self-assembly can be treated as a Turing-universal biomolecular system, capable of implementing any desired algorithm for computation or construction tasks.
Received September 14, 2004; Accepted October 5, 2004; Published December 7, 2004
DOI: 10.1371/journal.pbio.0020424
Copyright: © 2004 Rothemund et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abbreviations: AFM, atomic force microscopy; aTAM, abstract Tile Assembly Model; 1D, one-dimensional; 2D, two-dimensional; DNA, deoxyribonucleic acid; DAE-E, double-crossover, antiparallel, even intramolecular spacing, even intermolecular spacing; DAO-E, double-crossover, antiparallel, odd intramolecular spacing, even intermolecular spacing; kTAM, kinetic Tile Assembly Model; PCR, polymerase chain reaction; RAM, random-access memory; XOR, exclusive or
Academic Editor: Anne Condon, University of British Columbia
*To whom correspondence should be addressed. E-mail: winfree@caltech.edu
Citation: Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic Self-Assembly of DNA Sierpinski Triangles. PLoS Biol 2(12): e424.
Introduction - Selected Content
How is complex organization produced and maintained by physical processes? One may look to biology, where we find the most sophisticated organization of matter, often spanning more than 24 orders of magnitude from component molecules (0.1 attograms) to entire organism (100 kilograms). This organization is information-based: DNA sequences refined by evolution encode both the components and the processes that guide their development into an organism—the developmental program.[ISCID Editor's Note:Chance based CSI? Hmm...] For a language to describe this carefully orchestrated organization, it is tempting to turn to computer science, where the concepts of programming languages, data structures, and algorithms are used to specify complex organization of information and behavior. Indeed, the importance of universal computation for autonomous fabrication tasks was recognized in von Neumann's seminal work on self-reproducing automata, where he postulated a universal constructor that, by reading an input tape specifying an algorithm for what to build, could carry out the commands necessary to construct an arbitrary object (von Neumann 1966). If algorithmic concepts can be successfully adapted to the molecular context, the algorithm would join energy and entropy as essential concepts for understanding how physical processes create order. Unfortunately, the study of molecular algorithms has been hampered by the lack of suitable physical systems on which to hone such a theory: nature provides us with elementary chemical reactions too simple to program, full-blown life too complex to use as a model system, and few systems in between. This gap may be explored by synthesizing programmable biochemical systems in vitro ^ , where we can implement and study a variety of molecular algorithms ranging gradually from simple to complex.
Biomolecular self-assembly is particularly attractive for the exploration of molecular algorithms that control nanofabrication tasks. Attesting to its power, self-assembly is used pervasively in biology to create such structures as virus capsids, microtubules, and flagella. In each case, the binding interactions between a small number of protein species is sufficient to dictate the form of the final structure, often via a complex sequence of cooperative assembly steps. This can be viewed loosely as a form of programmable nanofabrication, where the program is the set of molecular species involved. For synthetic approaches, Seeman (1982, 2003) has demonstrated that DNA provides an alternative to protein that can be readily programmed by Watson–Crick complementarity. A seminal paper by Adleman (1994) used one-dimensional (1D) DNA self-assembly to operate as a finite-state machine, establishing the first experimental connection between DNA self-assembly and computation. This work inspired a theoretical proposal (Winfree 1996) that builds on Wang's (1961, 1962) embedding of computation in geometrical tilings to show that two-dimensional (2D) self-assembly of DNA can perform Turing-universal computation—which implies that any algorithm can in principle be embedded in, and guide, a potentially aperiodic crystallization process. In this “algorithmic self-assembly” paradigm, a set of molecular Wang tiles is viewed as the program for a particular computation or molecular fabrication task (Reif 1999; Rothemund and Winfree 2000; Adleman et al. 2001). (This framework differs from previous approaches relating tiling theory to crystalline ground-states [Radin 1985] in that kinetic phenomena are essential here.) Whereas 1D algorithmic self-assembly offers limited computational power (Winfree et al. 1998b) and has been experimentally demonstrated (Adleman 1994; Mao et al. 2000), 2D algorithmic self-assembly offers not only new capabilities for computation and construction, but also presents a new range of physical phenomena and experimental challenges as well.
A natural Turing-universal model of computation that can be implemented by 2D algorithmic self-assembly is the class of 1D cellular automata. A simple but interesting choice for the local cellular automaton rule is the exclusive–or (XOR) function: at each time step, each cell is computed as the XOR of its two neighbors. Beginning with a row of all ‘0's punctuated by a single central ‘1,' snapshots of the cellular automaton's state at successive time steps may be stacked one on top of the other to produce a space–time history identical to Pascal's triangle (Bondarenko 1993) modulo 2 (Figure 1A, left), which is a discrete form of Sierpinski's fractal triangle (Figure 1A, right). To represent this cellular automaton as a tiling, each local context present in the space–time history must have a corresponding Wang tile whose shape represents the input and output occurring at that location (Figure 1B). Thus, we need four tiles, one for each entry of the truth table for XOR, and a linear input row representing the initial state of the cellular automaton (Figure 1C). Given these tiles and the input row there is a unique way to tile the upper half-plane without mismatches or missing tiles—the Sierpinski Tiling—which reproduces the cellular automaton's space–time history (Figure 1D).
Figure 1. [Figure Notes ommitted - ISCID News Editor]
Whereas execution of a cellular automaton occurs perfectly and synchronously, molecular self-assembly is asynchronous and may have many types of errors. To be successful, an implementation of cellular automata by molecular tiling must address four challenges: (1) The abstract tiles must be translated into molecules (molecular tiles) that readily form 2D crystals. (2) Molecular tiles must be programmed with specific binding domains that match the logic of the chosen abstract tiles. (3) The binding of molecular tiles must be sufficiently cooperative to enforce the correct order of assembly and prevent errors. (4) Assembly of molecular tiles must occur on a specified nucleating structure, and spurious nucleation must be suppressed. These properties are necessary and sufficient for implementing not only the XOR cellular automaton, but also any other 1D cellular automaton. All four have been shown individually: several types of DNA Wang tiles have been designed and shown to grow into micron-scale 2D periodic crystals (Winfree et al. 1998a; Mao et al. 1999; LaBean et al. 2000b); the interactions between these tiles can be programmed by sequence-specific hybridization (Winfree et al. 1998a; Mao et al. 2000); cooperative binding of multiple domains ensures specificity—the right tile attaches in the right place (Winfree et al. 1998b; Mao et al. 2000); and input to the self-assembly process can be provided by a single-stranded template (LaBean et al. 2000a; Yan et al. 2003a). Here we demonstrate, via self-assembly of Sierpinski triangles, that all four challenges can be simultaneously overcome, thus establishing all the mechanisms necessary to implement arbitrary cellular automata. The Sierpinski tiling, then, gives rise to a new type of aperiodic crystal—an algorithmic crystal.
Results
Modeling Tile-Based Self-Assembly
Preventing the types of errors mentioned above may seem impossible. For example, if a single binding domain is strong enough to hold a tile in place (red arrows in Figure 1C), then one would expect roughly 33% of tiles to mismatch with tiles in the layer below. Simulations of self-assembly shed light on how to avoid such dire circumstances. We use two levels of abstraction that isolate and address critical issues for the design and analysis of our algorithmic self-assembly experiments. How crystal morphology and patterning can be programmed by tile design in an inherently asynchronous assembly process is addressed by the abstract Tile Assembly Model (aTAM) (Winfree 1996, 1998a). To explore how physical parameters, such as tile concentration and temperature, affect crystal growth and influence error rates, we use the kinetic Tile Assembly Model (kTAM) based on reversible tile association and dissociation rates (Winfree 1998a).
Control over the order of assembly is obtained by exploiting the cooperativity of binding. The aTAM models cooperativity via a threshold, τ, representing the number of bonds that must be made for an association event to be thermodynamically stable: a tile may be added to a crystal if at least τ binding domains match the existing crystal. Black arrows in Figure 1C indicate four potential association events that could occur at τ = 2; red arrows indicate two additional association events that would be permitted at τ = 1, but not at τ = 2. Simulation of cellular automata ^ is designed to work at τ= 2. Isolated tiles cannot associate at τ = 2 and so growth and computation must begin with a preformed nucleating structure (Figure 1C, blue) that represents the input to the computation. Importantly, at τ = 2 no tile may be added until both preceding tiles are already present, guaranteeing a deterministic outcome despite the asynchronous order of events. Thus, assembly from an input row containing a solitary ‘1' domain produces the Sierpinski triangle pattern (Figures 1D and 2A) regardless of the order in which permitted associations occur. If a small number of additional τ = 1 associations are permitted to occur, then mismatches between neighboring tiles (mismatch errors) may result. In this case, or if there are several ‘1's in the input row, the resulting pattern can appear to be qualitatively different: owing to propagation of information and the linearity of XOR, the resulting pattern is the superposition of Sierpinski triangles initiated at input ‘1's and at mismatch error sites (see Figure 1E).
Figure 2. [Figure Notes ommitted - ISCID News Editor]
.
.
.
Design and Preparation of DNA Tiles
Abstract Wang tiles are implemented as DNA tiles according to the scheme described earlier (Winfree et al. 1998a): each molecular Wang tile is a DNA double-crossover molecule (Fu and Seeman 1993) with four sticky-ends (5-base single-stranded overhangs) that serve as the programmable binding domains. We rendered the four Sierpinski rule tiles using two types of double-crossover molecule, known as DAE-E and DAO-E molecules (Winfree 1996), resulting in two independent molecular implementations (Figure 4, sequences are as given in Figures S4–S7). The DAE-E Sierpinski tile set (Figure 4A) consists of four molecular tiles, each composed of five strands whose sequences were designed to minimize the potential for forming alternative structures (Seeman 1990), as confirmed by non-denaturing gel electrophoresis (Figure S8).
Figure 4. [Figure Notes ommitted - ISCID News Editor]
Since untemplated crystals were not expected to produce recognizable Sierpinski triangles, it was necessary to create a proper nucleating structure to provide the initial input for the algorithmic self-assembly. Previous work using DNA tiles to self-assemble an initial boundary had proven to be difficult (Schulman et al. 2004), so in this work we took an alternative approach of using assembly PCR (Stemmer et al. 1995) to create a long single-stranded molecule which could serve as a scaffold (LaBean et al. 2000a; Yan et al. 2003a) for the assembly of a row of input tiles (Figures 4A and S9–S11). Because this nucleating strand serves as the bottom of these tiles, only four strands are needed to assemble the input tiles, and an additional capping strand is used to form a double-helix between input tiles on the nucleating strand. By doping the assembly PCR mix with a small fraction of the strands coding for an input tile outputting a single ‘1,' we ensure that each nucleating structure contains a few randomly located sites from which a Sierpinski triangle should grow.
The DAO-E Sierpinski tile set (Figure 4B) consists of six molecular tiles, due to peculiarities of the DAO-E motif. First, consideration of the 5′ and 3′ orientation of strands—particularly the fact that the sticky ends at the top and bottom of a DAO-E tile have opposite polarity—demands that each tile binds only to “upside-down” neighbors, resulting in layers of tiles with alternating orientation, which we refer to here as R-type and S-type tiles. Furthermore, the sugar–phosphate backbone of the DAO-E tiles has a dyad symmetry axis, implying that the R-01 and S-01 tiles each can play the roles of both the T-01 and T-10 tiles. Likewise, the R-00, R-11, S-00, and S-11 tiles can each bind in two orientations in a site where both inputs match.
In order for the nucleating structure for the DAO-E lattice to assemble onto a long PCR-generated nucleating strand, the tiles on the input row must be of the DAE-O variant. Further, we simplified the construction so that all nucleating strands contain the same repetitive sequence, but the input tile strands are doped with a fraction of strands containing a ‘1' sticky-end, and again the nucleating structure contains a few randomly located sites from which a Sierpinski triangle should grow.
Self-Assembly of DNA Sierpinski Triangles [ISCID Editor's Note: The in-vitro side of things starts about here...]
In principle, two approaches can be taken for initiating algorithmic self-assembly of DNA tiles. In the preformed tile approach, each tile is prepared separately by mixing a stoichiometric amount of each component strand in the hybridization buffer and then annealing from 90 °C to room temperature over the course of several hours. The nucleating structure is similarly prepared by annealing the nucleating strand with input tile and capping strands. Then the rule tiles and nucleating structure are mixed together at a temperature appropriate for crystal growth. In the bulk annealing approach, the nucleating strand, the capping and input tile strands, and the strands for all rule tiles are initially mixed together and then annealed. Since, at the concentrations we use, the tiles themselves have melting temperatures between roughly 60 °C and 70 °C while the crystals have a melting temperature within a few degrees of 40 °C (Figure S12), during annealing the tiles themselves will first form, and only later will the fully formed tiles assemble into crystals, presumably growing from the nucleating structure prior to overcoming the barrier to spontaneous nucleation. Both approaches work, but because of the convenience of the bulk annealing approach, all samples reported here were prepared using that method, with a final concentration of 0.2 μM each tile. After self-assembly in solution, samples are deposited onto mica and imaged by tapping mode atomic force microscopy (AFM).
Results for the DAE-E tile set are shown in Figures 5 and S13–S15. The majority of DNA crystals we observed were similar to those in Figure 5A: in addition to many small and indistinctly formed fragments, larger crystals are typically thin and long (up to several microns) with ‘1' tiles clearly visible. Crystals consisting exclusively of VE-00 tiles (upper arrow in Figure 5A) were particularly common; further investigation revealed that some (perhaps all) of these crystals formed as DNA tubes, and subsequently broke open and lay flat on the mica (see Figure S15; Rothemund et al. 2004). A ‘011011'-striped pattern (lower arrow in Figure 5A) was also quite common; it can be constructed from the RE-01, SE-10, and UE-11 tiles. Growth may have been biased to form ‘011011' patterns by the depletion of VE-00 tiles, a stoichiometric disproportionation of tiles, due to growth of tubes early during annealing. Crystals that clearly grew from the nucleating structure were also apparent; Figure 5B–5E show examples with particularly few errors. In several of these crystals, individual tiles could be identified and a compatible arrangement of abstract tiles (and thus errors) could be determined. Large error-free domains containing more than eight rows of perfect Sierpinski triangle were observed. In these examples, the mismatch error rate was about 2% over a wider selection of fragments, the error rate varied between 1% and 10%. We partly attribute this variation to changes in the physical conditions during annealing that result in a disproportionation of tiles. In addition to errors due to incorporation of the wrong tile, we also observed missing tiles and lattice dislocations. Frequently, as in Figure 5E, the identity of obscured or missing tiles was deduced from the neighboring tiles by assuming correct information propagation (the imperfection often being caused by sample preparation or by interaction with the AFM tip rather than by errors during assembly).
.
.
.
Discussion
The self-assembly of DNA Sierpinski triangles demonstrates all four features necessary for Turing-universal computation by crystallization: formation of extended crystals, programmable interactions between DNA tiles determined by sticky-end sequences, selective associations of tiles enforced by the cooperative binding of more than one sticky end, and controlled nucleation of growth initiated by a template containing input information. This tiling approach could be used to implement other cellular automaton rules. Given a set S of possible states for the memory cells and an update function f : S × S S, one can create a set of |S|2 tiles according to the scheme of Figure 1B, one tile for each possible input pair. The need for binding specificity limits the number of sticky-end sequences (and hence |S|) to about 20 for the DAO-E and DAE-E tile designs used here, but this is already sufficient to implement several known universal Turing machines and cellular automata (Lindgren and Nordahl 1990; Rogozhin 1996). A larger set of sticky-end sequences could be achieved by redesigning the DNA tile molecules to use longer sticky-ends, provided that the melting temperatures of tiles and crystals remain well separated. Thus, DNA crystallization is programmable and Turing-universal. Furthermore, for fabrication purposes, computation by self-assembly could be used to control the direction and extent of growth, thus allowing arbitrary shapes to be created efficiently (Soloveichik and Winfree 2005)—demonstrating that algorithmic self-assembly is not limited to the simulation of cellular automata or Turing machines.
The main obstacle currently limiting attempts to compute or fabricate using algorithmic self-assembly is the presence of several types of errors. We observed lattice dislocations, a structural error; untemplated tubes and untemplated crystals, an error in the control of nucleation; and mismatched tiles, an error in the growth process. Accurate quantitative models of algorithmic self-assembly will be valuable for developing methods to control and reduce such errors. The kTAM simulations described here, while qualitatively insightful, predict mismatch error rates an order of magnitude smaller than those observed—motivating experimental measurements of errors and refinement of the model. Although it may be possible to reduce the error rates by carefully controlling the assembly conditions, a more promising route is the creation of fault-tolerant tile sets that perform the same logic (Winfree and Bekbolatov 2004; Chen and Goel 2005; Reif et al. 2005; Schulman and Winfree 2005). For the same assembly conditions, and thus roughly the same growth rate, the kTAM predicts that these tile sets can reduce the mismatch error rates by many orders of magnitude—a conclusion likely to hold in spite of inaccuracies in the model.
Self-assembly has been touted as a possible successor to photolithography, a basis for nanotechnology and a route to complexity in chemistry (Whitesides et al. 1991). Algorithmic self-assembly—whether using DNA tiles as demonstrated here or using appropriately designed small molecules, proteins, or even macroscopic tiles (Bowden et al. 1997; Rothemund 2000)—extends the range of structures accessible by bottom-up fabrication techniques. For example, an abstract tile set that enumerates binary numbers—a binary counter—uses just four tiles, yet it can be used to define the size of self-assembled structures (Rothemund and Winfree 2000), thus addressing the synthetic chemistry challenge of creating monodisperse particles with programmable size. Furthermore, attachment of suitable logic gates to ‘0' and ‘1' tiles would yield a demultiplexer for a RAM circuit. This and other interesting digital circuits (Cook et al. 2004) might be created by using algorithmic crystals as templates for further chemical processing (Braun et al. 1998; Yan et al. 2003b).
The Turing-universality of self-assembly allows theoretical insights from computer science to be applied to self-assembly. For example, many questions phrased using the aTAM—such as “Will a certain tile type, say tile type #5, ever be incorporated into the assembly?” or “Will the final assembled shape have 4-fold symmetry?”—are formally undecidable as a consequence of the undecidability of the halting problem (Turing 1936; Adleman et al. 2002). This suggests that there exists no generally applicable method for predicting the behavior or properties of crystals. A concrete instance of this dilemma is whether quasicrystals' 5-fold symmetry and aperiodicity could arise from self-assembly. Crystallographers have argued that, if so, definitions of order based on X-ray diffraction must be modified to include the new structures (Senechal 1995). The growth of Sierpinski triangles, demonstrated here, shows unequivocally that self-assembly can create aperiodic structures based on local rules. Furthermore, traditional methods of measuring order, such as X-ray diffraction, will not recognize order that exists in certain algorithmic crystals. For example, an algorithmic crystal simulating a pseudo-random number generator (Wolfram 1986; Jen 1990; Knuth 1997) would appear disordered, yet each molecule would be precisely and deterministically positioned. Thus, the growth of algorithmic crystals motivates the use of algorithmic definitions of order (Kolmogorov 1965; Levin 1984; Bennett 1995) that generalize crystallography (Mackay 1975).
Finally, we ask whether the study of algorithmic self-assembly might further our understanding of biological self-assembly. Algorithmic crystals composed of simple sugar-based tiles have appeared in science fiction as a form of life (Egan 1995); indeed, the simplicity and versatility of crystalline self-assembly suggests that templating, as a basis for simple organisms (Penrose and Penrose 1957; Cairns-Smith 1971), may be more natural than previously supposed. However, examination of self-assembly in modern organisms reveals many mechanisms beyond those considered here, including conformational changes, dissipative mechanisms such as ATP hydrolysis, and interactions with genetic regulatory networks—themselves biochemical information processors.The development of a theory of molecular algorithms that encompasses these additional mechanisms, if successful, will deepen our understanding of the complex processes found in nature, their fundamental limits, and their remarkable potential.
[Emphases added by ISCID News Editor]
[Link-underlined terms with ^ indicate linked entry in ISCID Encyclopedia of Science and Philosophy as added by ISCID News Editor]
To read the entire paper about this astonishing experiment, go to PLoS biology
[ 07. December 2004, 23:26: Message edited by: ISCID News Editor ]
IP: Logged
|
Printer-friendly view of this topic