Abstract
Ma and Lombardi (2009) introduce and study the Pattern self-Assembly Tile set Synthesis (PATS) problem. In particular they show that the optimization version of the PATS 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 |
|---|---|
| Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 58-72 |
| Number of pages | 15 |
| Volume | 7433 LNCS |
| DOIs | |
| Publication status | Published - 2012 |
| Externally published | Yes |
| Event | 18th International Conference on DNA Computing and Molecular Programming, DNA 18 - Aarhus, Denmark Duration: Aug 14 2012 → Aug 17 2012 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 7433 LNCS |
| ISSN (Print) | 03029743 |
| ISSN (Electronic) | 16113349 |
Other
| Other | 18th International Conference on DNA Computing and Molecular Programming, DNA 18 |
|---|---|
| Country | Denmark |
| City | Aarhus |
| Period | 8/14/12 → 8/17/12 |
Fingerprint
ASJC Scopus subject areas
- Computer Science(all)
- Theoretical Computer Science
Cite this
Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. / Czeizler, Eugen; Popa, Alexandru.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7433 LNCS 2012. p. 58-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7433 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
AU - Czeizler, Eugen
AU - Popa, Alexandru
PY - 2012
Y1 - 2012
N2 - Ma and Lombardi (2009) introduce and study the Pattern self-Assembly Tile set Synthesis (PATS) problem. In particular they show that the optimization version of the PATS 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 - Ma and Lombardi (2009) introduce and study the Pattern self-Assembly Tile set Synthesis (PATS) problem. In particular they show that the optimization version of the PATS 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.
UR - http://www.scopus.com/inward/record.url?scp=84865264546&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865264546&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32208-2_5
DO - 10.1007/978-3-642-32208-2_5
M3 - Conference contribution
AN - SCOPUS:84865264546
SN - 9783642322075
VL - 7433 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 58
EP - 72
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -