zbMATH — the first resource for mathematics

Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly. (English) Zbl 1372.68097
Stefanovic, Darko (ed.) et al., DNA computing and molecular programming. 18th international conference, DNA 18, Aarhus, Denmark, August 14–17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32207-5/pbk). Lecture Notes in Computer Science 7433, 58-72 (2012).
Summary: X. Ma and F. Lombardi [“On the computational complexity of tile set synthesis for DNA self-assembly”, IEEE Trans. Circuits Syst. II: Express Briefs 56, No. 1, 31–35 (2009; doi:10.1109/TCSII.2008.2010161)] 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.
For the entire collection see [Zbl 1250.68051].

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI