Difference between revisions of "PATS problem and tile set generation"
| 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 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. | 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. | ||
| + | |||
| + | There are also additional results related to the [http://self-assembly.net/wiki/index.php/Pattern_Self-Assembly self-assembly of patterns] on squares. | ||
==References== | ==References== | ||
Latest revision as of 11:28, 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.
There are also additional results related to the self-assembly of patterns on squares.
References
- ↑
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
- BibtexAuthor : 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
- ↑
Mika Göös, Pekka Orponen - Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
- ↑
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
BibtexAuthor : 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
- ↑
Czeizler, Eugen, Popa, Alexandru - Synthesizing Minimal Tile Sets for Complex Patterns in the Framework of Patterned DNA Self-Assembly
- ↑
Shinnosuke Seki - Combinatorial Optimization in Pattern Assembly
- Technical Report, Computing Research Repository (1301.3771),2013
- BibtexAuthor : Shinnosuke Seki
Title : Combinatorial Optimization in Pattern Assembly
In : Technical Report, Computing Research Repository -
Address :
Date : 2013
