Years and Authors of Summarized Original Work
-
2006; Becker, Rapaport, Rémila
-
2008; Kao, Schweller
-
2009; Chandran, Gopalkrishnan, Reif
-
2010; Doty
Problem Definition
We use the abstract tile assembly model of Winfree [6], which models the aggregation of monomers called tiles that attach one at a time to a growing structure, starting from a single seed tile, in which bonds (“glues”) on the tile are specific (glues only stick to glues of the same type on other tiles) and cooperative (so that multiple weak glues are necessary to attach a tile). The general idea of randomizedself-assembly is to use the inherent randomness of self-assembly to help the assembly process. If multiple types of tiles are able to bind to a single binding site, then we assume that their relative concentrations determine the probability that each succeeds. With careful design, we can use the same tile set to create different structures, by changing the concentrations to affect what is likely to assemble....
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Supported by NSF grants CCF-1219274, CCF-1162589, and 1317694.
Recommended Reading
Becker F, Rapaport I, Rémila E (2006) Self-assembling classes of shapes with a minimum number of tiles, and in optimal time. In: FSTTCS 2006: foundations of software technology and theoretical computer science, Kolkata, pp 45–56
Chandran H, Gopalkrishnan N, Reif JH (2012) Tile complexity of linear assemblies. SIAM J Comput 41(4):1051–1073. Preliminary version appeared in ICALP 2009
Doty D (2010) Randomized self-assembly for exact shapes. SIAM J Comput 39(8):3521–3552. Preliminary version appeared in FOCS 2009
Kao M-Y, Schweller RT (2008) Randomized self-assembly for approximate shapes. In: ICALP 2008: international colloqium on automata, languages, and programming, Reykjavik. Volume 5125 of Lecture notes in computer science. Springer, pp 370–384
Soloveichik D, Winfree E (2007) Complexity of self-assembled shapes. SIAM J Comput 36(6):1544–1569. Preliminary version appeared in DNA 2004
Winfree E (1998) Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology, June 1998
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Doty, D. (2016). Randomized Self-Assembly. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_669
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_669
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering