A Caltech Library Service

Negative Interactions in Irreversible Self-assembly

Doty, David and Kari, Lila and Masson, Benoît (2011) Negative Interactions in Irreversible Self-assembly. In: DNA computing and molecular programming. Lecture notes in computer science. No.6518. Springer-Verlag , New York, pp. 37-48. ISBN 978-3-642-18304-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper explores the use of negative (i.e., repulsive) interactions in the abstract Tile Assembly Model defined by Winfree. Winfree in his Ph.D. thesis postulated negative interactions to be physically plausible, and Reif, Sahu, and Yin studied them in the context of reversible attachment operations. We investigate the power of negative interactions with irreversible attachments, and we achieve two main results. Our first result is an impossibility theorem: after t steps of assembly, Ω(t) tiles will be forever bound to an assembly, unable to detach. Thus negative glue strengths do not afford unlimited power to reuse tiles. Our second result is a positive one: we construct a set of tiles that can simulate an s-space-bounded, t-time-bounded Turing machine, while ensuring that no intermediate assembly grows larger than O(s), rather than O(s⋅t) as required by the standard Turing machine simulation with tiles.

Item Type:Book Section
Related URLs:
Additional Information:© 2011 Springer-Verlag Berlin Heidelberg. The authors are grateful to Shinnosuke Seki for insightful discussions and anonymous referees for their suggestions. This research was supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari, and by the )lSF Computing Innovation Fellowship grant to David Doty.
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery GrantR2824A01
Canada Research Chair Award in Biocomputing UNSPECIFIED
NSF Computing Innovation Fellowship UNSPECIFIED
Series Name:Lecture notes in computer science
Issue or Number:6518
Record Number:CaltechAUTHORS:20130327-142314617
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:37654
Deposited By: Tony Diaz
Deposited On:12 Apr 2013 22:48
Last Modified:03 Oct 2019 04:49

Repository Staff Only: item control page