Chen, Ho-Lin and Doty, David and Holden, Dhiraj and Thachuk, Chris and Woods, Damien and Yang, Chun-Tao (2014) Fast Algorithmic Self-assembly of Simple Shapes Using Random Agitation. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.8727. Springer , pp. 20-36. ISBN 978-3-319-11295-4. https://resolver.caltech.edu/CaltechAUTHORS:20170719-124844220
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170719-124844220
Abstract
We study the power of uncontrolled random molecular movement in a model of self-assembly called the nubots model. The nubots model is an asynchronous nondeterministic cellular automaton augmented with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on nubots showed how to build simple shapes such as lines and squares quickly—in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to push or pull large objects quickly, and only at a time and place of the programmers’ choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitation-free (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement.
Item Type: | Book Section | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||||
Additional Information: | © 2014 Springer. Supported by NSC grant number 101-2221-E-002-122-MY3. Supported by National Science Foundation grants 0832824 & 1317694 (The Molecular Programming Project), CCF-1219274, CCF-1162589. Supported by NSF grant CCF-1219274. Supported by NSF grant CCF/HCC-1213127. Supported by National Science Foundation grants 0832824 & 1317694 (The Molecular Programming Project), CCF-1219274, CCF-1162589. Supported by NSC grant number 101-2221-E-002-122-MY3. A special thanks to Erik Winfree for many insightful and helpful discussions on the model and constructions. We also thank Robert Schweller, Matthew Cook and Andrew Winslow for discussions on the model and problems studied in this paper. | ||||||||||||||||||
Funders: |
| ||||||||||||||||||
Series Name: | Lecture Notes in Computer Science | ||||||||||||||||||
Issue or Number: | 8727 | ||||||||||||||||||
Record Number: | CaltechAUTHORS:20170719-124844220 | ||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170719-124844220 | ||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||
ID Code: | 79210 | ||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||
Deposited By: | Ruth Sustaita | ||||||||||||||||||
Deposited On: | 19 Jul 2017 20:24 | ||||||||||||||||||
Last Modified: | 03 Oct 2019 18:17 |
Repository Staff Only: item control page