目前DNA 计算机研究中遇到的最大瓶颈是解空间指数爆炸问题，即随着问题规模的增大，所需要作为信息处理'数据'的DNA分子呈指数级增大。本文提出了一种新颖的图顶点着色DNA计算模型，该模型正是围绕着如何克服解空间指数爆炸问题以及如何提高运行速度而设计的。其主要贡献有：①通过如下三种方法来克服解空间指数爆炸问题：顶点颜色集的确定方法；子图分解方法以及子图中的顶点优化排序方法；②设计了一种并行型聚合酶链反应（PCR）操作技术，应用这种技术一次可以对图中多条边来删除非解，使得生物操作次数大大减少，极大地提高了运行速度。本文以一个3-着色的61 个顶点的图为例，实验表明，99% 的非可行解在构建初始解空间时就被删除，并利用DNA 自组装和并行PCR 方法，通过识别、拼接以及组装等技术得到解。由于该模型对任意61 个顶点的图是同样的操作方法，这就意味着，该模型的搜索能力可以达到O(359)。

The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and improve the processing speed, we propose a DNA computing model to solve the graph vertex coloring problem. The main points of the model are as follows:①The exponential explosion problem is solved by dividing subgraphs, reducing the vertex colors without losing the solutions, and ordering the vertices in subgraphs; and②the bio-operation times are reduced considerably by a designed parallel polymerase chain reaction (PCR) technology that dramatically improves the processing speed. In this article, a 3-colorable graph with 61 vertices is used to illustrate the capability of the DNA computing model. The experiment showed that not only are all the solutions of the graph found, but also more than 99% of false solutions are deleted when the initial solution space is constructed. The powerful computational capability of the model was based on specific reactions among the large number of nanoscale oligonucleotide strands. All these tiny strands are operated by DNA self-assembly and parallel PCR. After thousands of accurate PCR operations, the solutions were found by recognizing, splicing, and assembling. We also prove that the searching capability of this model is up to O(359). By means of an exhaustive search, it would take more than 896 000 years for an electronic computer (5 1014 s1) to achieve this enormous task. This searching capability is the largest among both the electronic and non-electronic computers that have been developed since the DNA computing model was proposed by Adleman's research group in 2002 (with a searching capability of O(220)).