Efficient 3-SAT algorithms in the tile assembly model

Self-assembly is a powerful process found in nature that guides simple objects assembling, on their own, into complex structures. Self-assembly is of interest to computer scientists because self-assembling systems can compute functions, assemble shapes, and guide distributed robotics systems. The tile assembly model is a formal mathematical model of self-assembly that allows the study of time and space complexities of self-assembling systems that lie at the heart of several molecular computer implementations and distributed computational software systems. These implementations and systems require efficient tile systems with small tilesets and fast execution times. The state of the art, however, requires vastly complex tile systems with large tilesets to implement fast algorithms. In this paper, I present ${\mathbb{S}}_{FS},$ a tile system that decides 3-SAT by creating $O^{\star}(1.8393^n)$ nondeterministic assemblies in parallel, improving on the previous best known solution that requires $\Uptheta(2^n)$ such assemblies. This solution directly improves the feasibility of building molecular 3-SAT solvers and efficiency of distributed software. I formally prove the correctness of the system, the number of required parallel assemblies, that the size of the system??s tileset is $147 = \Uptheta(1),$ and that the assembly time is nondeterministic linear in the size of the input.     

Self-Assembling Rulers for Approximating Generalized Sierpinski Carpets

Discrete self-similar fractals have been used as test cases for self-assembly, both in the laboratory and in mathematical models, ever since Winfree exhibited a tile assembly system in which the Sierpinski triangle self-assembles. For strict self-assembly, where tiles are not allowed to be placed outside the target structure, it is an open question whether any self-similar fractal can self-assemble. This has motivated the development of techniques to approximate fractals with strict self-assembly. Ideally, such an approximation would produce a structure with the same fractal dimension as the intended fractal, but with specially labeled tiles at positions corresponding to points in the fractal. We show that the Sierpinski carpet, along with an infinite class of related fractals, can approximately self-assemble in this manner. Our construction takes a set of parameters specifying a target fractal and creates a tile assembly system in which the fractal approximately self-assembles. This construction introduces rulers and readers to control the self-assembly of a fractal structure without distorting it. To verify the fractal dimension of the resulting assemblies, we prove a result on the dimension of sets embedded into discrete fractals. We also give a conjecture on the limitations of approximating self-similar fractals.     

Producibility in hierarchical self-assembly

Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly α is producible. The algorithm can be optimized to use \(O(|\alpha | \log ^2 |\alpha |)\) time. Cannon et al. (STACS 2013: proceedings of the thirtieth international symposium on theoretical aspects of computer science. pp 172–184, 2013) showed that the problem of deciding if an assembly α is the unique producible terminal assembly of a tile system \({\mathcal {T}}\) can be solved in \(O(|\alpha |^2 |{\mathcal {T}}| + |\alpha | |{\mathcal {T}}|^2)\) time for the special case of noncooperative “temperature 1” systems. It is shown that this can be improved to \(O(|\alpha | |{\mathcal {T}}| \log |{\mathcal {T}}|)\) time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently—i.e., if the positions that they share have the same tile type in each assembly—then their union is also producible.     

Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models

Efficient tile sets for self assembling rectilinear shapes is of critical importance in algorithmic self assembly. A lower bound on the tile complexity of any deterministic self assembly system for an n?×?n square is $\Upomega(\frac{\log(n)}{\log(\log(n))})$ (inferred from the Kolmogrov complexity). Deterministic self assembly systems with an optimal tile complexity have been designed for squares and related shapes in the past. However designing $\Uptheta(\frac{\log(n)}{\log(\log(n))})$ unique tiles specific to a shape is still an intensive task in the laboratory. On the other hand copies of a tile can be made rapidly using PCR (polymerase chain reaction) experiments. This led to the study of self assembly on tile concentration programming models. We present two major results in this paper on the concentration programming model. First we show how to self assemble rectangles with a fixed aspect ratio (??:??), with high probability, using $\Uptheta(\alpha+\beta)$ tiles. This result is much stronger than the existing results by Kao et?al. (Randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) and Doty (Randomized self-assembly for exact shapes. In: proceedings of the 50th annual IEEE symposium on foundations of computer science (FOCS), IEEE, Atlanta. pp 85?C94, 2009)??which can only self assembly squares and rely on tiles which perform binary arithmetic. On the other hand, our result is based on a technique called staircase sampling. This technique eliminates the need for sub-tiles which perform binary arithmetic, reduces the constant in the asymptotic bound, and eliminates the need for approximate frames (Kao et?al. Randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) . Our second result applies staircase sampling on the equimolar concentration programming model (The tile complexity of linear assemblies. In: proceedings of the 36th international colloquium automata, languages and programming: Part I on ICALP ??09, Springer-Verlag, pp 235?C253, 2009), to self assemble rectangles (of fixed aspect ratio) with high probability. The tile complexity of our algorithm is $\Uptheta(\log(n))$ and is optimal on the probabilistic tile assembly model (PTAM)??n being an upper bound on the dimensions of a rectangle.     

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.     

