PATS problem and tile set generation

From self-assembly wiki
Revision as of 15:16, 27 May 2014 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

In order to produce a surface with a complex template for potentially guiding the attachment of functional materials, an interesting problem in tile-based self-assembly is the Patterned self-Assembly Tile set Synthesis (PATS) problem. The PATS problem is concerned with finding the minimal tile set which will self-assemble into a given 2-D pattern of colors (where tile types are assumed to be assigned colors) and was introduced by Ma and Lombardi in [1]. In [2] Göös and Orponen presented an exhaustive branch-and-bound algorithm which works well for finding exact solutions to patterns of sizes up to 6 × 6, and approximate solutions for larger patterns. In [3], Lempiäinen, Czeizler, and Orponen modified the previous algorithm to be more efficient (but still require exponential time). In [4], Czeizler and Popa proved that the PATS problem is NP-hard, and in [5] Seki examined the parameterized version of the problem, c-PATS, in which any given pattern is guaranteed to contain at most c colors, and showed that 59-PATS is NP-hard by using a 3-SAT reduction.

References

  1. Xiaojun Ma, Fabrizio Lombardi - Synthesis of Tile Sets for DNA Self-Assembly
    IEEE Trans. on CAD of Integrated Circuits and Systems 27(5):963-967,2008
    Bibtex
    Author : Xiaojun Ma, Fabrizio Lombardi
    Title : Synthesis of Tile Sets for DNA Self-Assembly
    In : IEEE Trans. on CAD of Integrated Circuits and Systems -
    Address :
    Date : 2008
  2. Mika Göös, Pekka Orponen - Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
    DNA pp. 71-82,2010
    Bibtex
    Author : Mika Göös, Pekka Orponen
    Title : Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
    In : DNA -
    Address :
    Date : 2010
  3. Lempiäinen, Tuomo, Czeizler, Eugen, Orponen, Pekka - Synthesizing small and reliable tile sets for patterned DNA self-assembly
    Proceedings of the 17th international conference on DNA computing and molecular programming pp. 145--159, Berlin, Heidelberg,2011
    http://dl.acm.org/citation.cfm?id=2042033.2042048
    Bibtex
    Author : Lempiäinen, Tuomo, Czeizler, Eugen, Orponen, Pekka
    Title : Synthesizing small and reliable tile sets for patterned DNA self-assembly
    In : Proceedings of the 17th international conference on DNA computing and molecular programming -
    Address : Berlin, Heidelberg
    Date : 2011
  4. Czeizler, Eugen, Popa, Alexandru - Synthesizing Minimal Tile Sets for Complex Patterns in the Framework of Patterned DNA Self-Assembly
    ,2012
    Bibtex
    Author : Czeizler, Eugen, Popa, Alexandru
    Title : Synthesizing Minimal Tile Sets for Complex Patterns in the Framework of Patterned DNA Self-Assembly
    In : -
    Address :
    Date : 2012
  5. Shinnosuke Seki - Combinatorial Optimization in Pattern Assembly
    Technical Report, Computing Research Repository (1301.3771),2013
    Bibtex
    Author : Shinnosuke Seki
    Title : Combinatorial Optimization in Pattern Assembly
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2013