CaltechAUTHORS
  A Caltech Library Service

Fast Algorithmic Self-assembly of Simple Shapes Using Random Agitation

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. http://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: http://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:
URLURL TypeDescription
https://doi.org/10.1007/978-3-319-11295-4_2DOIArticle
https://link.springer.com/chapter/10.1007/978-3-319-11295-4_2PublisherArticle
http://rdcu.be/ujFqPublisherFree ReadCube access
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:
Funding AgencyGrant Number
National Science Council (Taipei)101-2221-E-002-122-MY3
NSFCCF-0832824
NSFCCF-1317694
NSFCCF-1219274
NSFCCF-1162589
NSFCCF-1213127
NSFCCF-0832824
NSFCCF-1317694
Record Number:CaltechAUTHORS:20170719-124844220
Persistent URL:http://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:19 Jul 2017 20:24

Repository Staff Only: item control page