A Caltech Library Service

Active Self-Assembly of Simple Units Using an Insertion Primitive

Dabby, Nadine and Chen, Ho-Lin (2013) Active Self-Assembly of Simple Units Using an Insertion Primitive. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, pp. 1526-1536. ISBN 978-1-61197-251-1.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


While computer science has given us a framework for determining the complexity and difficulty of solving computational problems, we do not yet have a theoretical framework for knowing what actions, behaviors, and life-like qualities can emerge from a given set of simple modular units. There has been much interest in developing models for programming active self-assembly processes in both the reconfigurable robotics community and the nanotechnology community. With respect to materials science and nanotechnology, the models proposed to date are either not yet implementable with our current understanding of synthetic chemistry or those that are implementable are limited to a set of features that do not capture the power of active components. Prior implementable models of molecular assembly only considered the passive behaviors of attaching and detaching from a complex. Inspired by the algorithmic tile assembly model [Winfree, 1996] and the graph grammar assembly model [Klavins et al., 2004], we describe a formal model for studying the complexity of self-assembled structures with active molecular components. In particular, we add an insertion primitive and we show a direct mapping of our model to a molecular implementation using DNA. We show that the expressive power of this language is stronger than regular languages, but at most as strong as context free grammars. Here, we explore the trade-off between the complexity of the system (in terms of the number of unit types), and the behavior of the system and speed of its assembly. We find that we can grow a line of any given length n in expected time O(log^3 n) using O(log^2 n) monomers. If we grow a line with k insertion rules, either the expected final length is infinite or the expected length at time t is at most (2t+2)^k^2, which is polynomial in t.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2013 SIAM. Research supported by an NSF Graduate Research Fellowship, NSF grant CCF-0829805, and the Molecular Programming Project under NSF grant 0832824. Research supported by NSC grant number 101-2218-E-002-007-, National Taiwan University Electrical Engineering Department, NSF grant CCF-0829805, the Molecular Programming Project under NSF grant CCF-0832824, and the Caltech Center for the Mathematics of Information (CMI).
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
National Science Council (Taipei)101-2218-E-002-007
Center for the Mathematics of Information, CaltechUNSPECIFIED
Record Number:CaltechAUTHORS:20161005-163012754
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:70904
Deposited On:05 Oct 2016 23:44
Last Modified:11 Nov 2021 04:37

Repository Staff Only: item control page