Identifying Shapes Using Self-assembly | Algorithmica
Skip to main content
Springer Nature Link
Log in

Identifying Shapes Using Self-assembly

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite tile set that can, in some sense, uniquely identify whether or not the given input shape—drawn from a very general class of shapes—matches a particular target shape. We first study the complexity of correctly identifying squares. Then we investigate the complexity associated with the identification of a considerably more general class of non-square, hole-free shapes.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abel, Z., Benbernou, N., Damian, M., Demaine, E., Demaine, M., Flatland, R., Kominers, S., Schweller, R.: Shape replication through self-assembly and RNAse enzymes. In: Proceedings of the Twentyfirst Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 1045–1064 (2010)

    Google Scholar 

  2. Adleman, L.: Toward a mathematical theory of self-assembly (extended abstract). Tech. report 00-722, University of Southern California (2000)

  3. Adleman, L., Cheng, Q., Goel, A., Huang, M.-D.: Running time and program size for self-assembled squares. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC 2001), New York, NY, USA, pp. 740–748. ACM, New York (2001)

    Chapter  Google Scholar 

  4. Adleman, L., Cheng, Q., Goel, A., Huang, M.-D., Wasserman, H.: Linear self-assemblies: equilibria, entropy and convergence rates. In: Sixth International Conference on Difference Equations and Applications. Taylor & Francis, London (2001)

    Google Scholar 

  5. Andersen, E.S., Dong, M., Nielsen, M.M., Jahn, K., Subramani, R., Mamdouh, W., Golas, M.M., Sander, B., Stark, H., Oliveira, C.L.P., Pedersen, J.S., Birkedal, V., Besenbacher, F., Gothelf, K.V., Kjems, J.: Self-assembly of a nanoscale DNA box with a controllable lid. Nature 459(7243), 73–76 (2009)

    Article  Google Scholar 

  6. Barish, R.D., Schulman, R., Rothemund, P.W., Winfree, E.: An information-bearing seed for nucleating algorithmic self-assembly. Proc. Natl. Acad. Sci. USA 106(15), 6054–6059 (2009)

    Article  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. Cook, M., Fu, Y., Schweller, R.: Temperature 1 self-assembly: deterministic assembly in 3d and probabilistic assembly in 2d. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 570–589 (2011)

    Google Scholar 

  9. Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Nat. Comput. 7(3), 347–370 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Doty, D., Kari, L., Masson, B.: Negative interactions in irreversible self-assembly. In: Proceedings of the Sixteenth International Meeting on DNA Computing and Molecular Programming (DNA 16). Lecture Notes in Computer Science, pp. 37–48. Springer, Berlin (2010)

    Google Scholar 

  11. Schweller, R.T., Demain, E.D., Patitz, M.J., Summers, S.M.: Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor. Algorithmica (to appear). Preliminary version appeared in “DNA 2010” (2011)

  12. Gu, H., Chao, J., Xiao, S.-J., Seeman, N.C.: A proximity-based programmable DNA nanoscale assembly line. Nature 465(7295), 202–205 (2010)

    Article  Google Scholar 

  13. Hartgerink, J.D., Beniash, E., Stupp, S.I.: Self-assembly and mineralization of peptide-amphiphile nanofibers. Science 294(5547), 1684–1688 (2001)

    Article  Google Scholar 

  14. Kalsin, A.M., Fialkowski, M., Paszewski, M., Smoukov, S.K., Bishop, K.J.M., Grzybowski, B.A.: Electrostatic self-assembly of binary nanoparticle crystals with a diamond-like lattice. Science 312(5772), 420–424 (2006)

    Article  Google Scholar 

  15. Kao, M.-Y., Schweller, R.T.: Reducing tile complexity for self-assembly through temperature programming. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, Jan. 2006, pp. 571–580 (2007)

    Google Scholar 

  16. Lathrop, J.I., Lutz, J.H., Patitz, Ma.J., Summers, S.M.: Computability and complexity in self-assembly. Theory Comput. Syst. 48, 617–647 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Luhrs, C.: Polyomino-safe DNA self-assembly via block replacement. In: Goel, A., Simmel, F.C., Sosík, P. (eds.) Proceedings of the Fourteenth International Meeting on DNA Computing and Molecular Programming (DNA 14). Lecture Notes in Computer Science, vol. 5347, pp. 112–126. Springer, Berlin (2008)

    Google Scholar 

  18. Lund, K., Manzo, A.J., Dabby, N., Michelotti, N., Johnson-Buck, A., Nangreave, J., Taylor, S., Pei, R., Stojanovic, M.N., Walter, N.G., Winfree, E., Yan, H.: Molecular robots guided by prescriptive landscapes. Nature 465(7295), 206–210 (2010)

    Article  Google Scholar 

  19. Majumder, U., LaBean, T.H., Reif, J.H.: Activatable tiles for compact error-resilient directional assembly. In: 13th International Meeting on DNA Computing (DNA 13), Memphis, Tennessee, June 4–8, 2007, (2007)

    Google Scholar 

  20. Reif, J.H., Sahu, S., Yin, P.: Rothemund, P.W.K.: Complexity of graph self-assembly in accretive systems and self-destructible systems. Theor. Comp. Sci. 412, 1592–1605 (2011)

    Article  MATH  Google Scholar 

  21. Rothemund, P.W.K.: Folding DNA to create nanoscale shapes and patterns. Nature 440(7082), 297–302 (2006)

    Article  Google Scholar 

  22. Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000), New York, NY, USA, pp. 459–468. ACM, New York (2000)

    Chapter  Google Scholar 

  23. Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2(12), 2041–2053 (2004)

    Article  Google Scholar 

  24. Sahu, S., Yin, P., Reif, J.H.: A self assembly model of time-dependent glue strength. In: Proceedings of the Eleventh International Meeting on DNA Based Computers (DNA11). Lecture Notes in Computer Science, pp. 113–124. Springer, Berlin (2006)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  26. Tang, Z., Zhang, Z., Wang, Y., Glotzer, S.C., Kotov, N.A.: Self-assembly of CdTe nanocrystals into free-floating sheets. Science 314(5797), 274–278 (2006)

    Article  Google Scholar 

  27. Vitányi, P., Li, M.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (1997)

    MATH  Google Scholar 

  28. Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology, June (1998)

  29. Winfree, E.: Simulations of computing by self-assembly. Tech. report CaltechCSTR:1998.22, California Institute of Technology (1998)

  30. Winfree, E.: Self-healing tile sets. In: Chen, J., Jonoska, N., Rozenberg, G. (eds.) Nanotechnology: Science and Computation. Natural Computing Series, pp. 55–78. Springer, Berlin (2006)

    Chapter  Google Scholar 

  31. Winfree, E., Yang, X., Seeman, N.C.: Universal computation via self-assembly of DNA: some theory and experiments. DNA Based Computers II, volume 44 of DIMACS, pp. 191–213. Am. Math. Soc., Providence (1996)

    Google Scholar 

  32. Yan, H., Park, S.H., Finkelstein, G., Reif, J.H., LaBean, T.H.: DNA-templated self-assembly of protein arrays and highly conductive nanowires. Science 301(5641), 1882–1884 (2003)

    Article  Google Scholar 

  33. Zeng, H., Li, J., Liu, J.P., Wang, Z.L., Sun, S.: Exchange-coupled nanocomposite magnets by nanoparticle self-assembly. Nature 420(6914), 395–398 (2002)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Texas-Pan American, Edinburg, TX, 78539, USA

    Matthew J. Patitz

  2. Department of Computer Science and Software Engineering, University of Wisconsin-Platteville, Platteville, WI, 53818, USA

    Scott M. Summers

Authors
  1. Matthew J. Patitz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Scott M. Summers
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Scott M. Summers.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Patitz, M.J., Summers, S.M. Identifying Shapes Using Self-assembly. Algorithmica 64, 481–510 (2012). https://doi.org/10.1007/s00453-011-9549-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-011-9549-7

Keywords

Search

Navigation