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 publicationDNA Computing and Molecular Programming - 18th International Conference, DNA 18, Proceedings
Pages58-72
Number of pages15
DOIs
Publication statusPublished - Aug 27 2012
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)0302-9743
ISSN (Electronic)1611-3349

Other

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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