Abstract
We analyze the complexity of building linear assemblies, sets of linear assemblies, and \({\mathcal{O}}(1)\)-scale general shapes in the staged tile assembly model. For systems with at most b bins and t tile types, we prove that the minimum number of stages to uniquely assemble a \(1 \times n\)line is \(\varTheta (\log _t{n} + \log _b{\frac{n}{t}} + 1)\). Generalizing to \({\mathcal{O}}(1) \times n\) lines, we prove the minimum number of stages is \({\mathcal{O}}(\frac{\log {n} - tb - t\log t}{b^2} + \frac{\log \log b}{\log t})\) and \(\varOmega (\frac{\log {n} - tb - t\log t}{b^2})\). We also obtain similar upper and lower bounds in a model permitting flexible glues using non-diagonal glue functions. Next, we consider assembling sets of lines and general shapes using \(t = {\mathcal{O}}(1)\) tile types. We prove that the minimum number of stages needed to assemble a set of k lines of size at most \({\mathcal{O}}(1) \times n\) is \({\mathcal{O}}(\frac{k\log n}{b^2}+\frac{k\sqrt{\log n}}{b}+\log \log n)\) and \(\varOmega (\frac{k\log n}{b^2})\). In the case that \(b = \mathcal {O}(\sqrt{k})\), the minimum number of stages is \(\varTheta (\log {n})\). The upper bound in this special case is then used to assemble “hefty” shapes of at least logarithmic edge-length-to-edge-count ratio at \(\mathcal {O}(1)\)-scale using \(\mathcal {O}(\sqrt{k})\) bins and optimal \(\mathcal {O}(\log {n})\) stages.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
The result is given for the aTAM in Cheng et al. (2005) but the same tile set at temperature 2 in the 2HAM behaves identically.
The original staged model Demaine et al. (2008) only considered \(\mathcal {O}(1)\) distinct tile types, and thus for simplicity allowed tiles to be added at any stage. Because systems here may have super-constant tile complexity, we restrict tiles to only be added at the initial stage.
This is a slight modification of the original staged model Demaine et al. (2008) in that the final stage may have multiple bins. However, all of our results apply to both variants of the model.
The “\(+1\)” implies the trivial requirement of at least one stage.
Note that the first bound is missing the additive constant to ensure at least one stage. There is still a requirement of at least one stage, but ‘\(+1\)’ may be insufficient as the term could be negative.
References
Adleman L, Cheng Q, Goel A, Huang MD, Wasserman H (2001) Linear self-assemblies: equilibria, entropy and convergence rates. In: 6th international conference on difference equations and applications
Adleman LM, Cheng Q, Goel A, Huang MDA, Kempe D, de Espanés PM, Rothemund PWK (2009) Combinatorial optimization problems in self-assembly. SIAM J Comput 38(6):2356–2381
Barish RD, Schulman R, Rothemund PWK, Winfree E (2009) An information-bearing seed for nucleating algorithmic self-assembly. Proc Nat Acad Sci 106(15):6054–6059
Cannon S, Demaine ED, Demaine ML, Eisenstat S, Patitz MJ, Schweller RT, Summers SM, Winslow A (2013) Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM. In: STACS 2013, LIPIcs, vol 20. p 172–184. Schloss Dagstuhl
Chalk C, Martinez E, Schweller R, Vega L, Winslow A, Wylie T (2018) Optimal staged self-assembly of general shapes. Algorithmica 80(4):1383–1409. https://doi.org/10.1007/s00453-017-0318-0
Chandran H, Gopalkrishnan N, Reif J (2012) Tile complexity of linear assemblies. SIAM J Comput 41(4):1051–1073
Chen HL, Doty D (2012) Parallelism and time in hierarchical self-assembly. In: 23rd annual ACM-SIAM symposium on discrete algorithms (SODA), p 1163–1182. SIAM
Cheng Q, Aggarwal G, Goldwasser MH, Kao MY, Schweller RT, de Espanés PM (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515
Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, Souvaine DL (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with \({O}(1)\) glues. Nat Comput 7(3):347–370
Demaine ED, Eisenstat S, Ishaque M, Winslow A (2013) One-dimensional staged self-assembly. Nat Comput 12(2):247–258
Demaine ED, Fekete SP, Scheffer C, Schmidt A (2015) New geometric algorithms for fully connected staged self-assembly. In: Proceedings of the 21st international conference on DNA computing and molecular programming, LNCS, vol 9211. Springer, p 104–116
Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D (2016) The two-handed tile assembly model is not intrinsically universal. Algorithmica 74(2):812–850
Evans C (2014) Crystals that count! Physical principles and experimental investigations of dna tile self-assembly. Ph.D. thesis, Caltech
Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the 32nd ACM symposium on theory of computing, STOC’00, p 459–468
Schulman R, Winfree E (2007) Synthesis of crystals with a programmable kinetic barrier to nucleation. Proc Nat Acad Sci 104(39):15236–15241
Schweller R, Winslow A, Wylie T (2017) Complexities for high-temperature two-handed tile self-assembly. In: Proceedings of the 23rd international conference on DNA computing and molecular programming
Schweller R, Winslow A, Wylie T (2017) Verification in staged tile self-assembly. In: 16th international conference unconventional computation and natural computation, p 98–112
Seeman NC (1982) Nucleic-acid junctions and lattices. J Theor Biol 99:237–247
Tikhomirov G, Petersen P, Qian L (2017) Fractal assembly of micrometre-scale dna origami arrays with arbitrary patterns. Nature 552(7683):67
Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, Caltech
Winslow A (2015) Staged self-assembly and polyomino context-free grammars. Nat Comput 14(2):293–302
Winslow A (2016) Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems. Nat Comput 15(1):143–151
Woods D (2015) Intrinsic universality and the computational power of self-assembly. Philos Trans R Soc A. https://doi.org/10.1098/rsta.2014.0214
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations
This research was supported in part by National Science Foundation Grants CCF-1117672, CCF-1555626, and CCF-1817602.
Rights and permissions
About this article
Cite this article
Chalk, C., Martinez, E., Schweller, R. et al. Optimal staged self-assembly of linear assemblies. Nat Comput 18, 527–548 (2019). https://doi.org/10.1007/s11047-019-09740-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-019-09740-y