DNA Self-Assembly for Graph Vertex 3-Coloring Problem

This paper presents a method of DNA self-assembly for solving the graph vertex 3-coloring problem. We encode all vertices of a graph in DNA tiles as the inputs, and then assign colors to vertices based on the rule that two adjacent vertices can not be assigned the same color in the process of DNA self-assembly. By creating huge numbers of copies of the participating DNA tiles, the algorithm will run in parallel on all possible vertex 3-coloring situations, finally exclude the aborted coloring situations and obtain the successful vertex coloring scheme(s). The potential computations by DNA self-assembly for the vertex 3-coloring problem is promising given the operational time complexity of O(n). This work shows further evidence for the ability of DNA self-assembly to solve other NP-complete problems.