An official website of the United States government
Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information. In particular, for all n∈N , we assemble n×n squares using O(2log∗n) tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with O(2log∗K) tiles, where K denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct n×O(1) rectangles using only O(logn/loglogn) tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature. These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.
more »
« less
Simulation of the Abstract Tile Assembly Model Using Crisscross Slats
The abstract Tile Assembly Model (aTAM) provides an excellent foundation for the mathematical study of DNA-tile-based self-assembling systems, especially those wherein logic is embedded within the designs of the tiles so that they follow prescribed algorithms. While such algorithmic self-assembling systems are theoretically powerful, being computationally universal and capable of building complex shapes using information-theoretically optimal numbers of tiles, physical DNA-based implementations of these systems still encounter formidable error rates and undesired nucleation that hinder this theoretical potential. Slat-based self-assembly is a recent development wherein DNA forms long slats that combine together in 2 layers, rather than square tiles in a plane. In this approach, the length of the slats is key; while tiles typically only bind to 2 neighboring tiles at a time, slats may bind to dozens of other slats. This increased coordination between slats means that several mismatched slats must coincidentally meet in just the right way for errors to persist, unlike tiles where only a few are required. Consequently, while still a novel technology, large slat-based DNA constructions have been successfully implemented in the lab with resilience to many tile-based construction problems. These improved error characteristics come at a cost however, as slat-based systems are often more difficult to design and simulate than tile-based ones. Moreover, it has not been clear whether slats, with their larger sizes and different geometries, have the same theoretical capabilities as tiles. In this paper, we show that slats are capable of doing anything that tiles can, at least at scale. We demonstrate that any aTAM system may be converted to and simulated by an effectively equivalent system of slats. Furthermore, we show that these simulating slat systems can be made more efficiently, using shorter slats and a smaller scale factor, if the simulated tile system avoids certain uncommon growth patterns. Specifically, we consider 5 classes of aTAM systems with increasing complexity, from zig-zag systems which grow in a rigid pattern to the full class of all aTAM systems, and show how they may be converted to equivalent slat systems. We show that the simplest class may be simulated by slats at only a 2c × 2c scale, where c is the freely chosen coordination number of the slats, and further show that the full class of aTAM systems can be simulated at only a 5c × 5c scale. These results prove that slats have the full theoretical power of aTAM tiles while also providing constructions that are compact enough for potential DNA-based implementations of slat systems that are both capable of powerful algorithmic self-assembly and possessing of the strong error resilience of slats.
more »
« less
- Award ID(s):
- 2329908
- PAR ID:
- 10586921
- Editor(s):
- Seki, Shinnosuke; Stewart, Jaimie Marie
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Volume:
- 314
- ISSN:
- 1868-8969
- ISBN:
- 978-3-95977-344-7
- Page Range / eLocation ID:
- 3:1-3:25
- Subject(s) / Keyword(s):
- DNA origami tile-assembly self-assembly aTAM kinetic modeling computational modeling Theory of computation → Models of computation
- Format(s):
- Medium: X Size: 25 pages; 1752143 bytes Other: application/pdf
- Size(s):
- 25 pages 1752143 bytes
- Right(s):
- Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Tile‐based DNA self‐assembly is a powerful approach for nano‐constructions. In this approach, individual DNA single strands first assemble into well‐defined structural tiles, which, then, further associate with each other into final nanostructures. It is a general assumption that the lower‐level structures (tiles) determine the higher‐level, final structures. In this study, we present concrete experimental data to show that higher‐level structures could, at least in the current example, also impact on the formation of lower‐level structures. This study prompts questions such as: how general is this phenomenon in programmed DNA self‐assembly and can we turn it into a useful tool for fine tuning DNA self‐assembly?more » « less
-
Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing Machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-Dimensional systems (all assemblies are of height $$1$$) and freezing Systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using $$n$$ states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment.more » « less
-
Surface-assisted, tile-based DNA self-assembly is a powerful method to construct large, two-dimensional (2D) nanoarrays. To further increase the structural complexity, one idea is to incorporate different types of tiles into one assembly system. However, different tiles have different adsorption strengths to the solid surface. The differential adsorptions make it difficult to control the effective molar ratio between different DNA tile concentrations on the solid surface, leading to assembly failure. Herein, we propose a solution to this problem by engineering the tiles with comparable molecular weights while maintaining their architectures. As a demonstration, we have applied this strategy to successfully assemble binary DNA 2D arrays out of very different tiles. We expect that this strategy would facilitate assembly of other complicated nanostructures as well.more » « less
-
Living cells regulate the dynamics of developmental events through interconnected signaling systems that activate and deactivate inert precursors. This suggests that similarly, synthetic biomaterials could be designed to develop over time by using chemical reaction networks to regulate the availability of assembling components. Here we demonstrate how the sequential activation or deactivation of distinct DNA building blocks can be modularly coordinated to form distinct populations of self-assembling polymers using a transcriptional signaling cascade of synthetic genes. Our building blocks are DNA tiles that polymerize into nanotubes, and whose assembly can be controlled by RNA molecules produced by synthetic genes that target the tile interaction domains. To achieve different RNA production rates, we use a strategy based on promoter “nicking” and strand displacement. By changing the way the genes are cascaded and the RNA levels, we demonstrate that we can obtain spatially and temporally different outcomes in nanotube assembly, including random DNA polymers, block polymers, and as well as distinct autonomous formation and dissolution of distinct polymer populations. Our work demonstrates a way to construct autonomous supramolecular materials whose properties depend on the timing of molecular instructions for self-assembly, and can be immediately extended to a variety of other nucleic acid circuits and assemblies.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.DNA.30.3
