Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals

Natural Computing - In this paper, we prove that in the abstract Tile Assembly Model (aTAM), an accretion-based model which only allows for a single tile to attach to a growing assembly at each...     

Self-assembly of infinite structures: A survey

We survey some recent results related to the self-assembly of infinite structures in Winfree’s abstract Tile Assembly Model. These results include impossibility results, as well as the construction of novel tile assembly systems that produce computationally interesting shapes and patterns. Several open questions are also presented and motivated.     

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model

We introduce a hierarchical self assembly algorithm that produces the quasiperiodic patterns found in the Robinson tilings and suggest a practical implementation of this algorithm using DNA origami tiles. We modify the abstract Tile Assembly Model (aTAM), to include active signaling and glue activation in response to signals to coordinate the hierarchical assembly of Robinson patterns of arbitrary size from a small set of tiles according to the tile substitution algorithm that generates them. Enabling coordinated hierarchical assembly in the aTAM makes possible the efficient encoding of the recursive process of tile substitution.     

Self-assembly of decidable sets

The theme of this paper is computation in Winfree’s Abstract Tile Assembly Model (TAM). We first review a simple, well-known tile assembly system (the “wedge construction”) that is capable of universal computation. We then extend the wedge construction to prove the following result: if a set of natural numbers is decidable, then it and its complement’s canonical two-dimensional representation self-assemble. This leads to a novel characterization of decidable sets of natural numbers in terms of self-assembly. Finally, we show that our characterization is robust with respect to various (restrictive) geometrical constraints.     

Self-assembly of 4-sided fractals in the Two-Handed Tile Assembly Model

We consider the self-assembly of fractals in one of the most well-studied models of tile based self-assembling systems known as the Two-Handed Tile Assembly Model (2HAM). In particular, we focus our attention on a class of fractals called discrete self-similar fractals (a class of fractals that includes the discrete Sierpiński carpet). We present a 2HAM system that finitely self-assembles the discrete Sierpiński carpet with scale factor 1. Moreover, the 2HAM system that we give lends itself to being generalized and we describe how this system can be modified to obtain a 2HAM system that finitely self-assembles one of any fractal from an infinite set of fractals which we call 4-sided fractals. The 2HAM systems we give in this paper are the first examples of systems that finitely self-assemble discrete self-similar fractals at scale factor 1 in a purely growth model of self-assembly. Finally, we show that there exists a 3-sided fractal (which is not a tree fractal) that cannot be finitely self-assembled by any 2HAM system.

     

A minimal requirement for self-assembly of lines in polylogarithmic time

Self-assembly is the process in which small and simple components assemble into large and complex structures without explicit external control. The nubot model generalizes previous self-assembly models (e.g. the abstract Tile Assembly Model (aTAM)) to include active components which can actively move and undergo state changes. One main difference between the nubot model and previous self-assembly models is its ability to perform exponential growth with respect to time. In the paper, we study the problem of finding a minimal set of features in the nubot model which allows exponential growth to happen. We only focus on nubot systems which assemble a long line of nubots with a small number of supplementary layers. We prove that exponential growth is not possible with the limit of one supplementary layer and one state-change per nubot. On the other hand, if two supplementary layers are allowed, or the disappearance rule can be performed without a state change, then we can construct nubot systems which grow exponentially.     

Self-assembly of discrete self-similar fractals

In this paper, we search for theoretical limitations of the Tile Assembly Model (TAM), along with techniques to work around such limitations. Specifically, we investigate the self-assembly of fractal shapes in the TAM. We prove that no self-similar fractal weakly self-assembles at temperature 1 in a locally deterministic tile assembly system, and that certain kinds of discrete self-similar fractals do not strictly self-assemble at any temperature. Additionally, we extend the fiber construction of Lathrop et al. (2009) to show that any discrete self-similar fractal belonging to a particular class of “nice” discrete self-similar fractals has a fibered version that strictly self-assembles in the TAM.     

Strict self-assembly of discrete Sierpinski triangles

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004).Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i.e., the task of tiling a discrete Sierpinski triangle and nothing else.We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2007).     

