Controlling Nucleation
A major source of potential errors is caused by spurious nucleation, or the formation of an assembly separate from and not containing the designated seed structure. Typically, systems are designed so that growth begins from a seed which essentially provides the initial input to the algorithm that directs the growth of the assembly. Thus, when an assembly forms in the absence of the seed, it has the possibility of "running the algorithm" starting at a random point and as though from a random input (and perhaps even running it in reverse as well from that point).
In order to combat the problem of spurious nucleation, Schulman and Winfree [1] designed systems which were able to quickly grow from seeded assemblies, but which were highly unlikely to form large unseeded assemblies due to high kinetic barriers. The "zig-zag" systems they introduced grow as fixed-width ribbons (i.e. long and thin rectangles) such that to increase the length of the strip, the assembly must grow a row first in one direction across the growing end, and then the next row grows back in the opposite direction. They were able to provide simulations to prove the effectiveness of their systems at resisting spurious nucleation and yet growing relatively quickly and correctly from seeds.
To further improve the ability of experimentalists to create seed structures, especially those which contain a reasonable amount of information used to direct a growing assembly, in [2] Barish, Schulman, Rothemund, and Winfree demonstrated, in a wet-lab, the use of DNA origami (introduced by Rothemund in [3]) to serve as a seed structure. They were able to design DNA origami seeds which displayed up to 32 glues and binding sites to which tiles could attach, and these seeds provided the relatively easy production of high-yield, low error-rate tile assembly systems. They were able to successfully demonstrate the use of DNA origami seeds to nucleate the growth of three different algorithmically directed systems. (See geometrically complex tiles for another example of tiles created using DNA origami.)
In a paper by Patitz, Rogers, Schweller, Summers, and Winslow[4], it is proven that Turing-universal computation is possible in the temperature-1 2HAM when a single negative-strength glue is also permitted. Without such a glue, spurious nucleation would seemingly cause the vast majority of produced supertiles to nucleate as encodings of random configurations of the Turing machine and run nonsense computations both forward and backward. This uncountably large sea of undesired supertiles would then dilute supertiles encoding the desired computation. The construction utilizes small “jackhammer” supertiles that break up the sea of undesired supertiles into constant-sized terminal supertiles (from a constant-sized set). This “jackhammering” is carried out on a “zig-zag” simulation of a modified version of the input Turing machine.
This paper[4] also presents a construction of a supertile in the 3D 2HAM with tile complexity \(O(log^2 n)\) by using a cyclic counter which combines two forward growth counters that seed each other upon completion. Erroneous backward growth halts, while forward growth proceeds until the crashing into the error to yield a full-length terminal supertile. The construction is finished by proving there exists an aperiodic 3D 2HAM system.
References
- ↑
Schulman, Rebecca, Winfree, Erik - Programmable Control of Nucleation for Algorithmic Self-Assembly
- SIAM J. Comput. 39(4):1581--1616, Philadelphia, PA, USA, @dec 2009
- http://dx.doi.org/10.1137/070680266
BibtexAuthor : Schulman, Rebecca, Winfree, Erik
Title : Programmable Control of Nucleation for Algorithmic Self-Assembly
In : SIAM J. Comput. -
Address : Philadelphia, PA, USA
Date : @dec 2009
- ↑
Barish, Robert D., Schulman, Rebecca, Rothemund, Paul W. K., Winfree, Erik - {An information-bearing seed for nucleating algorithmic self-assembly}
- Proceedings of the National Academy of Sciences 106(15):6054--6059, @apr 2009
- http://dx.doi.org/10.1073/pnas.0808736106
BibtexAuthor : Barish, Robert D., Schulman, Rebecca, Rothemund, Paul W. K., Winfree, Erik
Title : {An information-bearing seed for nucleating algorithmic self-assembly}
In : Proceedings of the National Academy of Sciences -
Address :
Date : @apr 2009
- ↑
Paul W. K. Rothemund - {Folding DNA to create nanoscale shapes and patterns}
- ↑ 4.0 4.1
Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Andrew Winslow - Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly