Top

Natural Computing

Published in:

01-06-2015

3-color bounded patterned self-assembly

Authors: Lila Kari, Steffen Kopecki, Shinnosuke Seki

Published in: Natural Computing | Issue 2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The problem of patterned self-assembly tile set synthesis (Pats) is to find a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the \(\mathrm {NP}\)-completeness of Pats and Seki showed that the Pats problem is already \(\mathrm {NP}\)-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains \(\mathrm {NP}\)-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is \(\mathrm {NP}\)-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the \(\mathrm {NP}\)-completeness of Pats which is more concise than the previous proofs.

previous article Exponential replication of patterns in the signal tile assembly model

next article Staged self-assembly and polyomino context-free grammars

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Czeizler E, Popa A (2012) Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. In: DNA computing and molecular programming, Springer, Berlin, pp 58–72

Göös M, Orponen P (2011) Synthesizing minimal tile sets for patterned DNA self-assembly. In: DNA computing and molecular programming, Springer, Berlin, pp. 71–82

Johnsen A, Kao MY, Seki S A manually-checkable proof for the NP-hardness of 11-colored patterned self-assembly of tile set synthesis. In: Preparation

Johnsen A, Kao MY, Seki S (2013) Computing minimum tile sets to self-assemble color patterns. In: ISAAC 2013 Proceedings of the 24th international symposium on algorithms and computation, LNCS, vol 8283, Springer, pp 699–710

Kari L, Kopecki S, Meunier PÉ, Patitz MJ, Seki S (2014) Binary pattern tile set synthesis is NP-hard. arXiv, preprint http://arxiv.org/abs/1404.0967arXiv:1404.0967

Kari L, Kopecki S, Seki S (2013) 3-color bounded patterned self-assembly. In: DNA computing and molecular programming–19th international conference, LNCS, vol 8141, Springer, pp 105–117

Liu F, Sha R, Seeman NC (1999) Modifying the surface features of two-dimensional DNA crystals. J Am Chem Soc 121(5):917–922CrossRef

Ma X, Lombardi F (2008) Synthesis of tile sets for DNA self-assembly. IEEE Trans Comput Aided Des Integr Circuits Syst 27(5):963–967CrossRef

Papadimitriou CH (2003) Computational complexity. Wiley, New York

Rothemund PW, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424CrossRef

Rothemund PW, Winfree E (2000) The program-size complexity of self-assembled squares. In: Proceedings of the thirty-second annual ACM symposium on theory of computing, pp 459–468, ACM

Seki S (2013) Combinatorial optimization in pattern assembly (extended abstract). In: Prodeedings of unconventional computation and natural computation, 12th international conference, LNCS, vol 7956, pp 220–231

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

Winfree E, Liu F, Wenzler LA, Seeman NC (1998) Design and self-assembly of two-dimensional DNA crystals. Nature 394(6693):539–544CrossRef

Zhang J, Liu Y, Ke Y, Yan H (2006) Periodic square-like gold nanoparticle arrays templated by self-assembled 2D DNA nanogrids on a surface. Nano letters 6(2):248–251CrossRef

Title: 3-color bounded patterned self-assembly
Authors: Lila Kari
Steffen Kopecki
Shinnosuke Seki
Publication date: 01-06-2015
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2015
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-014-9434-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2015

DNA walker circuits: computational potential, design, and verification

The parameters setting of a changing range genetic algorithm

Preface

Leaderless deterministic chemical reaction networks

Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles

Empirical modeling using genetic programming: a survey of issues and approaches

Premium Partner