[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-assembly in Two and Three Dimensions

  • Conference paper
DNA Computing (DNA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4287))

Included in the following conference series:

Abstract

Winfree’s pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly[26], but the construction resulted in increase of the size of assembly. Reif et. al. contributed further in this area with compact error-resilient schemes [15] that maintained the original size of the assemblies, but required certain restrictions on the Boolean functions to be used in the algorithmic self-assembly. It is a critical challenge to improve these compact error resilient schemes to incorporate arbitrary Boolean functions, and to determine how far these prior results can be extended under different degrees of restrictions on the Boolean functions. In this work we present a considerably more complete theory of compact error-resilient schemes for algorithmic self-assembly in two and three dimensions. First we consider two-dimensional algorithmic self-assembly. We present an error correction scheme for reduction of errors from ε to ε 2 for arbitrary Boolean functions in two dimensional algorithmic self-assembly. Then we characterize the class of Boolean functions for which the error reduction can be done from ε to ε 3, and present an error correction scheme that achieves this reduction. Then we prove ultimate limits on certain classes of compact error resilient schemes: in particular we show that they can not provide reduction of errors from ε to ε 4 is for any Boolean functions. Further, we develop the first provable compact error resilience schemes for three dimensional tiling self-assemblies. We also extend the work of Winfree on self-healing in two-dimensional self-assembly[25] to obtain a self-healing tile-set for three-dimensional self-assembly.

