Stochastic Analysis of Reversible Self-Assembly

摘要

The theoretical basis of computational self-assembly dates back to the idea of Wang tiling models in the early 1960s.(1) More recently, it has been recognized that self-assembly is a promising route to nano-scale computation and there have been many experimental demonstrations of self-assembling DNA tiles performing computation. Winfree(2) proposed abstract irreversible (only tile accretion is allowed) models for the self-assembly process that can perform universal computation. Realism, however, requires us to develop models and analysis for reversible tiling models, where tile dissociation is also allowed so that we can measure various thermodynamic properties. To date, however, the stochastic analysis of reversible tiling processes has only been done for one-dimensional assemblies and has not been extended to two or three dimensional assemblies. In this paper we discuss how we can extend prior work in one dimension by Adleman et al.(3) to higher dimensions. We describe how these self-assembly processes can be modeled as rapidly mixing Markov Chains. We characterize chemical equilibrium in the context of self-assembly processes and present a formulation for the equilibrium concentration of various assemblies. Since perfect equilibrium can only be reached in infinite time, we further derive the distribution of error around equilibrium. We present the first known direct derivation of the convergence rates of two and three-dimensional assemblies to equilibrium. Finally we observe that even when errors are allowed in the self-assembly model, the distribution over assemblies converge to uniform distribution with only small number of random association/dissociation events. We conclude with some thoughts on how to relax some of our model constraints.