Abstract
The standard abstract model for analyzing DNA self- assembly, aTAM, assumes that single tiles attach one by one to a larger structure. In practice, tiles may attach to each other forming structures called polyominoes and then attach to the assembly using bonds from multiple tiles. Such polyominoes may cause errors in systems designed with only aTAM in mind. In this paper, we first present a formal definition of when one tile system is a “block replacement” of another. Then we present a block replacement scheme for making any system that admits non-trivial block replacement polyomino-safe. In addition, we present a smaller block replacement scheme that makes the Chinese Remainder counter polyomino-safe and prove that the question of whether a system is polyomino-safe (or other similar properties) is undecidable. Finally, we show that applying our polyomino-safe system produces self-healing systems when applied to most self-healing systems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barish, R., Rothemund, P., Winfree, E.: Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Lett. 5, 2586–2592 (2005)
Winfree, E., Yang, X., Seeman, N.: 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, Providence (1998)
Winfree, E.: Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, Computation and Neural Systems Option (1998)
Rothemund, P.: Folding DNA to create nanoscale shapes and patterns. Nature 440, 297–302 (2006)
Soloveichik, D., Winfree, E.: Complexity of compact proofreading for self-assembled patterns. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 305–324. Springer, Heidelberg (2006)
Yurke, B., Turberfield, A., Mills Jr., A., Simmel, F., Neumann, J.: A DNA-fuelled molecular machine made of DNA. Nature (406), 605–608 (2000)
Shin, J.S., Pierce, N.: A synthetic DNA walker for molecular transport. J. Am. Chem. Soc. 126, 10834–10835 (2004)
Sherman, W., Seeman, N.: A precisely controlled DNA biped walking device. Nano Letters 4, 1203–1207 (2004)
Yin, P., Yan, H., Daniel, X., Turberfield, A., Reif, J.: A unidirectional DNA walker moving autonomously along a linear track. Angewandte Chemie 43, 4906–4911 (2004)
Tian, Y., He, Y., Chen, Y., Yin, P., Mao, C.: A DNAzyme that walks processively and autonomously along a one-dimensional track. Angewandte Chemie 117, 4429–4432 (2005)
Winfree, E., Liu, F., Wenzler, L., Seeman, N.: Design and self-assembly of two-dimensional DNA crystals. Nature 394, 539–544 (1998)
Rothemund, P., Winfree, E.: The program-size complexity of self-assembled squares. In: Symposium on Theory of Computing (STOC), Portland, Oregon, United States, pp. 459–468. ACM Press, New York (2000)
Adleman, L., Cheng, Q., Goel, A., Huang, M.: Running time and program size for self-assembled squares. In: ACM Symposium on Theory of Computing, pp. 740–748 (2001)
Cheng, Q., Goel, A., Moisset, P.: Optimal self-assembly of counters at temperature two. In: Proceedings of the first Conference on Foundations of nanoscience: self-assembled architectures and devices (April 2004)
Aggarwal, G., Cheng, Q., Goldwasser, M., Kao, M.Y., de Moisset Espanes, P., Schweller, R.: Complexities for generalized models of self-assembly. SIAM Journal on Computing 34, 1493–1515 (2005)
Lagoudakis, M., LaBean, T.: 2-D DNA self-assembly for satisfiability. In: Winfree, E., Gifford, D.K. (eds.) DNA Based Computers V. DIMACS, vol. 54, pp. 141–154. American Mathematical Society, Providence (2000)
Baryshnikov, Y., Coffman, E., Momcilovic, P.: DNA-based computation times. In: Proceedings of the Tenth International Meeting on DNA Based Computers, Milano, Italy (June 2004)
Winfree, E., Bekbolatov, R.: Proofreading tile sets: Error-correction for algorithmic self-assembly. In: Chen, J., Reif, J.H. (eds.) DNA 2003. LNCS, vol. 2943, pp. 126–144. Springer, Heidelberg (2004)
Chen, H., Goel, A.: Error free self-assembly using error prone tiles. In: [27], pp. 62–75
Reif, J., Sahu, S., Yin, P.: Compact error-resilient computational DNA tiling assemblies. In: [27], pp. 293–307
Schulman, R., Winfree, E.: Programmable control of nucleation for algorithmic self-assembly. In: [27], pp. 319–328 (Extended abstract; preprint of the full paper is cond.mat/0607317 on arXiv.org)
Chen, H., Cheng, Q., Goel, A., Huang, M., Moisset, P.: Invadable self-assembly: Combining robustness with efficiency. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2004)
Chen, H., Goel, A., Luhrs, C.: Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly. In: Symposium on Discrete Algorithms (2008)
Winfree, E.: Self-healing tile sets. Nanotechnology: Science and Computation, 55–78 (2006)
Chen, H., Goel, A., Luhrs, C., Winfree, E.: Self-assembling tile systems that heal from small fragments. In: DNA 13 (2007)
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. In: Garzon, M.H., Yan, H. (eds.) DNA 2007. LNCS, vol. 4848, pp. 1–14. Springer, Heidelberg (2008)
Ferretti, C., Mauri, G., Zandron, C. (eds.): DNA 2004. LNCS, vol. 3384. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Luhrs, C. (2009). Polyomino-Safe DNA Self-assembly via Block Replacement. In: Goel, A., Simmel, F.C., Sosík, P. (eds) DNA Computing. DNA 2008. Lecture Notes in Computer Science, vol 5347. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03076-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-03076-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03075-8
Online ISBN: 978-3-642-03076-5
eBook Packages: Computer ScienceComputer Science (R0)