Program size and temperature in self-assembly
From MaRDI portal
Abstract: Winfree's abstract Tile Assembly Model (aTAM) is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing "seed" assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an n x n square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanes, and Rothemund ("Combinatorial Optimization Problems in Self-Assembly", STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its "temperature" (the binding strength threshold required for a tile to attach).
Recommendations
Cites work
- scientific article; zbMATH DE number 3222108 (Why is no real title available?)
- Combinatorial optimization problems in self-assembly
- Complexities for Generalized Models of Self-Assembly
- Complexity of Self‐Assembled Shapes
- One-dimensional staged self-assembly
- Randomized Self-assembly for Approximate Shapes
- Randomized self-assembly for exact shapes
- Reducing tile complexity for self-assembly through temperature programming
- Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
- Running time and program size for self-assembled squares
- Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract)
- Self-assembly with geometric tiles
- Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
- Shape replication through self-assembly and RNase enzymes
- Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
- Step-assembly with a constant number of tile types
- Strict self-assembly of discrete Sierpinski triangles
- The program-size complexity of self-assembled squares (extended abstract)
- Tile Complexity of Linear Assemblies
Cited in
(33)- Size-dependent tile self-assembly: constant-height rectangles and stability
- Producibility in hierarchical self-assembly
- Convergence rates of Markov chains for some self-assembly and non-saturated Ising models
- Platform color designs for interactive molecular arrangements
- Self-assembly of any shape with constant tile types using high temperature
- Polyomino-Safe DNA Self-assembly via Block Replacement
- Minimal tile and bond-edge types for self-assembling DNA graphs
- Thermodynamic binding networks
- A domain-specific language for programming in the tile assembly model
- Toward Minimum Size Self-Assembled Counters
- Complexities for generalized models of self-assembly
- An efficient tile assembly model for maximum matching problem
- Program size and temperature in self-assembly
- On the effects of hierarchical self-assembly for reducing program-size complexity
- Running time and program size for self-assembled squares
- Reducing tile complexity for self-assembly through temperature programming
- Active tile self-assembly. I: Universality at temperature 1
- Toward minimum size self-assembled counters
- Nearly constant tile complexity for any shape in two-handed tile assembly
- Parallelism and time in hierarchical self-assembly
- The power of nondeterminism in self-assembly
- Optimal program-size complexity for self-assembly at temperature 1 in 3D
- Parallelism and time in hierarchical self-assembly
- Polyomino-safe DNA self-assembly via block replacement
- Self-assembly of Decidable Sets
- Thermodynamically favorable computation via tile self-assembly
- Small tile sets that compute while solving mazes
- Algorithmic DNA Self-assembly
- Optimal program-size complexity for self-assembled squares at temperature 1 in 3D
- On the behavior of tile assembly system at high temperatures
- An introduction to tile-based self-assembly
- Self-assembly with geometric tiles
- On the behavior of tile assembly system at high temperatures
This page was built for publication: Program size and temperature in self-assembly
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494811)
