Document Open Access Logo

Optimal Staged Self-Assembly of General Shapes

Authors Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.26.pdf
  • Filesize: 0.94 MB
  • 17 pages

Document Identifiers

Author Details

Cameron Chalk
Eric Martinez
Robert Schweller
Luis Vega
Andrew Winslow
Tim Wylie

Cite As Get BibTex

Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, and Tim Wylie. Optimal Staged Self-Assembly of General Shapes. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.26

Abstract

We analyze the number of stages, tiles, and bins needed to construct n * n squares and scaled shapes in the staged tile assembly model. In particular, we prove that there exists a staged system with b bins and t tile types assembling an n * n square using O((log n  - tb - t log t)/b^2 + log log b/log t) stages and Omega((log n - tb - t log t)/b^2) are necessary for almost all n. For a shape S, we prove  O((K(S) - tb - t log t)/b^2 + (log  log b)/log t) stages suffice and Omega((K(S) - tb - t log t)/b^2) are necessary for the assembly of a scaled version of S, where K(S) denotes the Kolmogorov complexity of S. Similarly tight bounds are also obtained when more powerful flexible glue functions are permitted. These are the first staged results that hold for all choices of b and t and generalize prior results.
The upper bound constructions use a new technique for efficiently converting each both sources of system complexity, namely the tile types and mixing graph, into a "bit string" assembly.

Subject Classification

Keywords
  • Tile self-assembly
  • 2HAM
  • aTAM
  • DNA computing
  • biocomputing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zachary Abel, Nadia Benbernou, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Scott Kominers, and Robert Schweller. Shape replication through self-assembly and RNAse enzymes. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010. Google Scholar
  2. Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang. Running time and program size for self-assembled squares. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 740-748, 2001. Google Scholar
  3. Bahar Behsaz, Ján Maňuch, and Ladislav Stacho. Turing universality of step-wise and stage assembly at temperature 1. In DNA Computing and Molecular Programming (DNA), volume 7433 of LNCS, pages 1-11. Springer, 2012. Google Scholar
  4. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Andrew Winslow. Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM. In Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 20 of LIPIcs, pages 172-184. Schloss Dagstuhl, 2013. Google Scholar
  5. Ho-Lin Chen and David Doty. Parallelism and time in hierarchical self-assembly. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163-1182, 2012. Google Scholar
  6. Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, and Pablo Moisset de Espanés. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34:1493-1515, 2005. Google Scholar
  7. E. D. Demaine, M. J. Patitz, T. A. Rogers, R. T. Schweller, and D. Woods. The two-handed tile assembly model is not intrinsically universal. In Automata, Languages and Programming (ICALP), volume 7965 of LNCS, pages 400-412. Springer, 2013. Google Scholar
  8. Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine. Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing, 7(3):347-370, 2008. Google Scholar
  9. Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow. One-dimensional staged self-assembly. Natural Computing, 12(2):247-258, 2013. Google Scholar
  10. Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, and Arne Schmidt. New geometric algorithms for fully connected staged self-assembly. In DNA Computing and Molecular Programming (DNA), volume 9211 of LNCS, pages 104-116. Springer, 2015. Google Scholar
  11. Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Self-assembly of arbitrary shapes using RNAse enzymes: Meeting the Kolmogorov bound with small scale factor (extended abstract). In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 9 of LIPIcs, pages 201-212. Schloss Dagstuhl, 2011. Google Scholar
  12. David Doty. Producibility in hierarchical self-assembly. In Proceedings of Unconventional Computation and Natural Computation (UCNC) 2014, pages 142-154, 2014. Google Scholar
  13. Constantine Evans. Crystals that Count! Physical Principles and Experimental Investigations of DNA Tile Self-Assembly. PhD thesis, Caltech, 2014. Google Scholar
  14. David Furcy, Samuel Micka, and Scott M. Summers. Optimal program-size complexity for self-assembly at temperature 1 in 3D. In DNA Computing and Molecular Programming (DNA), volume 9211 of LNCS, pages 71-86. Springer, 2015. Google Scholar
  15. Yonggang Ke, Luvena L. Ong, William M. Shih, and Peng Yin. Three-dimensional structures self-assembled from dna bricks. Science, 338(6111):1177-1183, 2012. Google Scholar
  16. Thomas H. Labean, Sung Ha Park, Sang Jung Ahn, and John H. Reif. Stepwise DNA self-assembly of fixed-size nanostructures. In Foundations of Nanoscience, Self-assembled Architectures, and Devices, pages 179-181, 2005. Google Scholar
  17. Ján Maňuch, Ladislav Stacho, and Christine Stoll. Step-wise tile assembly with a constant number of tile types. Natural Computing, 11(3):535-550, 2012. Google Scholar
  18. Matthew J. Patitz and Scott M. Summers. Identifying shapes using self-assembly. Algorithmica, 64:481-510, 2012. Google Scholar
  19. Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares (extended abstract). In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pages 459-468, 2000. Google Scholar
  20. David Soloveichik and Erik Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6):1544-1569, 2007. Google Scholar
  21. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, Caltech, 1998. Google Scholar
  22. Andrew Winslow. Staged self-assembly and polyomino context-free grammars. Natural Computing, 14(2):293-302, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact