Abstract
DNA self-assembly technology has brought novel inspirations to the development of DNA computing. Diversified computational models based on DNA self-assembly have been used to solve various NP problems. In this paper, a 3D DNA self-assembly model is presented to solve the Graph Vertex Coloring problem. With the capacity of DNA molecules in massive parallel computation, the model can simulate a non-deterministic algorithm and solve the problem in linear time: Θ(n). The number of distinct tiles used in the model is Θ(k2), where k is the size of the color set. For the vertex 3-coloring problem, the model requires only 22 types of distinct tiles. Our work makes a significant attempt for exploring the computational power of 3D DNA self-assembly.