Proving new directed tile complexity lower bounds at temperature 1 by folding between 2D and just-barely 3D self-assembly

期刊论文
发表日期：

2024年3月29日

查看全文

David Furcy,
Scott M. Summers,
Hailey Vadnais

摘要

We study the problem of determining the size of the smallest tile set that uniquely self-assembles into a given target shape in Winfree’s abstract Tile Assembly Model (aTAM), an elegant theoretical model of DNA tile self-assembly. This problem is also known as the “directed tile complexity” problem. We prove two main results related to the directed tile complexity problem within a variant of the aTAM in which the minimum binding strength threshold (temperature) is set to 1. For our first result, self-assembly happens in a “just-barely 3D” setting, where self-assembling unit cubes are allowed to be placed in the $z=0$ $z = 0$ and $z=1$ $z = 1$ planes. This is the same setting in which Furcy, Summers and Withers (DNA 2021) recently proved lower and upper bounds on the directed tile complexity of a just-barely 3D $k \times N$ $k \times N$ rectangle at temperature 1 of $\Omega \left( N^{\frac{1}{k}}\right) $ $Ω (N^{\frac{1}{k}})$ and $O\left( N^{\frac{1}{k-1}}+\log N\right) $ $O (N^{\frac{1}{k - 1}} + log N)$ , respectively, the latter of which does not hold for $k=2$ $k = 2$ . Our first result closes this gap for $k=2$ $k = 2$ by proving an asymptotically tight bound of $\Theta (N)$ $Θ (N)$ on the directed tile complexity of a just-barely 3D $2 \times N$ $2 \times N$ rectangle at temperature 1. Our proof uses a novel process by which a just-barely 3D assembly sequence is “unfolded” to an equivalent 2D assembly sequence. For our second result, we use the aforementioned lower bound by Furcy, Summers and Withers and a novel process that is complementary-in-spirit to our 3D-to-2D unfolding process, by which we “fold” a 2D tile assembly to an equivalent just-barely 3D assembly to prove a new lower bound on the directed tile complexity of a 2D $k \times N$ $k \times N$ rectangle at temperature 1 of $\Omega \left( \frac{N^{\frac{2}{k + (k \bmod 2)}}}{k} \right) $ $Ω (\frac{N^{\frac{2}{k + (k mod 2)}}}{k})$ . For fixed k, our new bound gives a nearly quadratic improvement over, and matches for general even values of $k < \frac{\log N}{\log \log N - \log \log \log N}$ $k < \frac{log N}{log log N - log log log N}$ the state of the art lower bound on the directed tile complexity of a $k \times N$ $k \times N$ rectangle at temperature 1 by Furcy, Summers and Wendlandt (DNA 2019) of $\Omega \left( N^{\frac{1}{k}}\right) $ $Ω (N^{\frac{1}{k}})$ . While both of our results represent improvements over previous corresponding state of the art results, the proofs thereof are facilitated by novel examples of reasoning about tile self-assembly happening in 2D (just-barely 3D) as though it is happening in just-barely 3D (2D).