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

Eugen Czeizler; Alexandru Popa

doi:10.1007/978-3-642-32208-2_5

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

Eugen Czeizler, Alexandru Popa

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Citations (Scopus)

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	DNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings
Pages	58-72
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-32208-2_5
Publication status	Published - Aug 27 2012
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)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	18th International Conference on DNA Computing and Molecular Programming, DNA 18
Country	Denmark
City	Aarhus
Period	8/14/12 → 8/17/12

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-32208-2_5

Fingerprint Dive into the research topics of 'Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly'. Together they form a unique fingerprint.

Cite this

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 - 18th International Conference, DNA 18, Proceedings (pp. 58-72). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7433 LNCS). https://doi.org/10.1007/978-3-642-32208-2_5

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

DNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings. 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

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 - 18th International Conference, DNA 18, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7433 LNCS, pp. 58-72, 18th International Conference on DNA Computing and Molecular Programming, DNA 18, Aarhus, Denmark, 8/14/12. https://doi.org/10.1007/978-3-642-32208-2_5

Czeizler E, Popa A. Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. In DNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings. 2012. p. 58-72. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-32208-2_5

Czeizler, Eugen ; Popa, Alexandru. / Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. DNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings. 2012. pp. 58-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5ddbedbefa0447b5825349af560ad4f9,

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

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.",

author = "Eugen Czeizler and Alexandru Popa",

year = "2012",

month = aug,

day = "27",

doi = "10.1007/978-3-642-32208-2_5",

language = "English",

isbn = "9783642322075",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "58--72",

booktitle = "DNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings",

note = "18th International Conference on DNA Computing and Molecular Programming, DNA 18 ; Conference date: 14-08-2012 Through 17-08-2012",

}

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/8/27

Y1 - 2012/8/27

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

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 58

EP - 72

BT - DNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings

T2 - 18th International Conference on DNA Computing and Molecular Programming, DNA 18

Y2 - 14 August 2012 through 17 August 2012

ER -