Difference between revisions of "PATS problem and tile set generation"

From self-assembly wiki
Jump to navigation Jump to search
Line 1: Line 1:
−
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 <ref name=MaLombardi08 />.  In <ref name=GoosOrponen10 /> 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 <ref name=LempCzeilOrp11 />, Lempiäinen, Czeizler, and Orponen modified the previous algorithm to be more efficient (but still require exponential time).  In <ref name=CzeizlerPopaPATS />, Czeizler and Popa proved that the PATS problem is NP-hard, and in <ref name=SekiPATS /> 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.
+
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 <ref name=MaLombardi08 />.  In <ref name=GoosOrponen10 /> 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 <ref name=LempCzeilOrp11 />, Lempiäinen, Czeizler, and Orponen modified the previous algorithm to be more efficient (but still require exponential time).  In a series of results that culminated in showing that [http://self-assembly.net/wiki/index.php/Binary_pattern_tile_set_synthesis_is_NP-hard the PATS problem is NP-hard even for 2-colored patterns], in <ref name=CzeizlerPopaPATS /> Czeizler and Popa proved that the PATS problem is NP-hard, and in <ref name=SekiPATS /> 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==
 
==References==

Revision as of 11:13, 4 March 2024

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 a series of results that culminated in showing that the PATS problem is NP-hard even for 2-colored patterns, 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
Retrieved from "http://self-assembly.net/wiki/index.php?title=PATS_problem_and_tile_set_generation&oldid=1959"