3D DNA Self-Assembly Model for Graph Vertex Coloring

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 Theta(n) The number of distinct tiles used in the model is Theta(k(2)), 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-assemblyChemistry, MultidisciplinaryNanoscience & NanotechnologyMaterials Science, MultidisciplinaryPhysics, AppliedPhysics, Condensed MatterSCI(E)EI3ARTICLE1246-253