DNA Tile Assembly Model for Bin Packing Problem

Research results have confirmed that some reasonable solution for NP-complete problem could be achieved using DNA self-assembly model, in which the ability of molecular computing to perform complicated mathematical operations could be get a full play. In this paper, the DNA self-assembly model for the bin packing problem is constructed. This model is composed of two units: grouping based on binary method and subtraction system. The great advantage of our schema is that it only needs a constant number of DNA tile types and in time linear with the size of the items to solve any bin packing problem. This work demonstrates further evidence for the ability of DNA tiles to solve other NP-complete problems.

I. Introduction

DNA self-assembly is one of the most significant application and an important method of DNA computation. Winfree et al. first proposed the idea of computation by self-assembled DNA tiles [1]. The first experimental demonstrations of computing using DNA tile assembly was in [2]. Because of its practical importance, DNA self-assembly has received increased theoretical attention over the last few years. Till now, computational systems based on self-assembly have been demonstrated in both one-dimensional arrangements called “string tiles” [1], [3] and two-dimensional (2D) lattices of DNA [4]. For 2D self-assembly, Winfree has proposed the tile assembly model and demonstrated that it is Turing-universal [4]. In particular, some of the recent works had focused on the assembling of squares. Brun proposed and studied some systems that compute the sums and products of two numbers using the tile assembly model [5], and then used it to solve some fundamental problems such as SubsetSum [6], satisfiability [7]. Inspired by Brun, Zhang et al. showed how the tile assembly process can be used for subtraction and division [8], and Cui et al. used the tile assembly model to solve 0–1 knapsack problem [9], maximum clique problem [10].