Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly

Eugen Czeizler, Alexandru Popa

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

The Pattern self-Assembly Tile set Synthesis (PATS) problem asks to determine a set of coloured tiles which, left alone in the solution, would self-assemble to implement a given rectangular colour pattern. Ma and Lombardi (2009) introduce and study the PATS problem from a combinatorial optimization point of view, trying to find algorithms which would minimize the required number of distinct tile types. In particular, they claimed that the above optimization problem is NP-hard. However, their NP-hardness proof turns out to be incorrect. Our main result is to give a correct NP-hardness proof via a reduction from the 3SAT. By definition, the PATS problem assumes that the assembly of a pattern starts always from an "L"-shaped seed structure, fixing the borders of the pattern. In this context, we study the assembly complexity of various pattern families and we show how to construct families of patterns which require a non-constant number of tiles to be assembled.

Original languageEnglish
Pages (from-to)23-37
Number of pages15
JournalTheoretical Computer Science
Volume499
DOIs
Publication statusPublished - Aug 12 2013
Externally publishedYes

Fingerprint

Self-assembly
Tile
Self assembly
DNA
NP-hardness
Synthesis
Hardness
Combinatorial optimization
Seed
Framework
Computational complexity
Combinatorial Optimization
Color
NP-complete problem
Optimization Problem
Distinct
Minimise

Keywords

  • DNA self-assembly
  • Minimal tile sets
  • NP-hardness
  • Pattern assembly
  • Tile assembly model

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. / Czeizler, Eugen; Popa, Alexandru.

In: Theoretical Computer Science, Vol. 499, 12.08.2013, p. 23-37.

Research output: Contribution to journalArticle

@article{92e3e76e57ef424491a1776d4ca7ff7a,
title = "Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly",
abstract = "The Pattern self-Assembly Tile set Synthesis (PATS) problem asks to determine a set of coloured tiles which, left alone in the solution, would self-assemble to implement a given rectangular colour pattern. Ma and Lombardi (2009) introduce and study the PATS problem from a combinatorial optimization point of view, trying to find algorithms which would minimize the required number of distinct tile types. In particular, they claimed that the above optimization problem is NP-hard. However, their NP-hardness proof turns out to be incorrect. Our main result is to give a correct NP-hardness proof via a reduction from the 3SAT. By definition, the PATS problem assumes that the assembly of a pattern starts always from an {"}L{"}-shaped seed structure, fixing the borders of the pattern. In this context, we study the assembly complexity of various pattern families and we show how to construct families of patterns which require a non-constant number of tiles to be assembled.",
keywords = "DNA self-assembly, Minimal tile sets, NP-hardness, Pattern assembly, Tile assembly model",
author = "Eugen Czeizler and Alexandru Popa",
year = "2013",
month = "8",
day = "12",
doi = "10.1016/j.tcs.2013.05.009",
language = "English",
volume = "499",
pages = "23--37",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly

AU - Czeizler, Eugen

AU - Popa, Alexandru

PY - 2013/8/12

Y1 - 2013/8/12

N2 - The Pattern self-Assembly Tile set Synthesis (PATS) problem asks to determine a set of coloured tiles which, left alone in the solution, would self-assemble to implement a given rectangular colour pattern. Ma and Lombardi (2009) introduce and study the PATS problem from a combinatorial optimization point of view, trying to find algorithms which would minimize the required number of distinct tile types. In particular, they claimed that the above optimization problem is NP-hard. However, their NP-hardness proof turns out to be incorrect. Our main result is to give a correct NP-hardness proof via a reduction from the 3SAT. By definition, the PATS problem assumes that the assembly of a pattern starts always from an "L"-shaped seed structure, fixing the borders of the pattern. In this context, we study the assembly complexity of various pattern families and we show how to construct families of patterns which require a non-constant number of tiles to be assembled.

AB - The Pattern self-Assembly Tile set Synthesis (PATS) problem asks to determine a set of coloured tiles which, left alone in the solution, would self-assemble to implement a given rectangular colour pattern. Ma and Lombardi (2009) introduce and study the PATS problem from a combinatorial optimization point of view, trying to find algorithms which would minimize the required number of distinct tile types. In particular, they claimed that the above optimization problem is NP-hard. However, their NP-hardness proof turns out to be incorrect. Our main result is to give a correct NP-hardness proof via a reduction from the 3SAT. By definition, the PATS problem assumes that the assembly of a pattern starts always from an "L"-shaped seed structure, fixing the borders of the pattern. In this context, we study the assembly complexity of various pattern families and we show how to construct families of patterns which require a non-constant number of tiles to be assembled.

KW - DNA self-assembly

KW - Minimal tile sets

KW - NP-hardness

KW - Pattern assembly

KW - Tile assembly model

UR - http://www.scopus.com/inward/record.url?scp=84881186834&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881186834&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2013.05.009

DO - 10.1016/j.tcs.2013.05.009

M3 - Article

VL - 499

SP - 23

EP - 37

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -