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

Eugen Czeizler, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages58-72
Number of pages15
Volume7433 LNCS
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event18th International Conference on DNA Computing and Molecular Programming, DNA 18 - Aarhus, Denmark
Duration: Aug 14 2012Aug 17 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7433 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other18th International Conference on DNA Computing and Molecular Programming, DNA 18
CountryDenmark
CityAarhus
Period8/14/128/17/12

Fingerprint

Self-assembly
Tile
Self assembly
DNA
Hardness
NP-hardness
Synthesis
Seed
Computational complexity
Framework
NP-complete problem
Optimization

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Czeizler, E., & Popa, A. (2012). Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7433 LNCS, 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.

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 proceedingConference contribution

Czeizler, E & Popa, A 2012, Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 7433 LNCS, 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 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)). 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7433 LNCS 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",
doi = "10.1007/978-3-642-32208-2_5",
language = "English",
isbn = "9783642322075",
volume = "7433 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "58--72",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

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

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 -