Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2015 | Submitted
Journal Article Open

Program Size and Temperature in Self-Assembly

Abstract

Winfree's abstract Tile Assembly Model is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing "seed" assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an n×n square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman et al. (Combinatorial optimization problems in self-assembly, STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its "temperature" (the binding strength threshold required for a tile to attach).

Additional Information

© 2014 Springer Science+Business Media New York. Received: 3 September 2012; Accepted: 19 March 2014; Published online: 4 April 2014. The authors thank Ehsan Chiniforooshan especially, for many fruitful and illuminating discussions that led to the results on temperature, and also Adam Marblestone and the members of Erik Winfree's group, particularly David Soloveichik, Joe Schaeffer, Damien Woods, and Erik Winfree, for insightful discussion and comments. The second author is grateful to Aaron Meyerowitz (via the website http://mathoverflow.net) for pointing out the Dedekind numbers as a way to count the number of collections of subsets of a given set that are closed under the superset operation. Ho-Lin Chen was supported by the Molecular Programming Project under NSF Grant 0832824. David Doty was supported by an Computing Innovation Fellowship under NSF Grant 1019343 and NSF Grants CCF-1219274 and CCF-1162589 and the Molecular Programming Project under NSF Grant 0832824. Shinnosuke Seki was supported by NSERC Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari, by Kyoto University Start-up Grant-in-Aid for Young Scientists (No. 021530), by HIIT Pump Priming Project 902184/T30606, and by Academy of Finland, Postdoctoral Researcher Grant No. 13266670/T30606.

Attached Files

Submitted - 1011.3493v2.pdf

Files

1011.3493v2.pdf
Files (309.8 kB)
Name Size Download all
md5:7c97abc2edf08a77768c71d757343051
309.8 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 23, 2023