Program Size and Temperature in Self-Assembly
Journal
Algorithmica
Journal Volume
72
Journal Issue
3
Pages
884-899
Date Issued
2014
Author(s)
Abstract
Winfree’s abstract Tile Assembly Model 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 \times n$$n×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 et al. (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).
Type
journal article