A “Nano-Dial” Molecular Computing Model Based on Circular DNA

A novel molecular computing model based on circular DNA was developed to solve a 3-coloring graph problem. This computing model uses circular DNA and works as to dial a number. The method of selecting true solutions is similar to dialing on a telephone. Moreover, the key methods in this model were circularization of single single-strand DNA (ssDNA) molecules and a backtracking deletion algorithm. In the course of computing, the structure of the DNA molecule was transformed into linear double-strand DNA (dsDNA), linear ssDNA, and circular ssDNA. For a 3-coloring graph problem with n vertices, the algorithm time complexity and the space complexity are both O(n2) at most. The computing achievement by this model indicates that circular DNA has extensive applications in molecular computing research.