Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature

Published on: 2010/04/07

Abstract

We consider the problem of fault-tolerance in nanoscale algorithmic self-assembly. We employ a variant of Winfree’s abstract Tile Assembly Model (aTAM), the two-handed aTAM, in which square “tiles” – a model of molecules constructed from DNA for the purpose of engineering selfassembled nanostructures – aggregate according to specific binding sites of varying strengths, and in which large aggregations of tiles may attach to each other, in contrast to the seeded aTAM, in which tiles aggregate one at a time to a single specially-designated “seed” assembly. We focus on a major cause of errors in tile-based self-assembly: that of unintended growth due to “weak” strength-1 bonds, which if allowed to persist, may be stabilized by subsequent attachment of neighboring tiles in the sense that at least energy 2 is now required to break apart the resulting assembly; i.e., the errant assembly is stable at temperature 2. We study a common self-assembly benchmark problem, that of assembling an n × n square using O(log n) unique tile types, under the two-handed model of self-assembly. Our main result achieves a much stronger notion of fault-tolerance than those achieved previously. Arbitrary strength-1 growth is allowed; however, any assembly that grows sufficiently to become stable at temperature 2 is guaranteed to assemble into the correct final assembly of an n × n square. In other words, errors due to insufficient attachment, which is the cause of errors studied in earlier papers on fault-tolerance, are prevented absolutely in our main construction, rather than only with high probability and for sufficiently small structures, as in previous fault-tolerance studies. We term this the fuzzy temperature model of faults, due to the following equivalent characterization: the temperature is normally 2, but may drift down to 1, allowing unintended temperature-1 growth for an arbitrary period of time. Our construction ensures that this unintended growth cannot lead to permanent errors, so long as the temperature is eventually raised back to 2. Thus, our construction overcomes a major cause of errors, insufficient strength- 1 attachments becoming stabilized by subsequent growth, without requiring the detachment of strength-2 bonds that slows down previous constructions, and without requiring the careful finetuning of thermodynamic parameters to balance forward and reverse rates of reaction necessary in earlier work on fault-tolerance. Although we focus on the task of assembling an n × n square, our construction uses a number of geometric motifs and synchronization primitives that will likely prove useful in other theoretical (and, we hope, experimental) applications.

Authors

David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, and Scott M. Summers

File

Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature.pdf