An official website of the United States government
The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of shape construction, we consider an extended version of the two-handed tile assembly model, which contains positive (attractive) and negative (repulsive) interactions. As a result, portions of an assembly can become unstable and detach. In this model, we utilize fuel-efficient computation to perform Turing machine simulations for the construction of the shape. In this paper, we show how an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (based on the shape’s Kolmogorov complexity). We achieve this at O(1) scale factor in this straightforward model, whereas all previous results with sublinear scale factors utilize powerful self-assembly models containing features such as staging, tile deletion, chemical reaction networks, and tile activation/deactivation. Furthermore, the computation and construction in our result only creates constant-size garbage assemblies as a byproduct of assembling the shape.
more »
« less
Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile Assembly Model
This paper answers a long-standing open question in tile-assembly theory, namely that it is possible to strictly assemble discrete self-similar fractals (DSSFs) in the abstract Tile-Assembly Model (aTAM). We prove this in 2 separate ways, each taking advantage of a novel set of tools. One of our constructions shows that specializing the notion of a quine, a program which prints its own output, to the language of tile-assembly naturally induces a fractal structure. The other construction introduces self-describing circuits as a means to abstractly represent the information flow through a tile-assembly construction and shows that such circuits may be constructed for a relative of the Sierpinski carpet, and indeed many other DSSFs, through a process of fixed-point iteration. This later result, or more specifically the machinery used in its construction, further enable us to provide a polynomial time procedure for deciding whether any given subset of ℤ2 will generate an aTAM producible DSSF. To this end, we also introduce the Tree Pump Theorem, a result analogous to the important Window Movie Lemma, but with requirements on the set of productions rather than on the self-assembling system itself.
more »
« less
- Award ID(s):
- 2329908
- PAR ID:
- 10586931
- Publisher / Repository:
- Society for Industrial and Applied Mathematics
- Date Published:
- Page Range / eLocation ID:
- 2387-2466
- Format(s):
- Medium: X
- Location:
- Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Meeks, Kitty; Scheideler, Christian (Ed.)The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows that seeded TA is a non-committal intrinsically universal model of self-assembly. We present a single universal Tile Automata system containing approximately 4600 states that can simulate (a) the output assemblies created by any other Tile Automata system Γ, (b) the dynamics involved in building Γ’s assemblies, and (c) Γ’s internal state transitions. It does so in a non-committal way: it preserves the full non-deterministic dynamics of a tile’s potential attachment or transition by selecting its state in a single step, considering all possible outcomes until the moment of selection. The system uses supertiles, each encoding the complete system being simulated. The universal system builds supertiles from its seed, each representing a single tile in Γ, transferring the information to simulate Γ to each new tile. Supertiles may also asynchronously transition states according to the rules of Γ. This result also implies IU for pairwise asynchronous Cellular Automata.more » « less
-
Inspired by nature and motivated by a lack of top-down tools for precise nanoscale manufacture, self-assembly is a bottom-up process where simple, unorganized components autonomously combine to form larger more complex structures. Such systems hide rich algorithmic properties - notably, Turing universality - and a self-assembly system can be seen as both the object to be manufactured as well as the machine controlling the manufacturing process. Thus, a benchmark problem in self-assembly is the unique assembly of shapes: to design a set of simple agents which, based on aggregation rules and random movement, self-assemble into a particular shape and nothing else. We use a popular model of self-assembly, the 2-handed or hierarchical tile assembly model, and allow the existence of repulsive forces, which is a well-studied variant. The technique utilizes a finely-tuned temperature (the minimum required affinity required for aggregation of separate complexes). We show that calibrating the temperature and the strength of the aggregation between the tiles, one can encode the shape to be assembled without increasing the number of distinct tile types. Precisely, we show one tile set for which the following holds: for any finite connected shape S, there exists a setting of binding strengths between tiles and a temperature under which the system uniquely assembles S at some scale factor. Our tile system only uses one repulsive glue type and the system is growth-only (it produces no unstable assemblies). The best previous unique shape assembly results in tile assembly models use O(K(S)/(log K(S))) distinct tile types, where K(S) is the Kolmogorov (descriptional) complexity of the shape S.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
-
Recent advances in synthetic posttranslational protein circuits are substantially impacting the landscape of cellular engineering and offer several advantages compared to traditional gene circuits. However, engineering dynamic phenomena such as oscillations in protein-level circuits remains an outstanding challenge. Few examples of biological posttranslational oscillators are known, necessitating theoretical progress to determine realizable oscillators. We construct mathematical models for two posttranslational oscillators, using few components that interact only through reversible binding and phosphorylation/dephosphorylation reactions. Our designed oscillators rely on the self-assembly of two protein species into multimeric functional enzymes that respectively inhibit and enhance this self-assembly. We limit our analysis to within experimental constraints, finding (i) significant portions of the restricted parameter space yielding oscillations and (ii) that oscillation periods can be tuned by several orders of magnitude using recent advances in computational protein design. Our work paves the way for the rational design and realization of protein-based dynamic systems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