Optimal staged self-assembly of linear assemblies

Natural Computing - We analyze the complexity of building linear assemblies, sets of linear assemblies, and $${\mathcal{O}}(1)$$ -scale general shapes in the staged tile assembly model. For systems...     

Step-wise tile assembly with a constant number of tile types

In this paper, we study the step-wise tile assembly model introduced by Reif (in: Based computers III, vol 48 of DIMACS, 1999) in which shape is assembled in multiple steps. In each step the partially built structure is exposed to a new set of tiles. We show that an N?×?N square can be assembled in N steps using a constant number of tile types. In general, we show that a constant number of tile types (24) is sufficient to assemble a large class of shapes in n steps, where n is the number of tiles of the shape. This class includes all shapes obtained from any shape by scaling by a factor of 2, in which case only 14 tile types suffices. For general shapes, we show that the tile complexity of this model is related to the monotone connected node search number of a spanning tree of the shape assuming the number of steps is n.     

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

Fast arithmetic in algorithmic self-assembly

In this paper we consider the time complexity of adding two n-bit numbers together within the tile self-assembly model. The (abstract) tile assembly model is a mathematical model of self-assembly in which system components are square tiles with different glue types assigned to tile edges. Assembly is driven by the attachment of singleton tiles to a growing seed assembly when the net force of glue attraction for a tile exceeds some fixed threshold. Within this frame work, we examine the time complexity of computing the sum of two n-bit numbers, where the input numbers are encoded in an initial seed assembly, and the output sum is encoded in the final, terminal assembly of the system. We show that this problem, along with multiplication, has a worst case lower bound of \(\varOmega ( \sqrt{n} )\) in 2D assembly, and \(\varOmega (\root 3 \of {n})\) in 3D assembly. We further design algorithms for both 2D and 3D that meet this bound with worst case run times of \(O(\sqrt{n})\) and \(O(\root 3 \of {n})\) respectively, which beats the previous best known upper bound of O(n). Finally, we consider average case complexity of addition over uniformly distributed n-bit strings and show how we can achieve \(O(\log n)\) average case time with a simultaneous \(O(\sqrt{n})\) worst case run time in 2D. As additional evidence for the speed of our algorithms, we implement our algorithms, along with the simpler O(n) time algorithm, into a probabilistic run-time simulator and compare the timing results.     

广义卡尔曼-布西滤波算法识别系统参数

根据结构力学与卡尔曼滤波相模拟的理论,构造了一种新的用于连续系统参数识别的广义卡尔曼—布西滤波计算格式．该算法运用了结构力学中的串联子结构拼装方法,在每一步子结构拼装的同时嵌入对系统状态和参数的估计以实现系统参数的识别,可以离线计算的数据都通过精细积分算法预先获得。     

Efficient algorithms for self assembling non-rectangular nano structures

Nano fabrication with biomolecular/DNA self assembly is a promising area of research. Building nano structures with self assembly is both efficient and inexpensive. Soloveichik and Winfree (SIAM J Comput 36(6):1544–1569, 2007) formalized a two dimensional (2D) tile assembly model based on Wang’s tiling technique. Algorithms with an optimal tile complexity of (\Uptheta(\fraclog(N)log(log(N))))\left(\Uptheta\left(\frac{\log(N)}{\log(\log(N))}\right)\right) were proposed earlier to uniquely self assemble an N × N square (with a temperature of α = 2) on this model. However efficient constructions to assemble arbitrary shapes are not known and have remained open. In this paper we present self assembling algorithms to assemble a triangle of base 2N − 1 (units) and height N with a tile complexity of \Uptheta(log(N)).\Uptheta(\log(N)). We also describe how this framework can be used to construct other shapes such as rhombus, hexagon etc.     

Polyominoes simulating arbitrary-neighborhood zippers and tilings

This paper provides a bridge between the classical tiling theory and the complex-neighborhood self-assembling situations that exist in practice.The neighborhood of a position in the plane is the set of coordinates which are considered adjacent to it. This includes classical neighborhoods of size four, as well as arbitrarily complex neighborhoods. A generalized tile system consists of a set of tiles, a neighborhood, and a relation which dictates which are the “admissible” neighboring tiles of a given tile. Thus, in correctly formed assemblies, tiles are assigned positions of the plane in accordance with this relation.We prove that any validly tiled path defined in a given but arbitrary neighborhood (a zipper) can be simulated by a simple “ribbon” of microtiles. A ribbon is a special kind of polyomino, consisting of a non-self-crossing sequence of tiles on the plane, in which successive tiles stick along their adjacent edge.Finally, we extend this construction to the case of traditional tilings, proving that we can simulate arbitrary-neighborhood tilings by simple-neighborhood tilings, while preserving some of their essential properties.     

One-dimensional staged self-assembly

We introduce the problem of staged self-assembly of one-dimensional nanostructures, which becomes interesting when the elements are labeled (e.g., representing functional units that must be placed at specific locations). In a restricted model in which each operation has a single terminal assembly, we prove that assembling a given string of labels with the fewest steps is equivalent, up to constant factors, to compressing the string to be uniquely derived from the smallest possible context-free grammar (a well-studied O(log n)-approximable problem) and that the problem is NP-hard. Without this restriction, we show that the optimal assembly can be substantially smaller than the optimal context-free grammar, by a factor of $\Omega(\sqrt{n/\log n})$ even for binary strings of length n. Fortunately, we can bound this separation in model power by a quadratic function in the number of distinct glues or tiles allowed in the assembly, which is typically small in practice.     

The design and development of an automated DFA system

This paper presents the design and development of an automated system to assist with Design for Assembly (DFA) analysis. The system is designed to accept information on alternative assemblies using DFA metaphors. Statistics are calculated for these assemblies so as to evaluate their assemblability. The alternative assemblies and improvements in any assembly design are evaluated using these statistics.

A binary tree data structure is used in the DFA system to represent the design data. This structure is implemented by a linked method with three links in each tree node. This allows any arbitrary tree to be represented efficiently, and it also allows for unpredictable tree growth and easy tree manipulation. The user interface of the DFA system is managed by the “User Interface Management System”, that achieves direct and fast control of the screen by directly accessing the video memory.     

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.     

Nondeterministic polynomial time factoring in the tile assembly model

Formalized study of self-assembly has led to the definition of the tile assembly model, Previously I presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Here, I present tile assembly model systems that factor numbers nondeterministically using Θ(1)$\Theta \left(1\right)$ distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that the probability can be made arbitrarily close to 1.     

An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly

Scheduling of aircraft assembling activities is proven as a non-deterministic polynomial-time hard problem; which is also known as a typical resource-constrained project scheduling problem (RCPSP). Not saying the scheduling of the complex assemblies of an aircraft, even for a simple product requiring a limited number of assembling operations, it is difficult or even infeasible to obtain the best solution for its RCPSP. To obtain a high quality solution in a short time frame, resource constraints are treated as the objective function of an RCPSP, and an adaptive genetic algorithm (GA) is proposed to solve demand-driven scheduling problems of aircraft assembly. In contrast to other GA-based heuristic algorithms, the proposed algorithm is innovative in sense that: (1) it executes a procedure with two crossovers and three mutations; (2) its fitness function is demand-driven. In the formulation of RCPSP for aircraft assembly, the optimizing criteria are the utilizations of working time, space, and operators. To validate the effectiveness of the proposed algorithm, two encoding approaches have been tested with the real data of demand.