Program Size and Temperature in Self-Assembly
- Creators
- Chen, Ho-Lin
- Doty, David
- Seki, Shinnosuke
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
Name | Size | Download all |
---|---|---|
md5:7c97abc2edf08a77768c71d757343051
|
309.8 kB | Preview Download |
Additional details
- Eprint ID
- 58618
- DOI
- 10.1007/s00453-014-9879-3
- Resolver ID
- CaltechAUTHORS:20150625-144504315
- CCF-0832824
- NSF
- CNS-1019343
- NSF
- CCF-1219274
- NSF
- CCF-1162589
- NSF
- R2824A01
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Canada Research Chairs Program
- 021530
- Kyoto University
- 902184/T30606
- HIIT Pump Priming Project
- 13266670/T30606
- Academy of Finland
- Created
-
2015-06-25Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field