3D DNA self-assembly formaximum weighted independent set problem
HongWang1, Zicheng Wang2, Yanfeng Wang2, Guangzhao Cui2
COMPUTER MODELLING & NEW TECHNOLOGIES 2014 18(12A) 79-85
1School of Architectural and Environmental Engineering, Zhengzhou University of Light Industry, Zhengzhou, 450002, China
2School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou, 450002, China
The problem of finding a maximum weighted independent set (MWIS) is a classical combinatorial optimization problem of graph theory, which has been proved to be NP-complete (NPC). A 2-D DNA tile self-assembly model for solving the problem has been proposed previously, but it still has many deficiencies. In this paper, we will propose a 3-D DNA tile self-assembly model based on 2-D DNA tile self-assembly model to solve the problem. This model includes two parts: the non-deterministic search system and the addition system. Firstly, we can find all the independent sets via the non-deterministic search system, and then get the total weight value of each independent set according to the addition system, and by comparison, the maximum weighted independent set will be found finally. Result shows that the operational time is linear, and the number of the tiles required in the process is constant