Application of DNA self-assembly for maximum matching problem

DNA tile self-assembly have been demonstrated to be used to solve graph theory or combinatorial optimization problem because of its high-density storage and huge-scale parallel computing ability. In this paper, tile self-assembly have been shown to be used for solving the maximum matching problem by mainly constructing four sub-systems which are seed configuration system, nondeterministic guess system, verification system and output system. These systems can be used to probabilistically get the feasible solution of the problem. The model can successfully perform the maximum matching problem in polynomial time with distinct tile types, parallel and at very low cost. Copyright © 2016 American Scientific Publishers. All rights reserved.