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

J 2013

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

EUGEN, Czeizler and Alexandru POPA

Basic information

Original name

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

Authors

EUGEN, Czeizler and Alexandru POPA

Edition

Theoretical Computer Science, Elsevier, 2013, 0304-3975

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 0.516

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1016/j.tcs.2013.05.009

UT WoS

000323809200003

Keywords in English

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

Abstract

V originále

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.

Links

LG13010, research and development project

Name: Zastoupení ČR v European Research Consortium for Informatics and Mathematics (Acronym: ERCIM-CZ)

Investor: Ministry of Education, Youth and Sports of the CR

Citovat

EUGEN, Czeizler and Alexandru POPA. Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. Theoretical Computer Science. Elsevier, 2013, vol. 499, No 1, p. 23-37. ISSN 0304-3975. Available from: https://dx.doi.org/10.1016/j.tcs.2013.05.009.

@article{1179434,
   author = {Eugen, Czeizler and Popa, Alexandru},
   article_number = {1},
   doi = {http://dx.doi.org/10.1016/j.tcs.2013.05.009},
   keywords = {DNA self-assembly; Tile assembly model; Pattern assembly; Minimal tile sets; NP-hardness},
   language = {eng},
   issn = {0304-3975},
   journal = {Theoretical Computer Science},
   title = {Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly},
   url = {http://www.sciencedirect.com/science/article/pii/S0304397513003605},
   volume = {499},
   year = {2013}
}

TY  - JOUR
ID  - 1179434
AU  - Eugen, Czeizler - Popa, Alexandru
PY  - 2013
TI  - Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
JF  - Theoretical Computer Science
VL  - 499
IS  - 1
SP  - 23-37
EP  - 23-37
PB  - Elsevier
SN  - 03043975
KW  - DNA self-assembly
KW  - Tile assembly model
KW  - Pattern assembly
KW  - Minimal tile sets
KW  - NP-hardness
UR  - http://www.sciencedirect.com/science/article/pii/S0304397513003605
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.
ER  -

EUGEN, Czeizler and Alexandru POPA. Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. \textit{Theoretical Computer Science}. Elsevier, 2013, vol.~499, No~1, p.~23-37. ISSN~0304-3975. Available from: https://dx.doi.org/10.1016/j.tcs.2013.05.009.

Detailed Information on Publication Record