Search methods for tile sets in patterned DNA self-assembly

The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model.     

Distributed agreement in tile self-assembly

Laboratory investigations have shown that a formal theory of fault-tolerance will be essential to harness nanoscale self-assembly as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena are related to the field of distributed computing. This paper formalizes some of that intuition. We construct tile assembly systems that are able to simulate the solution of the wait-free consensus problem in some distributed systems. (For potential future work, this may allow binding errors in tile assembly to be analyzed, and managed, with positive results in distributed computing, as a “blockage” in our tile assembly model is analogous to a crash failure in a distributed computing model.) We also define a strengthening of the “traditional” consensus problem, to make explicit an expectation about consensus algorithms that is often implicit in distributed computing literature. We show that solution of this strengthened consensus problem can be simulated by a two-dimensional tile assembly model only for two processes, whereas a three-dimensional tile assembly model can simulate its solution in a distributed system with any number of processes.     

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example, the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly process, but also to errors caused by malformed tiles.     

Tile Complexity of Approximate Squares

The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively. We consider the problem of building approximate squares in TAM. Given any $\varepsilon \in (0,\frac{1}{4}]$ we show how to construct squares whose sides are within (1±ε)N of any given positive integer N using $O( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types. We prove a matching lower bound by showing that $\varOmega( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types are necessary almost always to build squares of required approximate dimensions. In comparison, the optimal construction for a square of side exactly N in TAM uses $O(\frac{\log N}{\log \log N})$ tile types. The question of constructing approximate squares has been recently studied in a modified tile assembly model involving concentration programming. All our results are trivially translated into the concentration programming model by assuming arbitrary (non-zero) concentrations for our tile types. Indeed, the non-zero concentrations could be chosen by an adversary and our results would still hold. Our construction can get highly accurate squares using very few tile types and are feasible starting from values of N that are orders of magnitude smaller than the best comparable constructions previously suggested. At an accuracy of ε=0.01, the number of tile types used to achieve a square of size 10⁷ is just 58 and our constructions are proven to work for all N≥13130. If the concentrations of the tile types are carefully chosen, we prove that our construction assembles an L×L square in optimal assembly time O(L) where (1?ε)N≤L≤(1+ε)N.     

Polyomino-safe DNA self-assembly via block replacement

The standard abstract model for analyzing DNA self-assembly, aTAM, assumes that single tiles attach one by one to a larger structure. In practice, tiles may attach to each other forming structures called polyominoes and then attach to the assembly using bonds from multiple tiles. Such polyominoes may cause errors in systems designed with only aTAM in mind. In this paper, we first present a formal definition of when one tile system is a “block replacement” of another. Then we present a block replacement scheme for making any system that admits non-trivial block replacement polyomino-safe. In addition, we present a smaller block replacement scheme that makes the Chinese Remainder counter polyomino-safe and prove that the question of whether a system is polyomino-safe (or other similar properties) is undecidable. Finally, we show that applying our polyomino-safe system produces self-healing systems when applied to most self-healing systems.     

A Universal Accepting Hybrid Network of Evolutionary Processors

We propose a construction of an accepting hybrid network of evolutionary processors (AHNEP) which behaves as a universal device in the class of all these devices. We first construct a Turing machine which can simulate any AHNEP and then an AHNEP which simulates the Turing machine. We think that this approach can be applied to other bio-inspired computing models which are computationally complete.     

Error suppression mechanisms for DNA tile self-assembly and their simulation

Algorithmic self-assembly using DNA-based molecular tiles has been demonstrated to implement molecular computation. When several different types of DNA tile self-assemble, they can form large two-dimensional algorithmic patterns. Prior analysis predicted that the error rates of tile assembly can be reduced by optimizing physical parameters such as tile concentrations and temperature. However, in exchange, the growth speed is also very low. To improve the tradeoff between error rate and growth speed, we propose two novel error suppression mechanisms: the Protected Tile Mechanism (PTM) and the Layered Tile Mechanism (LTM). These utilize DNA protecting molecules to form kinetic barriers against spurious assembly. In order to analyze the performance of these two mechanisms, we introduce the hybridization state Tile Assembly Model (hsTAM), which evaluates intra-tile state changes as well as assembly state changes. Simulations using hsTAM suggest that the PTM and LTM improve the optimal tradeoff between error rate $\epsilonAlgorithmic self-assembly using DNA-based molecular tiles has been demonstrated to implement molecular computation. When several different types of DNA tile self-assemble, they can form large two-dimensional algorithmic patterns. Prior analysis predicted that the error rates of tile assembly can be reduced by optimizing physical parameters such as tile concentrations and temperature. However, in exchange, the growth speed is also very low. To improve the tradeoff between error rate and growth speed, we propose two novel error suppression mechanisms: the Protected Tile Mechanism (PTM) and the Layered Tile Mechanism (LTM). These utilize DNA protecting molecules to form kinetic barriers against spurious assembly. In order to analyze the performance of these two mechanisms, we introduce the hybridization state Tile Assembly Model (hsTAM), which evaluates intra-tile state changes as well as assembly state changes. Simulations using hsTAM suggest that the PTM and LTM improve the optimal tradeoff between error rate e\epsilon and growth speed r, from r ? be^2.0r \approx \beta \epsilon^{2.0} (for the conventional mechanism) to r ? be^1.4r \approx \beta \epsilon^{1.4} and r ? be^0.7r \approx \beta \epsilon^{0.7}, respectively.     

Negative Interactions in Irreversible Self-assembly

This paper explores the use of negative (i.e., repulsive) interactions in the abstract Tile Assembly Model defined by Winfree. Winfree in his Ph.D. thesis postulated negative interactions to be physically plausible, and Reif, Sahu, and Yin studied them in the context of reversible attachment operations. We investigate the power of negative interactions with irreversible attachments, and we achieve two main results. Our first result is an impossibility theorem: after t steps of assembly, Ω(t) tiles will be forever bound to an assembly, unable to detach. Thus negative glue strengths do not afford unlimited power to reuse tiles. Our second result is a positive one: we construct a set of tiles that can simulate an s-space-bounded, t-time-bounded Turing machine, while ensuring that no intermediate assembly grows larger than O(s), rather than O(s?t) as required by the standard Turing machine simulation with tiles. In addition to the space-bounded Turing machine simulation, we show another example application of negative glues: reducing the number of tile types required to assemble “thin” (n×o(logn/loglogn)) rectangles.     

Toward minimum size self-assembled counters

DNA self-assembly is a promising paradigm for nanotechnology. In this paper we study the problem of finding tile systems of minimum size that assemble a given shape in the Tile Assembly Model, defined by Rothemund and Winfree (Proceedings of the thirty-second annual ACM symposium on theory of computing, 2000). We present a tile system that assembles an rectangle in asymptotically optimal time. This tile system has only 7 tiles. Earlier constructions need at least 8 tiles (Chen et al. Proceedings of symposium on discrete algorithms, 2004). We managed to reduce the number of tiles without increasing the assembly time. The new tile system works at temperature 3. The new construction was found by the combination of exhaustive computerized search of the design space and manual adjustment of the search output.     

P Systems with Mobile Membranes

P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased).     

Approximate Self-Assembly of the Sierpinski Triangle

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in the Sierpinski triangle. More recently, Lathrop, Lutz, and Summers proved that the Sierpinski triangle cannot self-assemble in the ??strict?? sense in which tiles are not allowed to appear at positions outside the target structure. Here we investigate the strict self-assembly of sets that approximate the Sierpinski triangle. We show that every set that does strictly self-assemble disagrees with the Sierpinski triangle on a set with fractal dimension at least that of the Sierpinski triangle (??1.585), and that no subset of the Sierpinski triangle with fractal dimension greater than 1 strictly self-assembles. We show that our bounds are tight, even when restricted to supersets of the Sierpinski triangle, by presenting a strict self-assembly that adds communication fibers to the fractal structure without disturbing it. To verify this strict self-assembly we develop a generalization of the local determinism method of Soloveichik and Winfree.