Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information. In particular, for all \(n \in \mathbb {N}\), we assemble \(n \times n\) squares using \(O(2^{\log ^*{n}})\) tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with \(O(2^{\log ^*{K}})\) tiles, where K denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct \(n \times O(1)\) rectangles using only \(O(\log {n}/\log \log {n})\) tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature. These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Notes

  1. The function \(\log ^*{n}\) is the iterated logarithm: the number of times the logarithm must be repeatedly applied, beginning with n, until a value of less than 1 is reached.

  2. The term thin refers to the constant height of the rectangle.

References

  1. Adleman, L., Cheng, Q., Goel, A., Huang, M.D.: Running time and program size for self-assembled squares. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, STOC’01, pp. 740–748 (2001)

  2. Bryans, N., Chiniforooshan, E., Doty, D., Kari, L., Seki, S.: The power of nondeterminism in self-assembly. In: Proceedings of the 22nd ACM–SIAM Symposium on Discrete Algorithms, SODA’11, pp. 590–602. SIAM (2011)

  3. Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Patitz, M.J., Schweller, R., Summers, S.M., Winslow, A.: Two hands are better than one (up to constant factors). In: Proceedings of 30th International Symposium on Theory Aspects of Computing Science, STACS’13, pp. 172–184 (2013)

  4. Chalk, C., Luchsinger, A., Schweller, R., Wylie, T.: Self-assembly of any shape with constant tile types using high temperature. In: Proceedings of the 26th Annual European Symposium on Algorithms, ESA’18 (2018)

  5. Chen, H.L., Doty, D.: Parallelism and time in hierarchical self-assembly. In: Proceedings of the 23rd ACM–SIAM Symposium on Discrete Algorithms, SODA’12, pp. 1163–1182. SIAM (2012)

  6. Chen, H.L., Doty, D., Seki, S.: Program size and temperature in self-assembly. Algorithmica 72(3), 884–899 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cheng, Q., Aggarwal, G., Goldwasser, M.H., Kao, M.Y., Schweller, R.T., de Espanés, P.M.: Complexities for generalized models of self-assembly. SIAM J. Comput. 34, 1493–1515 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Demaine, E., Patitz, M., Rogers, T., Schweller, R., Summers, S.M., Woods, D.: The two-handed tile assembly model is not intrinsically universal. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013) (2013)

  9. Doty, D.: Personal communication

  10. Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R., Summers, S.M., Woods, D.: The tile assembly model is intrinsically universal. In: Proceedings of the 53rd IEEE Conference on Foundations of Computer Science (FOCS), pp. 302–310 (2012)

  11. Doty, D., Patitz, M.J., Summers, S.M.: Limitations of self-assembly at temperature one. In: Proceedings of 15th International Conference on DNA Computing and Molecular Programming (DNA’09), LNCS, vol. 5877, pp. 35–44. Springer, Berlin (2009)

  12. Evans, C.: Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly. Ph.D. thesis, California Institute of Technology (2014)

  13. Maňuch, J., Stacho, L., Stoll, C.: Two lower bounds for self-assemblies at temperature 1. J. Comput. Biol. 16(6), 841–852 (2010)

    MathSciNet  Google Scholar 

  14. Meunier, P.E.: The self-assembly of paths and squares at temperature 1. Tech. rep., arXiv (2013)

  15. Meunier, P.E., Patitz, M.J., Summers, S.M., Theyssier, G., Woods, D.: Intrinsic universality in tile self-assembly requires cooperation. In: Proceedings of the 25th Symposium on Discrete Algorithms (SODA), pp. 752–771 (2014)

  16. Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 459–468 (2000)

  17. Schulman, R., Winfree, E.: Programmable control of nucleation for algorithmic self-assembly. SIAM J. Comput. 39(4), 1581–1616 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Schweller, R.T., Winslow, A., Wylie, T.: Complexities for high-temperature two-handed tile self-assembly. In: 23rd International Conference on Computing and Molecular Programming, DNA’17, pp. 98–109 (2017). https://doi.org/10.1007/978-3-319-66799-7_7

  19. Seeman, N.C.: Nucleic-acid junctions and lattices. J. Theor. Biol. 99, 237–247 (1982)

    Article  Google Scholar 

  20. Seki, S., Ukuno, Y.: On the behavior of tile assembly system at high temperatures. Computability 2(2), 107–124 (2013)

    MathSciNet  MATH  Google Scholar 

  21. Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM J. Comput. 36(6), 1544–1569 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  22. Summers, S.M.: Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica 63(1), 117–136 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  23. Winfree, E.: Algorithmic Self-Assembly of DNA. Ph.D. thesis, California Institute of Technology (1998)

  24. Woods, D.: Intrinsic universality and the computational power of self-assembly. Philos. Trans. R. Soc. A (2015). https://doi.org/10.1098/rsta.2014.0214

Download references

Author information

Authors and Affiliations

  1. University of Texas - Rio Grande Valley, Edinburg, TX, USA

    Robert Schweller, Andrew Winslow & Tim Wylie

Authors
  1. Robert Schweller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Winslow
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tim Wylie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tim Wylie.

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-1555626 and CCF-1817602.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Schweller, R., Winslow, A. & Wylie, T. Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly. Algorithmica 81, 3114–3135 (2019). https://doi.org/10.1007/s00453-019-00573-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-019-00573-w

Keywords

Search

Navigation