Deterministic algorithm for the reordering problem using tile assembly

Algorithmic self-assembly, a generalization of crystal growth, has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computation. In theory, growth can be programmed by designing a set of molecular tiles with binding interactions that enforce assembly rules. There are many interesting applications of the reordering problem in Mathematics, as well as Computer Sciences. It is a useful primitive operation for computation and construction in the field of science and engineering. It is worth exploring more efficient approach to solve this problem. In this paper, we provide a description of a novel method for the reordering problem by use of the programmable tile assembly model. We propose the thought of block assembly model which takes full advantage of the huge parallelism inherent in the tile assembly. On the basis of the structural property, we delicately devise a rule to produce a long reporter strand which can connect all the inputs of the given problem with the final results. It is proved that this method can be extended to any reordering problem with arbitrary size in theory. The great advantage of our schema is that it only needs a constant number of tile types and in time linear with the size of the input problem to solve any reordering problem. ?2009 IEEE.EI