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

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

EUGEN Czeizler POPA Alexandru

Rok publikování 2013
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.sciencedirect.com/science/article/pii/S0304397513003605
Doi http://dx.doi.org/10.1016/j.tcs.2013.05.009
Obor Informatika
Klíčová slova DNA self-assembly; Tile assembly model; Pattern assembly; Minimal tile sets; NP-hardness
Popis The Pattern self-Assembly Tile set Synthesis (PATS) problem asks to determine a set of coloured tiles which, left alone in the solution, would self-assemble to implement a given rectangular colour pattern. Ma and Lombardi (2009) introduce and study the PATS problem from a combinatorial optimization point of view, trying to find algorithms which would minimize the required number of distinct tile types. In particular, they claimed that the above optimization 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.