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 language | English |
|---|---|
| Pages (from-to) | 23-37 |
| Number of pages | 15 |
| Journal | Theoretical Computer Science |
| Volume | 499 |
| DOIs | |
| Publication status | Published - Aug 12 2013 |
| Externally published | Yes |
Fingerprint
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 journal › Article
}
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 -