Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing, China.
IEEE Trans Nanobioscience. 2011 Jun;10(2):94-8. doi: 10.1109/TNB.2011.2160996. Epub 2011 Jul 7.
The solution space exponential explosion caused by the enumeration of the candidate solutions maybe is the biggest obstacle in DNA computing. In the paper, a new unenumerative DNA computing model for graph vertex coloring problem is presented based on two techniques: 1) ordering the vertex sequence for a given graph in such a way that any two consecutive labeled vertices i and i+1 should be adjacent in the graph as much as possible; 2) reducing the number of encodings representing colors according to the construture of the given graph. A graph with 12 vertices without triangles is solved and its initial solution space includes only 283 DNA strands, which is 0.0532 of 3(12) (the worst complexity).
由于候选解决方案的枚举导致的解空间呈指数级增长，可能是 DNA 计算中最大的障碍。本文提出了一种新的基于图顶点着色问题的非枚举 DNA 计算模型，该模型基于两种技术：1）以尽可能使任何两个连续标记的顶点 i 和 i+1 在图中相邻的方式对给定图的顶点序列进行排序；2）根据给定图的结构减少表示颜色的编码数量。解决了一个没有三角形的 12 个顶点的图，其初始解空间仅包含 283 个 DNA 链，这是 3(12)的 0.0532（最坏复杂度）。
