Difference between revisions of "Pattern Self-Assembly"

From self-assembly wiki
Jump to navigation Jump to search
 
(20 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
[[Category:Results in the aTAM]]
 
[[Category:Results in the aTAM]]
  
−
==Abstract==
+
When designing a self-assembling system, the desired goal is often the creation of an assembly with a target shape. However, it may instead be an assembly that serves as surface onto which a desired pattern of cargo molecules are attached. In the domain of the  [[Abstract_Tile_Assembly_Model_(aTAM)| aTAM]], this problem is typically represented as the problem of [[Weak_Self-Assembly | weakly self-assembling]] a pattern of colored tiles, which can be thought of as forming structures on which colored patterns are “painted.” In <ref name=PatternsArxiv/> they discuss results related to the complexity, in terms of the unique tile types required, of assembling various patterns. The following results are generally concerned with the optimal complexity of construction of $n \times n$ patterns. However, the problem of designing optimal tile sets to self-assemble patterned squares, the [http://self-assembly.net/wiki/index.php/PATS_problem_and_tile_set_generation PATS problem], has also been widely studied.
−
In the abstract Tile Assembly Model, self-assembling systems consisting of tiles of different colors can form structures on which
 
−
colored patterns are “painted.” We explore the complexity, in terms of
 
−
the unique tile types required, of assembling various patterns, proving
 
−
several upper and lower bounds.
 
  
−
==Overview==
+
=== Simple patterns ===
  
−
This paper concerns itself with the optimal complexity of construction of nxn patterns.
+
We first discuss constructions for three different "simple patterns" on the surface of $n \times n$ square. A '''single-pixel pattern''' is a pattern where a single tile is set to black and all others are white. A '''multi-pixel pattern''' is a pattern with a set of locations set to black such that the locations are at least $(\log n)$ distance away from each other. A '''striped pattern''' is a pattern where black stripes repeat themselves every $i$ tiles horizontally and $j$ tiles vertically. The single-pixel and striped patterns can be built using $O(\log n)$ tile types making relatively straightforward uses of binary counters, and the multi-pixel pattern for a set of $L$ black points can be built using $O(|L|\log n)$ tile types.  
−
 
 
−
We first show constructions for three different simple patterns. A single-pixel pattern is a pattern where a single tile is set to black. A multi-pixel pattern is a pattern with a set of locations set to black such that the locations are $(\log n)$ distance away from each other. A striped pattern is a pattern where black stripes repeat themselves every $i$ times horizontally and $j$ times vertically. This paper provides constructions for each of these that use $O(\log n)$ tile types.  
 
  
 
{| class="wikitable"
 
{| class="wikitable"
Line 19: Line 13:
 
| [[File:MultiPixel.png|thumb|center|Multiple black tiles]]
 
| [[File:MultiPixel.png|thumb|center|Multiple black tiles]]
 
| [[File:StripesPattern.png|thumb|center|Repeating black tiles]]
 
| [[File:StripesPattern.png|thumb|center|Repeating black tiles]]
−
| [[File:GridRepeat.png|thumb|center|A repeated pattern in a grid. The spines are colored to show the counter values embedded in them. Red mean 1 and blue mean 0]]
 
 
|}
 
|}
  
−
This paper also shows that for almost all positive integers n, the tile complexity of weakly
+
=== Arbitrary 2-colored patterns ===
−
self-assembling 2-colored patterns on a n × n squares in the aTAM is $\Theta(\frac{n^2}{\log n})$. This is done by proving this is lower bound for almost all patterns and by providing a construction for building any n x n square.  
+
 
 +
Another pair of results show tight bounds on the tile complexity of weakly self-assembling 2-colored patterns on $n \times n$ squares. A lower bound, using an information theoretic argument, shows that for almost all positive integers $n$, the tile complexity of weakly
 +
self-assembling 2-colored patterns on a $n \times n$ squares in the aTAM is $\Omega(\frac{n^2}{\log n})$. The matching upper bound of $O(\frac{n^2}{\log n})$ is shown using a relatively simple construction that grows a hard-coded ''skeleton'' with ''ribs'' spaced out by approximately $\log n$ locations and shared ''filler'' tiles filling in the locations between ribs. An extension to that construction shows how multiple copies of a pattern can be efficiently repeated across the surface of a square.
 +
 
 +
In the Software provided below, a script called ''tiled_images'' can be used to convert image files into aTAM systems that weakly self-assemble black and white versions of the images.
  
 
{| class="wikitable"
 
{| class="wikitable"
Line 29: Line 26:
 
| [[File:Skeleton1.png|thumb|center|The skeleton. The green tile represents the seed]]  
 
| [[File:Skeleton1.png|thumb|center|The skeleton. The green tile represents the seed]]  
 
| [[File:SkeletonFilled1.png|thumb|center|The square once the ribs of the skeleton have filled in (blue growing left, yellow growing right)]]
 
| [[File:SkeletonFilled1.png|thumb|center|The square once the ribs of the skeleton have filled in (blue growing left, yellow growing right)]]
 +
| [[File:GridRepeat.png|thumb|center|A repeated pattern in a grid. The spines are colored to show the counter values embedded in them. Red mean 1 and blue mean 0]]
 
|}
 
|}
  
−
This paper also shows that almost any pattern $p_n$ may be generated such that $O \frac{\log n} {\log \log n}$ tile types are required. And there exist patterns, both finite and infinite, that can be weakly self-assembled using asymptotically fewer tile types using barely-3DaTAM systems than by regular, 2D aTam Systems.
 
  
−
A pattern consists of a bit-sequence of length $m$ such that the north row, and west column of an $mxm$ square are made up of that tile representing that bit sequence of length $m$, with colors associated being either $\{White, Green, Black\}$ or $\{Red, Green, Black\}$. Each bound propagates a signal which interacts with the bound on its perpendicular, creating an intersection between the two bits $\{00, 01, 10, 11\}$. Each intersection is assigned its own color within the interior along $\{Aqua, Blue, Yellow, Fuchsia\}$.
+
=== Barely-3DaTAM patterns ===
 +
 
 +
There exist patterns, both finite and infinite, that can be weakly self-assembled using asymptotically (in fact, exponentially) fewer tile types using barely-3DaTAM systems (i.e. those which use only 2 planes of the third dimension) than by regular, 2D aTAM Systems.
 +
 
 +
Each of these patterns is generated using of a bit-sequence of length $m$ such that the north row, and west column of an $m \times m$ square are made up of colors representing that bit sequence. The pattern represents the intersection between the bits of each column and row, with the possible pairings of $\{00, 01, 10, 11\}$ and unique colors assigned to each. The $m \times m$ pattern is repeated a large number of times over the surface of a larger $n \times n$ square, and there is a set of unique colors for the boundaries of each $m \times m$ ''cell'', as well as for the interior locations of each cell.
 +
 
 +
Using a form of ''diagonalization'', a Barely-3DaTAM construction that uses $O( \frac{\log n} {\log \log n})$ tile types simulates all aTAM systems with $\le n$ tile types (whose number we will refer to as $m$) and constructs the bit sequence of length $m$ such that the colored pattern generated for it is guaranteed to differ from the assemblies produced by every one of those systems. This is done inside of a square assembly in the plane $z = 0$. Then, that pattern grows upward into plane $z = 1$ where it is used to cover the surface of the square in $z = 0$ with the colored pattern previously mentioned.
  
−
Patterns may be generated in the 2D plane using $O( \frac{\log n} {\log \log n})$ tile types, and it has been proven that this is the most efficient way to generate almost all patterns. This is done through the exhibition of pattern $p_n$ such that every 2D aTAM system, $\mathcal{T}_{\le n}$, with fewer than $n$ tile types fails to weakly self-assemble $p_n$. For each $\mathcal{T}_{\le n}$, $p_n$ is defined in such a way that its color differs in at least one location in each “cell” of a repeating grid of cells.
 
  
 
{| class="wikitable"
 
{| class="wikitable"
Line 43: Line 45:
 
|}
 
|}
  
−
Patterns generated within 2D aTAM systems, and barely-3DaTAM systems may be exhibited in the attached software “2_layer_patterns”, with usage instructions detailed in the README.
+
Portions of the construction used to generate the patterns of the Barely-3DaTAM systems may be generated by the attached software “2_layered_patterns”, with usage instructions detailed in the README.
  
−
These patterns may be extended to infinitely cover the 2D plane in a cross-like shape through the use of grid-reconstruction utilizing $O(1)$ unique tile type, with subsequent patterns copying themselves along the cross-like shape, as is described in the below figure Any bit-sequence of length n may be constructed to tile both finitely, or infinitely through the use of the attached piece of software “infinite_tiling_patterns”, with usage instructions detailed in the README.
+
These patterns may also be extended to infinitely cover the 2D plane in a cross-like shape through the use of grid-reconstruction utilizing $O(1)$ unique tile type, with subsequent patterns copying themselves along the cross-like shape, as is described in the below figure Any bit-sequence of length $n$ may be constructed to tile both finitely, or infinitely through the use of the attached piece of software “infinite_tiling_patterns”, with usage instructions detailed in the README.
 +
 
 +
{| class="wikitable"
 +
|-
 +
| [[File:Infinite-assembly-high-level.png|thumb|center|High-level illustration of the infinite assembly of $p_n$ across $\mathbb{Z}^2$.]]
 +
| [[File:Infinite-assembly-0110010010101-marked.png|thumb|center|Infinite assembly of the bit sequence "0110010010101", with creation and bound tiles marked as to demonstration cross-like growth.]]
 +
|}
 +
 
 +
 
 +
==Software==
  
 
A set of Python and Java programs that generate aTAM systems related to these constructions, as well as example systems, can be downloaded here:
 
A set of Python and Java programs that generate aTAM systems related to these constructions, as well as example systems, can be downloaded here:
  
−
[http://self-assembly.net/software/SelfAssembledPatterns/ SelfAssembledPatterns code] (Note that the latest version can be found at the bottom of the list.)
+
[[Pattern Self-Assembly Software]]
 +
 
 +
They can be simulated using [[WebTAS]], [[PyTAS]], or [[ISU_TAS]].
 +
 
 +
 
 +
==References==
 +
<references>
 +
 
 +
<ref name =PatternsArxiv><bibtex>
 +
@techreport{PatternsArxiv,
 +
    author = {Drake, Phillip and Patitz, Matthew J. and Summers, Scott M. and Tracy, Tyler},
 +
    title = {Self-Assembly of Patterns in the abstract Tile Assembly Model},
 +
    number = "2402.16284",
 +
    institution = "arXiv",
 +
    year = {2024},
 +
    url = "https://arxiv.org/abs/2402.16284"
 +
}
 +
</bibtex></ref>
 +
 
 +
</references>

Latest revision as of 09:43, 4 June 2024


When designing a self-assembling system, the desired goal is often the creation of an assembly with a target shape. However, it may instead be an assembly that serves as surface onto which a desired pattern of cargo molecules are attached. In the domain of the aTAM, this problem is typically represented as the problem of weakly self-assembling a pattern of colored tiles, which can be thought of as forming structures on which colored patterns are “painted.” In [1] they discuss results related to the complexity, in terms of the unique tile types required, of assembling various patterns. The following results are generally concerned with the optimal complexity of construction of \(n \times n\) patterns. However, the problem of designing optimal tile sets to self-assemble patterned squares, the PATS problem, has also been widely studied.

Simple patterns

We first discuss constructions for three different "simple patterns" on the surface of \(n \times n\) square. A single-pixel pattern is a pattern where a single tile is set to black and all others are white. A multi-pixel pattern is a pattern with a set of locations set to black such that the locations are at least \((\log n)\) distance away from each other. A striped pattern is a pattern where black stripes repeat themselves every \(i\) tiles horizontally and \(j\) tiles vertically. The single-pixel and striped patterns can be built using \(O(\log n)\) tile types making relatively straightforward uses of binary counters, and the multi-pixel pattern for a set of \(L\) black points can be built using \(O(|L|\log n)\) tile types.

A single black tile
Multiple black tiles
Repeating black tiles

Arbitrary 2-colored patterns

Another pair of results show tight bounds on the tile complexity of weakly self-assembling 2-colored patterns on \(n \times n\) squares. A lower bound, using an information theoretic argument, shows that for almost all positive integers \(n\), the tile complexity of weakly self-assembling 2-colored patterns on a \(n \times n\) squares in the aTAM is \(\Omega(\frac{n^2}{\log n})\). The matching upper bound of \(O(\frac{n^2}{\log n})\) is shown using a relatively simple construction that grows a hard-coded skeleton with ribs spaced out by approximately \(\log n\) locations and shared filler tiles filling in the locations between ribs. An extension to that construction shows how multiple copies of a pattern can be efficiently repeated across the surface of a square.

In the Software provided below, a script called tiled_images can be used to convert image files into aTAM systems that weakly self-assemble black and white versions of the images.

The skeleton. The green tile represents the seed
The square once the ribs of the skeleton have filled in (blue growing left, yellow growing right)
A repeated pattern in a grid. The spines are colored to show the counter values embedded in them. Red mean 1 and blue mean 0


Barely-3DaTAM patterns

There exist patterns, both finite and infinite, that can be weakly self-assembled using asymptotically (in fact, exponentially) fewer tile types using barely-3DaTAM systems (i.e. those which use only 2 planes of the third dimension) than by regular, 2D aTAM Systems.

Each of these patterns is generated using of a bit-sequence of length \(m\) such that the north row, and west column of an \(m \times m\) square are made up of colors representing that bit sequence. The pattern represents the intersection between the bits of each column and row, with the possible pairings of \(\{00, 01, 10, 11\}\) and unique colors assigned to each. The \(m \times m\) pattern is repeated a large number of times over the surface of a larger \(n \times n\) square, and there is a set of unique colors for the boundaries of each \(m \times m\) cell, as well as for the interior locations of each cell.

Using a form of diagonalization, a Barely-3DaTAM construction that uses \(O( \frac{\log n} {\log \log n})\) tile types simulates all aTAM systems with \(\le n\) tile types (whose number we will refer to as \(m\)) and constructs the bit sequence of length \(m\) such that the colored pattern generated for it is guaranteed to differ from the assemblies produced by every one of those systems. This is done inside of a square assembly in the plane \(z = 0\). Then, that pattern grows upward into plane \(z = 1\) where it is used to cover the surface of the square in \(z = 0\) with the colored pattern previously mentioned.


Visualization of the growth of a pattern \(p_n\) from the seed row.
Finite assembly of the bit-sequence "00101010".

Portions of the construction used to generate the patterns of the Barely-3DaTAM systems may be generated by the attached software “2_layered_patterns”, with usage instructions detailed in the README.

These patterns may also be extended to infinitely cover the 2D plane in a cross-like shape through the use of grid-reconstruction utilizing \(O(1)\) unique tile type, with subsequent patterns copying themselves along the cross-like shape, as is described in the below figure Any bit-sequence of length \(n\) may be constructed to tile both finitely, or infinitely through the use of the attached piece of software “infinite_tiling_patterns”, with usage instructions detailed in the README.

High-level illustration of the infinite assembly of \(p_n\) across \(\mathbb{Z}^2\).
Infinite assembly of the bit sequence "0110010010101", with creation and bound tiles marked as to demonstration cross-like growth.


Software

A set of Python and Java programs that generate aTAM systems related to these constructions, as well as example systems, can be downloaded here:

Pattern Self-Assembly Software

They can be simulated using WebTAS, PyTAS, or ISU_TAS.


References

  1. ↑ Drake, Phillip, Patitz, Matthew J., Summers, Scott M., Tracy, Tyler - Self-Assembly of Patterns in the abstract Tile Assembly Model
    Technical Report, arXiv (2402.16284),2024
    https://arxiv.org/abs/2402.16284
    Bibtex
    Author : Drake, Phillip, Patitz, Matthew J., Summers, Scott M., Tracy, Tyler
    Title : Self-Assembly of Patterns in the abstract Tile Assembly Model
    In : Technical Report, arXiv -
    Address :
    Date : 2024
Retrieved from "http://self-assembly.net/wiki/index.php?title=Pattern_Self-Assembly&oldid=1992"