The work is supported by NSF EMT Grants CCF-0523555 and CCF-0432038.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bondarenko, B.A.: Generalized Pascal Triangles and Pyramids, Their Fractals, Graphs and Applications. The Fibonacci Association (1993) Translated from Russion and edited by R.C. Bollinger

    Google Scholar 

  2. Bowden, N., Terfort, A., Carbeck, J., Whitesides, G.M.: Self-assembly of mesoscale objects into ordered two-dimensional arrays. Science 276(11), 233–235 (1997)

    Article  Google Scholar 

  3. Chelyapov, N., Brun, Y., Gopalkrishnan, M., Reishus, D., Shaw, B., Adleman, L.: DNA triangles and self-assembled hexagonal tilings. J. Am. Chem. Soc. 126, 13924–13925 (2004)

    Article  Google Scholar 

  4. Chen, H.L., Cheng, Q., Goel, A., Huang, M.D., de Espanes, P.M.: Invadable self-assembly: Combining robustness with efficiency. In: Proceedings of the 15th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 890–899 (2004)

    Google Scholar 

  5. Chen, H.L., Goel, A.: Error free self-assembly using error prone tiles. DNA Based Computers 10, 274–283 (2004)

    Google Scholar 

  6. Clark, T.D., Ferrigno, R., Tien, J., Paul, K.E., Whitesides, G.M.: Template-directed self-assembly of 10-microm-sized hexagonal plates. J. Am. Chem. Soc. 124(19), 5419–5426 (2002)

    Article  Google Scholar 

  7. Jonoska, N., Karl, S.A., Saito, M.: Three dimensional DNA structures in computing. BioSystems 52, 143–153 (1999)

    Article  Google Scholar 

  8. LaBean, T.H., Yan, H., Kopatsch, J., Liu, F., Winfree, E., Reif, J.H., Seeman, N.C.: The construction, analysis, ligation and self-assembly of DNA triple crossover complexes. J. Am. Chem. Soc. 122, 1848–1860 (2000)

    Article  Google Scholar 

  9. Lagoudakis, M.G., LaBean, T.H.: 2-D DNA self-assembly for satisfiability. In: DNA Based Computers V. DIMACS, vol. 54, pp. 141–154. American Mathematical Society (2000)

    Google Scholar 

  10. Liu, D., Wang, M., Deng, Z., Walulu, R., Mao, C.: Tensegrity: Construction of rigid DNA triangles with flexible four-arm dna junctions. J. Am. Chem. Soc. 126, 2324–2325 (2004)

    Article  Google Scholar 

  11. Mao, C., Sun, W., Seeman, N.C.: Designed two-dimensional DNA holliday junction arrays visualized by atomic force microscopy. J. Am. Chem. Soc. 121, 5437–5443 (1999)

    Article  Google Scholar 

  12. Martin, B.R., Furnange, D.C., Jackson, T.N., Mallouk, T.E., Mayer, T.S.: Self-alignment of patterned wafers using capillary forces at a water-air interface. Advanced Functional Materials 11, 381–386 (2001)

    Article  Google Scholar 

  13. Paukstelis, P.J., Nowakowski, J., Birktoft, J.J., Seeman, N.C.: Crystal structure of a continuous three-dimensional DNA lattice. Chemistry and Biology 11, 1119–1126 (2004)

    Article  Google Scholar 

  14. Reif, J.H.: Local parallel biomolecular computation. In: Rubin, H., Wood, D.H. (eds.) DNA-Based Computers 3. DIMACS, vol. 48, pp. 217–254. American Mathematical Society (1999)

    Google Scholar 

  15. Reif, J.H., Sahu, S., Yin, P.: Compact error-resilient computational DNA tiling assemblies. In: Proc. 10th International Meeting on DNA Computing, pp. 248–260 (2004)

    Google Scholar 

  16. Rothemund, P.W.K.: Using lateral capillary forces to compute by self-assembly. Proc. Natl. Acad. Sci. USA 97(3), 984–989 (2000)

    Article  Google Scholar 

  17. Sahu, S., Reif, J.H.: Capabilities and limits of compact error resilience methods for algorithmic self-assembly in two and three dimensions. Technical Report CS-2006-04, Duke University (2006)

    Google Scholar 

  18. Schulman, R., Winfree, E.: Programmable control of nucleation for algorithmic self-assembly. In: DNA Based Computers 10, LNCS (2005)

    Google Scholar 

  19. Seeman, N.C.: DNA in a material world. Nature 421, 427–431 (2003)

    Article  MathSciNet  Google Scholar 

  20. Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. In: DNA Based Computers 10. LNCS, Springer, Heidelberg (2005)

    Google Scholar 

  21. Wang, H.: Proving theorems by pattern recognition ii. Bell Systems Technical Journal 40, 1–41 (1961)

    Google Scholar 

  22. Whitesides, G.M., Grzybowski, B.: Self-assembly at all scales. Science 295, 2242–2418 (2002)

    Article  Google Scholar 

  23. Winfree, E.: Complexity of restricted and unrestricted models of molecular computation. In: Lipton, R.J., Baum, E.B. (eds.) DNA Based Computers 1. DIMACS, vol. 27, pp. 187–198. American Mathematical Society (1996)

    Google Scholar 

  24. Winfree, E.: Simulation of computing by self-assembly. Technical Report 1998.22, Caltech (1998)

    Google Scholar 

  25. Winfree, E.: Self-healing tile sets. In: Nanotechnology: Science and Computation. One-page abstract in proceedings of FNANO 2005 (preprint, 2006)

    Google Scholar 

  26. Winfree, E., Bekbolatov, R.: Proofreading tile sets: Error correction for algorithmic self-assembly. In: Chen, J., Reif, J.H. (eds.) DAN 2003. LNCS, vol. 2943, pp. 126–144. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  27. Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional DNA crystals. Nature 394(6693), 539–544 (1998)

    Article  Google Scholar 

  28. Winfree, E., Yang, X., Seeman, N.C.: Universal computation via self-assembly of DNA: Some theory and experiments. In: Landweber, L.F., Baum, E.B. (eds.) DNA Based Computers II. DIMACS, vol. 44, pp. 191–213. American Mathematical Society (1999)

    Google Scholar 

  29. Xiong, X., Hanein, Y., Fang, J., Wang, Y., Wang, W., Schwartz, D., Bohringer, K.: Controlled multibatch self-assembly of microdevices. Journal Of Microelectromechanical Systems 12, 117–127 (2003)

    Article  Google Scholar 

  30. Yan, H., Feng, L., LaBean, T.H., Reif, J.H.: Parallel molecular computation of pair-wise xor using DNA string tile. J. Am. Chem. Soc. 125(47) (2003)

    Google Scholar 

  31. Yan, H., LaBean, T.H., Feng, L., Reif, J.H.: Directed nucleation assembly of DNA tile complexes for barcode patterned DNA lattices. Proc. Natl. Acad. Sci. USA 100(14), 8103–8108 (2003)

    Article  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 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Duke University, Box 90129, Durham, NC, 27708-0129, USA

    Sudheer Sahu & John H. Reif

Authors
  1. Sudheer Sahu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John H. Reif
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Chemistry, Purdue University, 560 Oval Drive, 47907-2084, West Lafayette, IN, USA

    Chengde Mao

  2. Faculty of Education and Integrated Arts and Sciences, Department of Mathematics, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, 169-8050, Tokyo, Japan

    Takashi Yokomori

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sahu, S., Reif, J.H. (2006). Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-assembly in Two and Three Dimensions. In: Mao, C., Yokomori, T. (eds) DNA Computing. DNA 2006. Lecture Notes in Computer Science, vol 4287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11925903_17

Download citation

  • DOI: https://doi.org/10.1007/11925903_17

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49024-1

  • Online ISBN: 978-3-540-68423-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation