nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Complexities for High-Temperature Two-Handed Tile Self-assembly

verfasst von : Robert Schweller, Andrew Winslow, Tim Wylie

Erschienen in: DNA Computing and Molecular Programming

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Tile self-assembly is a formal model of computation capturing DNA-based nanoscale systems. Here we consider the popular two-handed tile self-assembly model or 2HAM. Each 2HAM system includes a temperature parameter, which determines the threshold of bonding strength required for two assemblies to attach. Unlike most prior study, we consider general temperatures not limited to small, constant values. We obtain two results. First, we prove that the computational complexity of determining whether a given tile system uniquely assembles a given assembly is coNP-complete, confirming a conjecture of Cannon et al. (2013). Second, we prove that larger temperature values decrease the minimum number of tile types needed to assemble some shapes. In particular, for any temperature \(\tau \in \{3, \dots \}\), we give a class of shapes of size n such that the ratio of the minimum number of tiles needed to assemble these shapes at temperature \(\tau \) and any temperature less than \(\tau \) is \(\varOmega (n^{1/(2\tau +2)})\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Stochastic Molecular Scheme for an Artificial Cell to Infer Its Environment from Partial Observations

Nächstes Kapitel A DNA Neural Network Constructed from Molecular Variable Gain Amplifiers

Note that only matching glues have positive strength. The more general model of “flexible glues” where non-matching glue pairs may also have positive strength has been considered [7].

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

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

Adleman, L.M., Cheng, Q., Goel, A., Huang, M.-D.A., Kempe, D., de Espanés, P.M., Rothemund, P.W.K.: Combinatorial optimization problems in self-assembly. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 23–32 (2002)

Cannon, S., Demaine, E.D., Demaine, E.D., Eisenstat, S., Patitz, M.J., Schweller, R., Summers, S.M., Winslow, A.: 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). LIPIcs, vol. 20, pp. 172–184. Schloss Dagstuhl (2013)

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

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

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)MathSciNetCrossRefMATH

Demaine, E.D., Patitz, M.J., Rogers, T.A., Schweller, R.T., Summers, S.M., Woods, D.: The two-handed tile assembly model is not intrinsically universal. Algorithmica 74(2), 812–850 (2016)MathSciNetCrossRefMATH

Doty, D.: Producibility in hierarchical self-assembly. Nat. Comput. 15(1), 41–49 (2016)MathSciNetCrossRefMATH

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., Reishus, D., Schweller, R.T., Summers, S.M.: Strong fault-tolerance for self-assembly with fuzzy temperature. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 417–426 (2010)

12.

Doty, D., Patitz, M.J., Summers, S.M.: Limitations of self-assembly at temperature one. In: Deaton, R., Suyama, A. (eds.) DNA 2009. LNCS, vol. 5877, pp. 35–44. Springer, Heidelberg (2009). doi:10.1007/978-3-642-10604-0_4 CrossRef

13.

Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676–686 (1982)MathSciNetCrossRefMATH

14.

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, pp. 571–580 (2006)

15.

Luhrs, C.: Polyomino-safe DNA self-assembly via block replacement. Nat. Comput. 9(1), 97–109 (2010)MathSciNetCrossRefMATH

16.

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

17.

Meunier, P.-E.: The self-assembly of paths and squares at temperature 1. Technical report, arXiv (2013). http://arxiv.org/abs/1312.1299

18.

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

19.

Patitz, M.J., Rogers, T.A., Schweller, R.T., Summers, S.M., Winslow, A.: Resiliency to multiple nucleation in temperature-1 self-assembly. In: Rondelez, Y., Woods, D. (eds.) DNA 2016. LNCS, vol. 9818, pp. 98–113. Springer, Cham (2016). doi:10.1007/978-3-319-43994-5_7 CrossRef

20.

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)

21.

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

22.

Schweller, R., Winslow, A., Wylie, T.: Verification in staged tile self-assembly. In: Patitz, M.J., Stannett, M. (eds.) UCNC 2017. LNCS, vol. 10240, pp. 98–112. Springer, Cham (2017). doi:10.1007/978-3-319-58187-3_8 CrossRef

23.

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

24.

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

25.

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

26.

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

27.

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

28.

Woods, D.: Intrinsic universality and the computational power of self-assembly. Philos. Trans. R. Soc. A 373, 2015 (2046)

Titel: Complexities for High-Temperature Two-Handed Tile Self-assembly
verfasst von: Robert Schweller
Andrew Winslow
Tim Wylie
Verlag: Springer International Publishing
Buch: DNA Computing and Molecular Programming
Print ISBN: 978-3-319-66798-0

Electronic ISBN: 978-3-319-66799-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-66799-7_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner