Robust self-assembly of graphs

Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled one vertex at a time starting from a designated seed vertex. The weight of an edge specifies the magnitude of attraction (positive weight) or repulsion (negative weight) between adjacent vertices. It is feasible to add a vertex to the assembly if the total attraction minus repulsion of the already built neighbors exceeds a certain threshold, called the assembly temperature. This model naturally generalizes the extensively studied Tile Assembly Model. A natural question in graph self-assembly is to determine whether or not there exists a sequence of feasible vertex additions to realize the entire graph. However, even when it is feasible to realize the assembly, not much can be inferred about its likelihood of realization in practice due to the uncontrolled nature of the self-assembly process. Motivated by this, we introduce the robust self-assembly problem where the goal is to determine if every possible sequence of feasible vertex additions leads to the completion of the assembly. We show that the robust self-assembly problem is co-NP-complete even on planar graphs with two distinct edge weights. We then examine the tractability of the robust self-assembly problem on a natural subclass of planar graphs, namely grid graphs. We identify structural conditions that determine whether or not a grid graph can be robustly self-assembled, and give poly-time algorithms to determine this for several interesting cases of the problem. Finally, we also show that the problem of counting the number of feasible orderings that lead to the completion of an assembly is #P-complete.     

自组装DNA计算的研究进展及展望

近年来,许多研究者已经证明二维自组装模型有通用计算能力,同时证明了自组装DNA计算具有可扩展性。随着分子生物学技术的发展,自组装DNA计算有着广阔的应用前景,在纳米科学、优化计算、密码学、医学等众多科学领域中有突破性的创新与应用。较全面地介绍了自组装DNA计算的研究现状、原理、分子结构和数学模型,以及自组装DNA计算的复杂度和误差分析,并对自组装DNA计算待研究的问题和发展前景进行了分析和展望。     

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.     

嵌段共聚物受限自组装结构的计算机模拟和理论预测

本文简述高分子自组装的几种计算机理论模拟方法.重点叙述用模拟方法去模拟和预测嵌段共聚物受限诱导自组装结构的情况.总结它们在一维、二维以及三维受限条件下自组装的理论预测和模拟的研究成果,并指出了在受限条件下自组装的研究中亟待解决的问题.     

DNA自组装技术的研究进展及难点(英文)

近年来,DNA自组装成为DNA计算及纳米材料科学等领域研究的热点,它关系着DNA计算机的发展．DNA分子如何组装已成为许多学者关注的焦点．为此,文中主要围绕着DNA分子组装成的初级元件的类型：一条长的DNA单链、多条短寡核苷酸链和自组装单元,重点从自组装的初级元件形成的一维、二维及三维结构上讨论DNA自组装技术与方法．文中讨论了这些技术的原理及应用的研究进展,并且分析了DNA自组装应用于DNA计算的主要难点及解决方案．首先,编码的好坏决定着实验是否能实施;其次,DNA单链之间组装的角度及初级原件之间的连接是影响自组装体产量的关键因素;从具体的实验操作上看,每条DNA单链的浓度比例及退火温度则决定着自组装的成败．随着学科之间的高度交叉,DNA自组装将是材料学、信息学、生物学等领域的重要研究方向,也是推动DNA计算机发展的重要手段．     

On aggregation in multiset-based self-assembly of graphs

We continue the formal study of multiset-based self-assembly. The process of self-assembly of graphs, where iteratively new nodes are attached to a given graph, is guided by rules operating on nodes labelled by multisets. In this way, the multisets and rules model connection points (such as “sticky ends”) and complementarity/affinity between connection points, respectively. We identify three natural ways (individual, free, and collective) to attach (aggregate) new nodes to the graph, and study the generative power of the corresponding self-assembly systems. For example, it turns out that individual aggregation can be simulated by free or collective aggregation. However, we demonstrate that, for a fixed set of connection points, collective aggregation is rather restrictive. We also give a number of results that are independent of the way that aggregation is performed.     

A Framework for Augmented Reality using Non-Central Catadioptric Cameras

This paper proposes a strategy for a group of swarm robots to self-assemble into a single articulated(legged) structure in response to terrain difficulties during autonomous exploration. These articulated structures will have several articulated legs or backbones, so they are well suited to walk on difficult terrains like animals. There are three tasks in this strategy: exploration, self-assembly and locomotion. We propose a formation self-assembly method to improve self-assembly efficiency. At the beginning, a swarm of robots explore the environment using their sensors and decide whether to self-assemble and select a target configuration from a library to form some robotic structures to finish a task. Then, the swarm of robots will execute a self-assembling task to construct the corresponding configuration of an articulated robot. For the locomotion, with joint actuation from the connected robots, the articulated robot generates locomotive motions. Based on Sambot that are designed to unite swarm mobile and self-reconfigurable robots, we demonstrate the feasibility for a varying number of swarm robots to self-assemble into snake-like and multi-legged robotic structures. Then, the effectiveness and scalability of the strategy are discussed with two groups of experiments and it proves the formation self-assembly is more efficient in the end.     

Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-Assembly

Winfree’s pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly (Winfree and Bekbolatov in DNA Based Computers 9, LNCS, vol. 2943, pp. 126–144, [2004]), but the construction resulted in increase of the size of assembly. Reif et al. (Nanotechnol. Sci. Comput. 79–103, [2006]) contributed further in this area with compact error-resilient schemes that maintained the original size of the assemblies, but required certain restrictions on the Boolean functions to be used in the algorithmic self-assembly. It is a critical challenge to improve these compact error resilient schemes to incorporate arbitrary Boolean functions, and to determine how far these prior results can be extended under different degrees of restrictions on the Boolean functions. In this work we present a considerably more complete theory of compact error-resilient schemes for algorithmic self-assembly in two and three dimensions. In our error model, ε is defined to be the probability that there is a mismatch between the neighboring sides of two juxtaposed tiles and they still stay together in the equilibrium. This probability is independent of any other match or mismatch and hence we term this probabilistic model as the independent error model. In our model all the error analysis is performed under the assumption of kinetic equilibrium. First we consider two-dimensional algorithmic self-assembly. We present an error correction scheme for reduction of errors from ε to ε ² for arbitrary Boolean functions in two dimensional algorithmic self-assembly. Then we characterize the class of Boolean functions for which the error can be reduced from ε to ε ³, and present an error correction scheme that achieves this reduction. Then we prove ultimate limits on certain classes of compact error resilient schemes: in particular we show that they can not provide reduction of errors from ε to ε ⁴ is for any Boolean functions. Further, we develop the first provable compact error resilience schemes for three dimensional tiling self-assemblies. We also extend the work of Winfree on self-healing in two-dimensional self-assembly (Winfree in Nanotechnol. Sci. Comput. 55–78, [2006]) to obtain a self-healing tile set for three-dimensional self-assembly.     

分子自组装的应用与计算机模拟研究进展

分子自组装技术已经在纳米技术、膜技术和生命科学等领域有广泛的应用。计算机模拟又是研究分子自组装特性、超分子聚集体结构和特性的有效方法。本文综述了分子自组装技术的应用情况,从热力学和动力学角度对近年分子自组装特性计算机模拟的研究进展进行了评述,最后分析了存在的一些问题并对今后的发展前景进行了展望。     

Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational perspective, that is, from the perspective of mathematical problems whose study may give insight into the natural processes through which elementary objects self-assemble into more complex ones. One of the main problems of algorithmic self-assembly is the minimum tile set problem, which in the extended formulation we consider, here referred to as MTSP, asks for a collection of types of elementary objects (called tiles) to be found for the self-assembly of an object having a pre-established shape. Such a collection is to be as concise as possible, thus minimizing supply diversity, while satisfying a set of stringent constraints having to do with important properties of the self-assembly process from its tile types. We present a study of what, to the best of our knowledge, is the first practical approach to MTSP. Our study starts with the introduction of an evolutionary heuristic to tackle MTSP and includes selected results from extensive experimentation with the heuristic on the self-assembly of simple objects in two and three dimensions, including the possibility of tile rotation. The heuristic we introduce combines classic elements from the field of evolutionary computation with a problem-specific variant of Pareto dominance into a multi-objective approach to MTSP.     

Self-assembly strategies in a group of autonomous mobile robots

Robots are said to be capable of self-assembly when they can autonomously form physical connections with each other. By examining different ways in which a system can use self-assembly (i.e., different strategies), we demonstrate and quantify the performance costs and benefits of (i) acting as a physically larger self-assembled entity, (ii) letting the system choose when and if to self-assemble, (iii) coordinating the sensing and actuation of the connected robots so that they respond to the environment as a single collective entity. Our analysis is primarily based on real world experiments in a hill crossing task. The configuration of the hill is not known by the robots in advance—the hill can be present or absent, and can vary in steepness and orientation. In some configurations, the robots can overcome the hill more quickly by navigating individually, while other configurations require the robots to self-assemble to overcome the hill. We demonstrate the applicability of our self-assembly strategies to two other tasks—hole crossing and robot rescue—for which we present further proof-of-concept experiments with real robots.     

Self-assembly of shapes at constant scale using repulsive forces

Natural Computing - The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of shape construction, we consider an extended version of the...     

Convergence rates of Markov chains for some self-assembly and non-saturated Ising models

Algorithms based on Markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. For some self-assembly models, Markov chains can be used to predict both equilibrium and non-equilibrium dynamics. In fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. We give an overview of the theory of Markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. We illustrate this behavior for the non-saturated Ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. Unlike the standard Ising model, we also allow empty spaces that are not occupied by either type of tile. We prove that for a local Markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.     

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.     

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).     

Combining self-healing and proofreading in self-assembly

Molecular self-assembly is a promising approach to bottom-up fabrication of complex structures. A major impediment to the practical use of self-assembly to create complex structures is the high rate of error under existing experimental conditions. Recent theoretical work on algorithmic self-assembly has shown that under a realistic model of tile addition and detachment, error correcting tile sets are possible that can recover from the attachment of incorrect tiles during the assembly process. An orthogonal type of error correction was recently considered as well: whether damage to a completed structure can be repaired. It was shown that such self-healing tile sets are possible. However, these tile sets are not robust to the incorporation of incorrect tiles. It remained an open question whether it is possible to create tile sets that can simultaneously resist wholesale removal of tiles and the incorporation of incorrect ones. Here we present a method for converting a tile set producing a pattern on the quarter plane into a tile set that makes the same pattern (at a larger scale) but is able to withstand both of these types of errors.

Fabrication,simulations, and measurements of self-assembled millimeter-wave antennas for system-on-chip applications

A micro-electro-mechanical systems fabrication process has been developed to create self-assembled on-chip high efficiency antennas. The self-assembly creates out-of-plane antenna structures, which can have good radiation efficiency on low resistivity substrates. The structural material is SU-8 and the self-assembly curvatures are defined lithographically. The losses are reduced by having the antennas, transmission lines, and an isolating conducting ground plane placed on top of the supporting (and lossy) dielectric layer. The fabrication process includes deposition of a thick metal layer, which envelopes the antenna structure. This paper presents the fabrication process for a self-assembled monopole antenna, and numerical and physical experiments for the antenna pattern characteristics. The physical measurements show a realized gain (includes mismatch loss) of ?1.29 dBi at 59 GHz.     

Reducing Tile Complexity for the Self-assembly of Scaled Shapes Through Temperature Programming

This paper concerns the self-assembly of scaled-up versions of arbitrary finite shapes. We work in the multiple temperature model that was introduced by Aggarwal, Cheng, Goldwasser, Kao, and Schweller (Complexities for Generalized Models of Self-Assembly, SIAM J. Comput. 2005). The multiple temperature model is a natural generalization of Winfree’s abstract tile assembly model, where the temperature of a tile system is allowed to be shifted up and down as self-assembly proceeds. We first exhibit two constant-size tile sets in which scaled-up versions of arbitrary shapes self-assemble. Our first tile set has the property that each scaled shape self-assembles via an asymptotically “Kolmogorov-optimum” temperature sequence but the scaling factor grows with the size of the shape being assembled. In contrast, our second tile set assembles each scaled shape via a temperature sequence whose length is proportional to the number of points in the shape but the scaling factor is a constant independent of the shape being assembled. We then show that there is no constant-size tile set that can uniquely assemble an arbitrary (non-scaled, connected) shape in the multiple temperature model, i.e., the scaling is necessary for self-assembly. This answers an open question of Kao and Schweller (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 571–580, 2006), who asked whether such a tile set exists.     

Programming and evolving physical self-assembling systems in three dimensions

Being able to engineer a set of components and their corresponding environmental conditions such that target entities emerge as the result of self-assembly remains an elusive goal. In particular, understanding how to exploit physical properties to create self-assembling systems in three dimensions (in terms of component movement) with symmetric and asymmetric features is extremely challenging. Furthermore, primarily top-down design methodologies have been used to create physical self-assembling systems. As the sophistication of these systems increases, it will be more challenging to use top-down design due to self-assembly being an algorithmically NP-complete problem. In this work, we first present a nature-inspired approach to demonstrate how physically encoded information can be used to program and direct the self-assembly process in three dimensions. Second, we extend our nature-inspired approach by incorporating evolutionary computing, to couple bottom-up construction (self-assembly) with bottom-up design (evolution). To demonstrate our design approach, we present eight proof-of-concept experiments where virtual component sets either defined (programmed) or generated (evolved) during the design process have their specifications translated and fabricated using rapid prototyping. The resulting mechanical components are placed in a jar of fluid on an orbital shaker, their environment. The energy and physical properties of the environment, along with the physical properties of the components (including complementary shapes and magnetic-bit patterns, created using permanent magnets to attract and repel components) are used to engineer the self-assembly process to create emergent target structures with three-dimensional symmetric and asymmetric features. The successful results demonstrate how physically encoded information can be used with programming and evolving physical self-assembling systems in three dimensions.     

Self-assembling DNA graphs

It has been shown theoretically that three dimensional graph structure and DNA self-assembly can be used to solve numerous computational problems such as 3-SAT and 3-colorability in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. This paper presents experimental results of DNA self-assembly of non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections.