1. 引言
1961年，Feynman提出了分子计算的构想[
1]，33年后，Adleman实现了Feynman的构想，在1994年提出了以DNA分子作为“数据”，以生物酶或生物操作为“工具”来进行信息处理的DNA计算模型[
2]。从1994年至今，DNA计算模型无论在理论、实验还是应用等方面，都取得了很大的进展。十多年的研究表明，目前阻碍DNA计算机发展的最大瓶颈是：在求解大规模的优化计算问题上，特别是一些困难的NP（非确定性多项式）-完全问题上，随着问题规模的增大，所需要的DNA量呈指数增长。
1.1. 相关研究综述
1994年，Adleman[
2]创立了以DNA分子为“数据”，以生物酶和生物操作为信息处理“工具”的DNA计算模型。随后，许多学者在此领域内作出了杰出的工作，如Lipton[
3]建立了SAT问题的DNA计算模型，Ouyang等[
4]建立了求解图的最大团问题的DNA计算模型，Sakamoto等[
5]建立的求解可满足性（SAT）问题的发卡DNA计算模型，Rothemund等[
6]建立了图灵DNA计算机模型。除此之外，DNA分子建立用于基因表达逻辑控制的“自律式分子计算机”[7,8]，1998年Winfree等[
9]提出了自组装DNA计算模型，2002年Braich等[
10]建立了具有20个变量3-SAT问题的DNA计算机模型，其搜索次数超过104万次。这是迄今为止用非电子工具所解决的规模最大的一个问题。
图的顶点着色问题是指对图中的每个顶点分配一种颜色，使得相邻的顶点着不同的颜色。这是一个典型的NP-完全问题，由于该问题在许多应用领域如排课表问题[
11]、寄存器分配问题[
12,
13]等中都广泛存在，随着图的规模的扩大，计算量将会呈指数性增加，如何找到一个高效的算法就成为了解决有关问题的关键和突破点。1974年，Johnson[
14]展开了对图染色问题的近似算法的分析工作。之后，Blum[
15]提出用O(n
3/8 log
8/5n)种颜色可以对具有n个顶点的3-可着色图进行染色。Karger等[
16]提出了一种随机多项式时间算法，利用该算法可以对3-可着色图用min{O(Δ
1/3log
1/2 Δlogn), O(n
1/4 log
1/2n)}种颜色进行顶点染色。Schiermeyer[
17]给出了一种复杂算法，利用该算法，可以在小于O(1.415
n )的时间内，给出3-着色方案。之后，Beigel和Eppstein[
18]改进了算法，建立了一种快速算法，使得可以在O(1.3278
n )时间内求解图的3-着色问题。
基于DNA计算模型的图顶点着色方面的研究主要有如下工作：1999年，Jonoska等[
19]提出将3D的DNA分子用于DNA计算，在理论上证明，3D的DNA分子可以形成一个图当且仅当这个问题的解存在。在上述工作基础上，Jonoska和Sa-ardyen等利用生化操作构造了3-臂和4-臂的DNA分子，并将其用于求解顶点3-着色问题[
20,
21]。Liu等[
22]和Gao等[
23]先后分别提出了利用酶切操作技术来删除非解的用于求解图顶点着色的DNA计算模型。Xu等[
24]建立了一种利用磁珠分离技术来删除非解的图顶点着色DNA计算模型，并通过实验验证了该模型。
1.2. 本文的工作
围绕着如何克服解空间指数爆炸问题与如何提高计算过程中的运算速度，本文建立了一种新颖的图顶点着色DNA计算模型，称为并行型图顶点着色DNA计算模型。该模型适用于求解任意着色的图顶点着色问题。文中以展开分析研究，这些方法与技术自然可以推广到任意情形。
对于规模较大的图而言，本模型的基本思想是：首先将一个给定的图分解成若干个子图，目的是不仅使得生物操作易于实现，而且将尽可能多的非解较早地给予删除，这样可为后面的生化操作方便；然后对较小的每个子图求解，该求解过程涉及诸如顶点排序、桥点（即在子图中一对度数为最大的相邻顶点）的确定、每个顶点颜色集的确定、DNA序列编码、探针的确定、初始解空间的建立、非解的删除等（具体见3.3~3.7节）；最后，合并各个子图并逐步删除非解，直到合成为原始图（详见3.8节）。
本文的主要贡献有：①通过如下三种方法来克服解空间指数爆炸问题：子图分解方法、减少顶点颜色集的方法以及通过子图顶点排序方法来促使构造尽可能多的探针方法；②设计了一种并行型聚合酶链反应（PCR）操作技术，应用这种技术一次可以对图中多条边进行非解删除，使得生物操作次数大大减少，极大地提高了运行速度，并给出了提高运行速度相应的数学模型。
利用该计算模型，我们对如图1所示的61个顶点的图进行了实验计算，得到了满足该图正常3-着色的所有8个解。可以证明当v1 和vn 给定之后，本模型的计算能力可以达到O(359 )。
1.3. 本文的大纲
本文安排如下：第二部分给出文章所需要的一些概念及基础知识，诸如图的概念与记号、图的着色问题、PCR技术等；第三部分给出本文的计算模型，包括算法步骤及其每步操作方法与技术；第四部分以一个61个顶点的图的3-着色为例，给出具体的生化实验方法步骤；第五部分是本章的理论分析部分，重点分析了模型中克服解空间指数爆炸问题的算法的复杂性问题；最后一部分是文章的结论部分，对本文进行了总结，并指出进一步的研究方向。
图1. 一个3-着色的61个顶点的图G。
2. 定义和符号
2.1. 图着色问题
本文所言之图皆指有限、无自环、无圈的无向简单图，通常用G表示图。我们用V(G)、E(G)分别表示图G的顶点集和边集。文中用ΓG (v)表示图G中顶点v的邻域，即在图G中与顶点v相邻的顶点构成的子集合。定义dG (v)，即顶点v在图G的度数。这些符号在不致混淆的情况下，分别简化为V, E, dG 和ΓG 。若用V = {v1 ，v2 ，…，vn }表示图G的顶点集合，则用di = d(vi )表示顶点v i 的度数，其中i = 1,2,…,n。图G中一条链是由顶点和边交替形成的序列，用W表示。链满足从一个顶点从发，到另一个顶点结束，且连续的顶点都是相邻的。W可以表述成：
式中，k≥0，并且对每个i = 1,2,…,k–1，vi 和vi+1 是相邻的。链中边的数量即为链长。没有重复顶点的链构成路。
一个图G的着色是指对G中的每个顶点分配一种颜色，使得相邻的顶点着不同的颜色。换言之，是指对图G中的顶点集V(G)的剖分：
V(G) = V1 ∪V2 ∪…Vk ，Vi ≠ϕ(空集)，Vi ∩Vj ≠ϕ，i =1,2,…,k
满足图G正常着色的最小的颜色数称为色数，记为χ(G) 。图G的一个k-正常顶点着色，简称为图的k-顶点着色，是指用k [k ≥ c(G)]种颜色对图G进行着色。通常用C
k (G)表示图G的全体k着色构成的集合。由于本文仅考虑图的3-着色问题，故我们总是假定颜色集为C
3 (G) = {r, b,y}，其中，r表示红色，b表示蓝色，y表示黄色。所以，求解图的3-着色问题可以认为是寻找从图的顶点集V(G)到颜色集{r,b,y}的一种映射：f：V(G)→{r,b,y}，使得对于∀uv∈E(G)，f(u) ≠ f(v)。图的3-着色问题是一个NP-完全问题[
25]。文中的相关定义和符号参见文献[
26]。
定 义2.1 G是 一 个 简 单 图， 顶 点 集 合V(G) ={v1 ,v2 ,…,vn }。设vi1 vi2 …vin 是V(G)中顶点的排序，其中vij∈ V(G), j = 1,2,…,n，且若j ≠ l 则vij ≠ vil 。定义vi1 vi2 …vin 中的边数为Nedge (vi1 vi2 …vin )，满足：
2.2. PCR 技术
PCR法是一种可以快速并准确地大量复制DNA片段的技术。PCR的反应包括3个过程：变性、退火和延伸。当PCR产物的长度一定（相同）时，利用引物对序列作为目的序列，就可以得到首尾目的序列确定的所有的DNA片段，而中间未知的序列也将全部被扩增出来。PCR反应完成后，目标片段可以被大量地扩增出来，其数量可用公式y = (1 + x) n 计算。其中，y为DNA扩增倍数，x为扩增效率，n为循环数。
3. 模型及算法分析
本节将对1.2节中给出的计算模型的基本机理以及相关算法分析等给出较为详细的讨论。
3.1. 算法模型
在这个算法模型中，通过有限次的PCR操作，逐步删除不满足顶点着色的非解，扩增保留代表解的DNA分子。具体的算法流程图如图2所示。
图2. 模型的算法流程图。
3.2. 子图划分及桥点的确定
本模型计算时首先进行子图划分。子图划分的原因主要有如下两条：第一是易于生物操作实验：第二是为了较早地删除非解。这里G
j , V(G
j )
V(G), E(G
j )
E(G), j = 1,2,…,m–1用来代表一级子图。子图划分方法步骤如下。
步骤1 ：确定子图的大小。一般划分的导出子图的顶点数以15~20为宜，原因是易于生物操作，并要求每个子图的规模基本接近，我们把这样划分的子图称为一级子图。划分前需要分析整体图，要求：每个子图的边数尽可能得多，因为边数越多，在一级子图处理中就可以尽可能多地删除非解。由于在一级子图中删除非解生化操作方便，且在一级子图中删除的非解越多，后面合成的二级子图中的非解自然越少，越容易进行相应的生化操作。例如，对于如图3中所示的图给出了两种不同的划分，一种是：G′1 ，以V′1 = {1,2,3,4,5,6,7,16,17,18,19,20,21,22}为顶点子集，和G′2 ，以V′2 ={8,9,10,11,12,13,14,15,23,24,25,26,27,28,29,30}为顶点子集；另外一种划分是：G′3 ，以V′3= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}为顶点子集，和G′4 ，以V′4 ={16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}为顶点子集。显然，后一种划分比前一种划分好。
步骤2：确定第一个子图，并确定该子图的两个桥点u1 和u2 。这两个桥点必须相邻，且在该子图中度数之和最大；若满足该条件的顶点对不止一对，则选择以此两点为起点与终点的顶点排序后边数最多的那一对，即满足Nedge (u1 = vi1 vi2 …vin = u2 )最大（详见3.3节）；若满足上述三个条件的不止一对，则选择其中之一即可。
步骤3：确定第二个子图G2 ，该子图包含u2 。在子图G2 中找一个新的桥点u3 ，寻找的方法是：与u2 相邻的且在G2 中度数最大的。选择条件同步骤2。
步骤4：重复步骤3，直到完成最后一个子图的划分。
值得注意的是，第一，最后一个子图的顶点数目一般与前面子图的顶点数不同；第二，最后一个子图Gm的桥点有可能是前一个子图的一个桥点u1 与第一个子图的桥点um–1 构成。
桥点是本模型中的关键顶点，这是因为是通过桥点利用PCR技术很容易将各种子图之间合并起来。我们在子图桥点的确定时要求：在一个子图中两个桥点的度序列之和尽可能得大。这是因为，两个顶点度序列之和越大，即与这两顶点相邻的顶点越多，因此，相应顶点的颜色集合中颜色数必然减少越多，从而使得初始解空间变得越小。但对于所有顶点度数均相等的情况，我们所选择的桥点应遵循3.3节中关于子图顶点排序与每个顶点颜色集的确定。图4给出了图1中所示图G被划分的4个子图，其中顶点1,16,31,46,61是5个桥点。
3.3. 子图顶点排序与子图中每个顶点颜色集的确定
完成子图划分后，每个子图的桥点也随之确定。本小节所言的子图顶点排序就是求解出该子图以两个桥点为起点和终点的一种顶点排序，使其该排序中相邻顶点之间的边数（见定义2.1）尽可能得多。以子图G1 为例，若子图G1 的顶点集为V(G1 ) = {v1 ,v2 ,…,vt }，令v1 、vt是它的两个桥点，不失一般性，设排序的顶点序列为v1= vi1 vi2 vi3 …vit = vt ，需要满足：
为了给出下面顶点排序算法，我们在此先引入根点路集的概念。设v是图G的一个顶点。我们把以顶点v为起点的G中所有路径构成的路径集称为v-根点路径集，或简称为v-路径集，并记作P(v)。求一个顶点的路径集是不困难的，如首先取v的邻域Γ(v)，接着再对Γ(v)中每个顶点求邻域，记作Γ2(v)，Γ2(v)中不含元素v，如此下去，得到诸如Γ3(v)、Γ4(v)等，将在|V(G)|–1步之内终止，这种方法实际上是所谓的剪枝算法，是一种NP-算法，但文中所确定的图的子图的顶点数在20之内，故易于实现。
设G1 一个划分子图。v1 和vt 是它的两个桥点，则子图G1 顶点排序的算法步骤如下。
步骤1：求出两个桥点v1 和vt 的根点路径集P(v1 )和P(vt )，若在P(v1 )中含有子图G1 的Hamilton路，则选择该路径，否则，转向步骤2。
步骤2：若P(v1 )∪P(vt ) = V(G1 )，则从P(v1 )与P(vt )中分别选择出满足下式的两条路径P1 = vi1vi2vi3…vir ，Pt =visvisvis+1 …vt ；max|E(P1 )|+|E(Pt )|；P1 ∈P(v1 )，Pt ∈P(v2 )，V(P1 )∩V(Pt ) = ϕ。
步骤3：若V′ = V(G1 ) – P(v1 )∪P(vt ) ≠ ϕ。则从导出子图G[V′]中找出最长的路径，记作P′ = u1 u2 …um 。若V′′= V(G1 ) – V(P1 ) – V(Pt ) – V′ = ϕ，则子图G1 的顶点排序为：vi1vi2vi3…vir u1u2 …um vis vi(s+1) …vt 。若V′′ = V(G1 ) – V(P1 )– V(Pt ) – V′ = {ui1ui2…u iq }≠ϕ，则子图G1 的顶点排序为：v1vi2vi3…viru1 u2 …umui1ui2…uiqvisvi(s+1) …vt 。
对于图3中所示的子图G′3 ，它的两个桥点为1与13，我们在桥点1的根点路径集中找到路径1-10-11-2；桥点13的根点路径集中找到与之相匹配的路径13-14-7-8-15-3-9-4，在剩余的顶点中得到5-6,12，因此，顶点排序1,10,11,2,5,6,12,4,9,3,15,8,7,14,13（图5）。
图3. 一个一级子图划分的例子。（a）图G；（b）子图G′1 ；（c）子图G′2 ；（d）子图G′3 ；（e）子图G′4 。
在图4中第一个子图中顶点中顶点的排序是：1,2,…,16，这种排序是最好的，每对相邻的顶点i和i+1均有边相邻，i = 1, 2, …, 15。但若将它们的次序排成1,3, 5, 7, 9, 11, 13, 15, 2, 4, 6, 8, 10, 12, 14 ,1，则只有5条边：{5, 7}，{9,11}，{13,15}，{15, 2}，{6, 8}。
图4. 图1中图G的一级子图划分的4个子图。（a）子图G1 ；（b）子图G2 ；（c）子图G3 ；（d）子图G4 。
图5. 图3中子图G′ 3 的一种顶点排序及对应的11条边的集合。
步骤4：顶点重新排序。当子图的顶点排序按着步骤1的方法确定之后， 然后对图的顶点进行重新标定。假定标定前的子图的顶点排序为v1v2 …vt ，顶点重新排列后的序列为vσ(1) vσ(2) …vσ(t) ，显然，此排序就是顶点下标通过了下列置换而获得：
如对图2中子图G′3 的一种顶点排序（见图5）后，顶点重新排序的映射为
不失一般性，我们顶点排序后的子图顶点进行重新标定，标定的原则是：令顶点σ(i)标定为i，其中i = 1, 2,…, t。
我们在本文中的颜色数取k = 3，并且颜色集为C(3)= {red, yellow, blue}={r, y, b}，用ri 、yi 、bi 分别表示图中的顶点v i 着红色、黄色和蓝色。这种确定颜色集合的方法可以推广到颜色数k > 3的情况。
由于每个子图的首尾顶点（桥点）相邻，不失一般性，对于第一个子图G1 ，它的两个桥点分别是v1 和vt 。令顶点v1 着红色，记作r1 ，顶点vt 着蓝色，记作bt （注：顶点vt 也可以着黄色，我们在此先不予考虑，按照蓝色的情况下计算出所有解后，只需要对颜色集做一个颜色置换即可。即在红色不变的情况下，将黄色与蓝色互换即可得到另外一种着色，对于其他的子图同样，今后不再说明）。除顶点vt 外，顶点v1 的领域Γ(v1 )中的每个顶点着蓝色或黄色两种；同理，除顶点v1 外，顶点vt 的领域Γ(vt )中的顶点着红色或黄色两种。对于图1中所示的4个子图的颜色集合表分别如图6所示。此方法可使得初始解空间复杂度得到大大降低，有关详细讨论见5.2节。
图6. 确定图4中4个子图的颜色集。其中设定C(1)={r1 }，C(16)={b16 }，C(31)={r31 }，C(46)={b46 }以及C(61)={y1 }。（a）子图G1 ； （b）子图G2 ； （c）子图G3 ；（d）子图G4 。
3.4. DNA 序列的编码
由于DNA计算中作为“数据”的DNA序列在“运算过程”中是通过特异性杂交来实现的，因此，DNA计算中的编码要受到诸如解链温度、DNA序列的相似度、ΔG等众多条件的约束，而且要受到诸如问题的规模、链的长度、实验环境等诸多因素的影响。因此，DNA计算中的编码问题是一个非常复杂而困难的问题。许多学者视DNA序列中的编码问题为NP-完全问题，目前已有不少学者在不同约束条件下关于编码问题的算法。本文采用的编码不仅考虑特异性杂交反应，而且要考虑重点采用PCR技术的编码，综合设计，给出如下约束条件：
（1）所有编码没有超过连续4个A、4个T、4个C或4个G的现象；
（2）任意编码的GC含量为40%~60%；
（3）任意两条编码没有连续8个以上的碱基是相同的；
（4）任意一条编码自身不存在连续4个碱基的互补序列；
（5）任意一条编码的3′或5′末端的连续5个碱基和其他编码中的任意5个碱基不能相同；
（6）作为引物的DNA序列自身形成二聚体的化学自由能变化的绝对值（Δ|G|）一般不超过6.0 kcal·mol–1（1 cal=4.1868 J）；
（7）作为引物的DNA序列间形成的二聚体的|ΔG|一般不超过9.0 kcal·mol–1 ，而引物间3′端形成的二聚体的|ΔG|则不能高于6.0 kcal·mol–1 。
根据以上约束条件，搜索计算所需要每个代表顶点颜色的DNA序列。我们在搜索计算时采用了文献[
27]中的方法进行了初步搜索计算，然后在得到的DNA序列中选择出所需要的DNA序列。选择原则是：若搜索的DNA序列的长度小于15碱基，从长度为20碱基中选择；若搜索的DNA序列的长度大于20碱基，则选择颜色数达到要求的碱基长度最小的DNA序列，并进而采用最新的Preimer软件（5.0）进行挑选检测。
定理3.1：令代表顶点v i 可能的颜色的DNA序列标记为x i ，x∈{r, b, y}，i = 1, 2,…, n，它的Watson-Crick互补的序列则用x i 表示。根据每个顶点可能的颜色集，可以确定，对于一个任意的图来讲，所需要编码的DNA序列的数量为
本文需要代表颜色的129个DNA序列如表1所示。
3.5. 探针的确定
DNA计算机的优点是巨大的并行性、海量的信息存储能力等。通过十多年的研究，我们以为DNA计算机的最大优势应该是利用合成仪器合成的DNA序列仍具有一定的生物活性，其中氢键之间的引力是最为主要的。利用这一特性，可以将大量的非解排除在初始解空间之外，这一优势，电子计算机是无法比拟的。而实现这一思想的方法就是如何设计杂交中的探针。本模型关于探针的设计方法步骤如下（以颜色数为k = 3为例说明）。
步骤1：按照上节的方法确定给定图G的颜色集：令V(G) ={v1 , v2 , …, vn }，并令按照1的顶点排序为v1 , v2 ,…, vn ，定义Cvi 表示顶点vi 的可着颜色集，i = 1, 2,…, n。
步骤2：探针集的确定。探针只在由步骤1中确定排序相邻的两个顶点之间建立，即只在顶点v
i 与v
i+1之间建立，其中i=1, 2,…, n−1。这里将探针记作
。若v
i 与v
i+1在G中相邻，则x
i 和x
i+1 不能取相同颜色；若v
i 与v
i+1在G中不相邻，则x
i 和x
i+1 可以取相同颜色。例如，图4中给出的子图G
1 中顶点7的颜色集合为{r
7 , y
7 }，顶点8的颜色集合为{r
8 , y
8 }，由图3可知，这两个顶点在子图G
1 中相邻，故只有相异颜色之间有探针：
步骤3：每个探针的DNA序列构成：对探针
，用 代 表x
i 的DNA序 列 的 后 半 段 和x
i+1 的 前 半 段 组 成的序列的补链构成。y
7 = 5′-AATACGCACTCATCACATCG-3′，r
8 = 5′-GACCTTACCGTTTAGAGTCG-3′，则有y
7 r
8 = 5′-CATCACATCGGACCTTACCG-3′，
=5′-CGGTAAGGTCCGATGTGATG-3′。
为了更清晰地反映探针集合，我们在此引入图论方法给予描述，并且这种方法在后面关于降低初始解空间分析方面很有用。
一个图G的探针图，记作B(G)，在不致混淆的情况下简记为B，定义为
依据探针的定义，在图3与图4的基础上，我们在图7中分别给出了图4中所示4个子图3-着色的探针图，分别记为B1 、B2 、B3 和B4 。从每个探针图中，很清楚地看到该图的探针数目及分布情况。
3.6. 初始解空间的合成
采用Adleman[
2]的方法进行初始解空间合成。将代表各个顶点可能的颜色的DNA序列x
vi 和各种探针
混合后，通过T4连接酶作用后，产生新的长DNA序列则代表每个子图可能解的初始解空间。
表1 代表每个顶点的可能着色的DNA序列
（续表）
图7. 图4中4个子图相应的探针图。（a）B1 ；（b）B2 ；（c）B3 ；（d）B4 。
这里用S(Gj )代表生成的初始解空间，即集合S(Gj ) =(xvj1 xvj2 …xvjt )，这里x∈{r, b, y}，j=1,2,…,m。如果每个xvi长为l个碱基，且每个子图的顶点个数为t，则所生成的代表可能解的DNA序列长为t×l个碱基，j=1,2,…,m。
这里要说明的是，在合成每个子图初始解空间的时候，如果顶点vi 和vi+1 之间有边，则在杂交反应中，采用集合P1 中的探针，由于这些探针本身就不包含两个顶点着相同颜色的情况，则在初始解空间时，就可以删除一些相邻顶点着同色的非解。因此，在构建初始解空间时，若子图中含有的边e ={vi , vi+1 }的数量比较多，则可以删除较多的非解。
对于每个子图的合成初始解空间的具体步骤为：先用T4多核苷酸激酶（T4 PNK）对DNA序列x
vi 进行 5′ 端磷酸化。其次，将磷酸化产物与探针在10×T4PNK缓冲液中进行退火，反应条件为：94℃、5 min、50℃、10 min。再次，使用T4连接酶（T4 DNA ligase）对退火产物进行连接反应，16℃过夜。最后以连接产物为模板，以
，x∈{r, b, y}，j={1,2,…,m}为引物对，进行PCR扩增，得到的DNA序列的集合，即为每个子图的初始解空间。
3.7. 非解删除
删除非解实际上就是将
中的每条边两端具有同色的DNA序列从初始解空间S(G
j )中删除，主要是利用PCR技术来删除非解。在具体的删除非解的过程中，我们将
中的边分为两种情况，对不同的情况，具体操作分正向边和单边两种情况。
3.7.1. 正向边
在由
导出子图中，首先选择较长的路或者圈来从S(G
j )中删除非解。文中建立所谓的并行性PCR方法来删除非解。令G
1 为含有顶点子集V(G
1 ) = {v
1 , v
2 , …, v
t }的子图，v
1 , v
2 , …, v
t 为G
1 的顶点序列（排序方法见3.3节）。
若i < j，则e = v
t v
j 是一个正向边；否则即为反向边。如果路中所有的边均为正向边，则该路为正向路，否则为反向路。
其具体方法在此以路
为例给予说明（其他的路类似进行）。这条路上其实包含三条边：v
i v
j 、v
j v
y 和v
yv
z ，对此情况，在第一次PCR时，分别以
和
为引物对进行扩增。此时x
i 和x
j 、x j 和x
y 、x
y 和x
z 均不能同时取同色，这样DNA序列就被分成5个片段，然后逐级合并成长为t×l个碱基的DNA序列。利用此方法，能同时对多条边所对应的非解都进行删除。具体实现步骤见4.4节，理论分析5.3节。这样就可以使得利用较少次的PCR反应，同时删除多条边对应的非解。
3.7.2. 单边
在对
导出子图中所有路或圈删除非解后，有可能剩下一些单边，它们所对应的非解删除方法如下：对一条单边v
i v
j 删除非解，需要进行3次PCR反应，即可将这条边对应的非解删除。令x
i ∈C v
i ，x
j ∈C
vj ，且在第一次PCR时，将分别以
和
为引物进行扩增，这里，x
i 与x
j 不能同时取同色，这样代表顶点v
i 和v
j 着同色的DNA链将不被扩增出来，使得非解被删除。当完成了对每个子图的
中的边删除非解后，就可得到代表每个子图G
j （j=1,2,…,m），正常着色的DNA序列。
3.8. 子图合并及新子图中的非解删除
在获得了代表每个子图的解的DNA链之后，通过对子图进行合并，并删除合并后代表非解的DNA链，主要包括三步。
步骤1：合并子图Gj 和Gj+1 （j={1,2,…,m}）。利用桥点的DNA序列，以PCR为工具，将删除非解后的代表这两个子图的正常着色的DNA序列拼接在一起。若|V(Gj )|= t1 ，|V(G j+1 )| = t2 ，则形成长为(t1 + t2 – 1)×l个碱基的DNA序列，这些DNA序列将作为图G的二级导出子图G[V(Gj )∪V(Gj+1 )]的所有可能的解。
步骤2：按照3.7节所述的非解删除方法，对每个导出子图G[V(Gj )∪V(Gj+1 )]进行删除非解，更确切地讲，删除边集Ej, j+1 = {uv∈ E(G); u∈V(Gj ), v∈V(Gj+1 )}中每条边所对应的非解，即可得到代表其正常着色的DNA序列。
步骤3：对二级或更高级的导出子图重复步骤1和步骤2的操作，直至合并为图G，并得到代表图G正常着色的DNA序列。
3.9. 解的检测
采用测序的方法得到最终的代表每个子图的解的DNA序列，以及代表图G的解的DNA序列，并利用软件Gene Tool进行分析，得到图G的正常着色方案。
4. 实例与实现
为了实现所设计的图顶点着色DNA计算模型，本节对图1中对61个顶点图G的3-着色问题进行生化试验验证。这个实验规模不仅是迄今为止DNA计算研究中实验规模最大的一个实验，而且因为其通用性，证明了它的搜索计算能力可以超越O(359 )。
4.1. 子图划分及颜色集确定
由3.2节子图划分的方法以及子图顶点排序的方法，我们最终得到图G的4个子图如图4所示。按照3.3节的方法，4个子图的颜色集为图6所示。
4.2. 编码
按照3.5节中给出的编码方法，代表每个顶点可能的颜色的DNA序列如表1所示。根据3.5节中探针的构建方法和每个子图所对应的探针图（图7），共需要构建的探针的数目为185条：
所有的129条DNA序列和185条探针序列均由生工生物工程（上海）股份有限公司合成。
4.3.构建初始解空间
对每个子图采用了PCR技术合成初始解空间。具体以第一子图为例说明：将代表颜色的33条DNA序列的5′端磷酸化后，与相应的46条探针混合，用T4DNA连接酶进行连接后，再用引物对
进行扩增，得到大小为320bp的DNA序列集合即为初始解空间,见图8（a）。第二、三和四子图初始解空间的构建与第一个子图相同，见图8（b）~（d）。采用Gel Extract on Kit（U-gene），将回收产物溶于50μL的无菌水中，测其浓度为400ng·μL
–1。
图8.初始解空间的构建及检测，图中M即为φ174-Hae Ⅲ digest DNA marker。（a）~（d）中的泳道1为所构建的每个子图的初始解空间，其中，（a）~（d）分别对应S(G1)、S(G2)、S(G3)和S(G4)，每个DNA序列的大小为320bp。（e）中1–17对应的引物对为
和
。（f）中1~15泳道对应的引物对为
和
。 对各子图的初始解空间进行检测。以第一子图为例，分别用
，其中，x={r,b,y}，i=2,3,…,16为引物，初始解空间的DNA序列稀释50倍后作为模板，进行PCR反应，判断初始解空间是完备的。PCR的反应体系和反应条件同上。这里以子图G1的检测结果为例[图8（e）、（f）]，其余相同。
4.4.子图删除非解
将这些边分成可以形成路或圈以及边，分别针对三个基本类型给出实验结果。
4.4.1.路和圈
对于，路和圈采用了所谓的并行性PCR方法来删除非解。即由每次删除一条边，变成了同时删除多条边，使得PCR操作次数大大减少。在此以子图G2中的路P=16–20–22–26–30为例给出实验结果：
首先，分别以
和
为引物对，以初始解空间中DNA链稀释50倍为模板，把全长为320bp的第二子图库链DNA序列分解成了几个大小不同的片段：100bp（16~20）、60bp（20~22）、100bp（22~26）、100bp（26~30）和40bp（30~31）[图9（a）、（b）]。其中，16~20指从顶点16到顶点20，其余类同。图9（a）中泳道5的引物对为
，无电泳条带产生，是由于在构建初始解空间时不存在同时含有r
22与y
26的DNA序列。
其次，进行该圈第二次PCR操作。分别以
为引物，以图9（a）泳道1和3的PCR产物的混合物为模板，得到了140bp的电泳条带；以
为引物，以图9（b）泳道1和4的PCR反应产物的混合物为模板，得到了120bp的电泳条带；以
为引物，以图9（b）泳道2和5的PCR反应产物的混合物为模板，得到了120bp的电泳条带。电泳结果见图9（c）。
再次，进行该圈第三次PCR操作。以
为引物，以图9（a）泳道6和图9（c）泳道1的PCR产物的混合物为模板，得到了220bp的电泳条带。电泳结果见图9（d）。
最后，进行该圈第四次PCR操作。以
为引物，分别以图9（d）泳道1和图9（c）泳道2的PCR产物的混合物为模板；以图9（d）泳道1和图9（c）泳道3的PCR产物的混合物为模板进行，分别得到了两个全长320bp的电泳条带，电泳结果见图9（e）。此步骤的具体操作示意图如图9（f）所示。上述反应结束后，我们可以发现，生成了两组解：b
16r
20y
22r
26y
30r
31和b
16r
20y
22r
26b
30r
31。这两组解将作为新的模板，进入下一次非解删除过程。
图9.对圈C=16–17…31–16删除非解的实验结果。（a）泳道1~6对应的引物对为
和
；（b）泳道1~5对应的引物对为
和
；（c）泳道1~3对应的引物对为
和
；（d）泳道1~2对应的引物对为
；（e）泳道1~2对应的引物对为
；（f）PCR操作流程示意图。 4.4.2.两端颜色未定的边
对于两端颜色未定的边，采用了PCR技术删除非解。在此以第一个子图中的边e={4,8}为例给出实验结果。
首先，以上轮PCR的产物为模板，分别以
、
和
为引物对进行第一次PCR，结果如图10（a）所示。其中，当用
为引物时，没有PCR产物生成。
其次，以
为引物，以图10（a）的泳道1和3PCR产物的混合物为模板，进行第二次PCR操作，得到了160bp的电泳条带，见图10（b）。
最后，以
为引物，以图10（a）泳道5和图10（b）泳道1的PCR产物的混合物为模板进行PCR反应，得到了全长为320bp的电泳条带[图10（c）]。至此e={4,8}的三次PCR操作完成，得到全长为320bp的DNA序列的集合，且DNA序列中代表顶点4和8的着色方案已经确定为r
4和y
8。
图10.对边e={4,8}删除非解的实验结果。（a）泳道1和2、3和4、5和6的PCR产物分别以
和
为引物对；（b）中泳道1的PCR产物以
为引物对；（c）中泳道1的PCR产物相同，以
为引物对。 4.4.3.相关联的顶点的颜色已确定的边
对于相关联的顶点的颜色已确定的边，利用了PCR技术进行检测，删除非解。以第三子图的边e={(34),(39)}为例进行给出实验结果，如图11所示。当在子图G
3中完成删除圈C=34–38–42–46–34的所有PCR反应，以及完成了圈C=34–38–42–46–34第一次PCR反应之后，形成了代表6条解的DNA序列，其中顶点39和42分别为b
39、y
39、r
42和y
42。为了删除非解，利用引物对
，以6条DNA序列为模板，进行PCR反应，此时，出现DNA片段的则代表非解[图11（a）]。在图11（a）中，泳道5、6、7、8、11和12中出现了长为80bp的电泳条带。实验结果表明，编号为（3）、（4）和（6）的DNA序列将被删除。实验方案示意图如图11（b）所示。
图11.对边e={(34),(39)}删除非解的实验结果。（a）所有泳道对应的引物对均为
，泳道1和2的模板对应解（1），泳道3和4的模板对应解（2），泳道5和6的模板对应解（3），泳道7和8的模板对应解（4），泳道9和10的模板对应解（5），泳道11和12的模板对应解（6）；（b）非解删除示意图；“\”代表操作后被删除的非解。 4.5.子图合并及删除非解
完成了对每个子图的并行操作后，需要找出代表图1中所示的图G的正常3-着色的DNA链。这就需要将各个子图的解合并，并进一步删除非解(见4.4节)。具体合并和删除非解的结果见下文。
第一步将经过上述反应后，将代表满足子图G
1和G
2正常3-着色的解的长度为320bp的DNA序列的混合物两两混合作为模板，以r
1与
为引物，进行PCR扩增，得到长度为620bp的DNA链，就是图G中导出的子图G[V1∪V2]的所有可能的3-着色解，也就是子图G[V1∪V2]的初始解空间。然后对此初始解空间利用与上述子图非解的删除方法完全来删除其中的非解。得到的结果记为X
i,i=1,2,3,4，见图12（a）、（b）。
同时用相同的方法处理子图G3和G4，得到的结果记为Yi,i=1,2,3,4,5,6，见图12（c）~（e）。
图12.子图G[V1∪V2]和G[V3∪V4]的解。（a）泳道1和2对应解X1和X2；（b）泳道1和2对应解X3，泳道3和4对应解X4；（c）泳道1和2对应解Y1，泳道3对应解Y2；（d）泳道1对应解Y3,泳道2对应解Y4；（e）泳道1对应解Y5，泳道2对应解Y6。
将得到全长为620bp的DNA序列混合作为模板，以
为引物对，进行PCR扩增，得到长度为1220bp的DNA序列集合，其中也含有图G非解。用同样的方法进行删除非解，最后得到的DNA序列即代表了满足图G正常3-着色的解。共有8条DNA序列，分别代表8个解（图13）。
图13.图G的解，M3为150 bp ladder的DNA marker。泳道1~8分别对应解Z1~Z8。
将图13中的8条DNA序列回收后，连接在pMD 19-T载体上，并转化E.coli DH5α后，在北京奥科生物技术有限公司进行测序，得到满足图G正常3-着色的解，记为Zi(i=1,2,…,8)。
5.复杂性分析
本节在理论上较为系统地分析了文中所提出模型的算法复杂性问题，重点集中在降低初始解空间与为提高生物操作速度而提出的并行PCR操作方法。在初始解空间的复杂性方面，给出了一般计算公式，并分析了最坏与最好的情形。为了分析方便，在5.1节中引入图中链的计算公式，该公式可用于计算图中路的计数研究。
5.1.图中链的计数公式
本节给出求解一个给出图的任意两个顶点之间的walk(链)数目的计算公式，这个公式可用于路径的计数，进而用于分析通过合理地减少顶点颜色降低初始解空间复杂度的大小。
引理5.1[
28]设G是一个n子图，且V(G)={v
1,v
2,…,v
n}。A是G的相邻矩阵。那么从顶点v
i开始到v
j结束的长度为l的路径的数目为矩阵A
l中(i,j)位置的值。这里A
l是l个A相乘后得到的矩阵。
5.2.降低初始解空间复杂性的分析
在过去已有的一些用于NP-完全问题的DNA计算模型中，以为DNA分子是纳米级的，可以用大量的DNA分子来表示无穷的数据。而一般很少考虑在初始解空间中删除大量非解的优化计算的思想，总是采用枚举方法。事实证明这种用空间换时间的思想是不可取的。原因有两个：第一，随着问题规模的增大，所需要编码的DNA数量随之增大，就有可能无法得到足够数量的DNA分子；第二，即使通过增大DNA分子的长度，找到了一定数量的DNA分子，但由于DNA分子的增长，则会导致后续的生化试验操作的难度大大增大，不仅影响实验结果的可靠性，甚至无法操作。因此，如何降低DNA计算中初始解空间的DNA分子数量是至关重要的。
为了降低求解图顶点着色问题DNA计算模型的初始解空间，模型中采用了两种方法：第一种方法是3.2节中所给出的子图划分方法；第二种方法是3.3节给出的子图顶点排序方法。并在这两种方法的基础上给出子图中每个顶点颜色集。在子图颜色集的基础上，引入了探针图的概念。
实际上，我们引入探针图已经将顶点排序与减少顶点颜色集这两种方法的信息全部包括在其中。下面，我们利用探针图来给出模型中初始解空间中不同DNA序列数目的计算公式。这个公式由下述定理给出。
定理5.2设G是一个n子图，G1是按照3.2节中给出的一个子图。若V(G1)={v1,v2,…,vt}，且顶点1与顶点t分别是它的两个桥点。令B(G1)表示G1的探针图，则G1的初始解空间中不同DNA链的数目是图B(G1)中从顶点1到顶点t的长度为t–1的路径的数目，记作NP(1,t)，由如下公式给出：
证明由探针图B(G1)的定义知，B(G1)中的顶点xi代表图中顶点vi可着的颜色，B(G1)的边{xi,zi+1}表示xi与zi+1之间构成的探针，即表示在初始解空间中，当顶点vi着色为x时，顶点vi+1可以着颜色z，x,z∈{r,y,b}。因此，B(G1)中任意一条从顶点r1到顶点bt的路径代表了子图G1的一种着色，而从顶点r1到顶点bt的所有的路径代表了初始解空间中全体可能的解。
进一步，我们来考察B(G1)图的结构，该图可分为t组，下标为i的表示第i组。由B(G1)的定义知道：第i组只与第i+1组之间有边相连，且一定有边相连。因此，在探针图B(G1)中，从顶点r1到顶点bt的每条路径的长度只能为t–1，且从顶点r1到顶点bt的每条walk就是从顶点r1到顶点bt的每条路径。故由引理5.1，本定理获证。证毕。
推论5.3图4所示的子图G1、G2、G3和G4中初始解空间中不同DNA链的数目分别是：89、81、412和151条；删除枚举型初始解空间中非解比例是：99.9998%、99.9998%、99.999%和99.9997%。
证明由定理5.2知，图G1中初始解空间中DNA链的数目就是G1的探针图B1（图7）中从顶点r1到顶点b16之间长度为15的数目N33(r1,b16)。
为了计算N33(r1,b16)，利用引理5.1，先给出图B1的相邻矩阵：
其中，相邻矩阵中行列A(B1)的标记与探针图B1中顶点的对应关系为
不难算出，A(B
1)
15(1,33)=89。这说明了对子图G
1进行3-着色，代表所有可能3-着色的初始解空间中含有不同DNA链的条数为89。与枚举型需要的DNA链3
16=43046721相比：
≈0.000002=0.0002%。也就是说，我们在构建子图G
1的初始解空间S(G
1)时删除了99.9998%的非解。
类似的，对子图G2，可知A(B2)15(1,32)=81；对于子图G3，A(B3)15(1,35)=412；对于子图G4，有A(B4)15(1,32)=151。说明在构建S(G2)、S(G3)和S(G4)时，分别有99.9998%、99.999%和99.9997%的非解被删除。证毕。
5.3.并行型PCR技术降低运算复杂度
在实验中，子图G1中所有长度大于等于2的路径进行被分为正向路径和反向路径（见3.7节）。在上节实验操作中，关于非解删除主要使用的是我们提出的并行型PCR删除技术，该技术的应用对象是正向路径。下面，我们对使用并行PCR技术可大大降低生物操作次数的机理给予较为详细的分析。首先给出并行型PCR删除非解的一般性方法与步骤。
设P=vi0vi1…vim是子图G1中的一条顶点数为m+1、边数为m的正向路径。由于在进行并行PCR时必须考虑整个子图，因而在进行PCR操作时必须考虑两个桥点v1和vt，有如下三种情况。
情况1：路径的两个端点v1和vt不是子图的桥点，即vi0≠v1、vim≠vt，对此情况，需要增加这两个桥点v1和vt，如图14（a）所示。
情况2：路径的两个端点v1和vt中恰有一个是子图的桥点，即或vi0=v1、vim≠vt；或vi0≠v1、vim=vt；对此情况，需要增加一个桥点vt或v1，如图14（b）所示。
情况3：路径的两个端点v1和vt都是子图的桥点，即vi1=v1且vit=vt，对此情况，只考虑路径P的情况，如图14（c）所示。
图14.正向路径与桥点的三种情况。
由于桥点的颜色已经确定，故上述情况2与情况3中与桥点相邻的顶点的着色集合中不含桥点的颜色。基于并行PCR技术中顶点的确定（见上述三种情况），我们统一成上述情况1的情况，即对于情况2和3中删除与桥点相邻的边：从情况2中的路径P删除一条边{vi1,vi2}或{vi(m–1),vim}，得到与情况1类似的路径P′；从情况3中的路径P中删除两条边{vi1,vi2}和{vi(m–1),vim}，得到与情况1类似的路径P′。
下面来介绍并行PCR方法，仅考虑上述情况1的路径。首先按照图14中的方法确定正向路径P=vi0vi2…vim的顶点数目及次序；然后进行PCR操作。其实，PCR扩增的次数只与由图14中确定的顶点数或者边数有关。如对于情况1，第一次PCR扩增时的扩增对分别为：<v1,vi0>、<vi0,vi1>、…、<vi(m–1),vim>、<vim,vt>；第二次PCR是在第一次PCR结果的基础上，分别从两边以相邻的两个片段进行PCR扩增；第三次在第二次的基础上再从两边分别以相邻的两个片段进行PCR扩增。在图15中，我们分别以5个顶点（即两条边路径）和6个顶点（即3条边的路径）的情况给予说明，这里的连接边表示对两个或多个顶点之间实行的PCR扩增。
由图15可以看出，边数是2的路径需要进行PCR的次数为3，边数为6时需要PCR的次数为4。一般的，边数为x时，按着并行PCR方法，需要多少次？我们有如下定理。
图15.并行PCR扩增技术示意图。
定理5.4设P是子图G1中一条边数为x的正向路径。当2l–1<x≤2l时，定义〈x〉=2l，则并行PCR操作次数，记作PCR(x)，应为
证明根据对情况1进行证明。此时，路径的两个端点v1和vt不是子图的桥点，即vi0≠v1、vim≠vt；如果路径P包含x条边，那么路径的顶点数目为x+1，由于此路径不含桥点v1和vt，按照并行PCR方法，需要再增加两个桥点，使得顶点数为x+3[图14（a）]。假设x+2=2l，第一次PCR操作的顶点对的数目即为增加了桥点v1和vt之后的边数，为(x+3)–1=x+2=2l。按照并行PCR的定义，第二次操作顶点对的数目为(x+2)/2，2l–1个，第3次PCR操作对的数目为2l–2，……，第l次PCR操作对的数目为2l–(l–1)=2，第l+1次操作即可完成全部PCR操作，即推出：当x+2=2l时，PCR操作的次数l+1。所以PCR(x)=l+1=1+log22l=1+log2〈2l〉=1+log2〈x+2〉。即证明了当x+2=2l时结论成立。同理可以证明当x+2=2l+1时结论成立，即PCR(x)=l+2。
下面，我们来证明x+2=2l+1的情况。
类似于上述证明，路径P的顶点数为x+1，加上两个桥点，使得顶点数为x+3，当x+2=2l+1时，即x+3=2l+2个顶点，因此，第一次PCR操作对的数目为(x+3)–1=x+2=2l+1；第二次操作对的数目为2l–1+1个，第3次PCR操作对的数目为2l–2+1，…，第l次PCR操作对的数目为2l–(l–1)+1=3，第l+1次操作的次数为2，第l+2即可完成全部PCR操作。另一方面，将x+2=2l+1代入式（5.1），有PCR(x)=l+2=1+(l+1)=1+log22l+1=1+log2〈2l+1〉=1+log2〈x+2〉，即证明了当x+2=2l+1时结论成立。
由于对于任意2≤y<2l，x+2=2l+y对应的PCR操作次数不小于x+2=2l+1对应的PCR操作，但不大于x+2=2l+1对应的PCR操作次数，而这两个PCR操作次数均为l+2，这就证明了，对于任意2≤y<2l，x+2=2l+y时，结论成立。正如上面所述，图14中第二种情况和第三种情况最终都可以转换成第一种情况，所以本定理得证。
定理5.4完整地刻画了并行PCR操作时，其正向路径的长度x与PCR操作次数的关系。显然，并行PCR操作可大大降低操作次数，使得DNA计算机的运行速度得到极大的提高。我们知道，逐边删除非解，即一条一条地删除非解，每次需要3次PCR(见第4节)。下面，我们通过表2与图16中曲线可以清楚地看到并行PCR的优势。
表2 逐边删解与并行PCR方法PCR操作次数对照表
图16.逐边删解与并行PCR方法PCR操作次数曲线。其中，x表示正向路径P的边数，y表示PCR操作次数。
进一步，我们有：
推论5.5设P是子图G1中边数为x的一个正向路径，则有如下结论：
证明令x+2=2l+y，1≤y<2l，则〈x+2〉=2l+1=2(2l+y–y)<2(2l+y)；又因为2l>y，所以，2l+2l>y+2l，即2l+1>y+2l，从而有：
y+2l<2 l+1<2(2l+y)，此即x+2<〈x+2〉<2(x+2)，从而有log2(x+2)<log2〈x+2〉<log22(x+2)，因而，
由洛必达法则有
从而本推论获得证明。
推论5.5说明，随着子图中正向路径P中边数的增加，并行PCR方法操作的优势越大，即DNA计算的速度越快。由于每次PCR需要的时间较长（约半个小时），因此，更显示出并行PCR方法的优势。
6.结论与讨论本
文建立了一种用于求解图顶点着色的DNA计算模型。本文对该模型进行了详细的论述。该模型延续了上一章中介绍的DNA计算模型的优势，同时利用对图进行分解与合并的操作，使得在实际处理中，大部分的生化实验可以并行操作，进而使得该模型可用于求解较大规模的图顶点着色问题。本文利用该模型成功地对一个含有61个顶点的图进行了求解。
在目前已建立的DNA计算模型中，几乎都采用枚举方法来构建初始解空间。而用这种方法构建的初始解空间中自然存在大量非解，因此也就不能避免解空间指数爆炸问题。而且，利用这种方法，还可以使编码的数量多，长度增加，进而加大了生化操作的难度和实验费用。本模型所建立的子图初始解空间提出了两个原则：一个是图顶点序列的首、尾点的度数尽可能大；另一个是子图的顶点序列中相邻的顶点在原图中尽可能有边相连。按照这两个原则，该DNA计算模型在构建初始解空间的时候，就删除了相当数量的非解，使得初始解空间不再枚举，进而回避了初始解空间指数爆炸问题。通过计算，我们对每个子图所建立非枚举型的初始解空间中不同DNA链的数目分别为89、81、304和151，极大地降低了初始解空间，不但回避了解空间指数爆炸问题，而且可以使得生物操作更加方便，生物结果更加可靠。
通过子图的分解与合并，可以同时处理多个子图。在文章中，我们同时对四个子图进行了处理，并且同时对图G导出子图G[V1∪V2]和G[V1∪V2]也采用并行处理。而且，子图分解后，解空间也随之减少。从而使得一个复杂的NP-完全问题在一个较短的时间内更加容易地完成了。
并行操作这也是本模型的一个关键技术创新点，它使得实验速度得到了极大的提高。这里的平行操作主要包括两点：第一，因为子图的分解而导致的并行操作；第二，实验中对图的路或者圈的删除非解的操作也是并行的。在实验过程中，我们将许多条边按它们顶点的顺序形成或长或短的路（或圈），这就使得我们在实验中，可以对多条边同时处理。这样也就大大缩短了实验的时间。
在本文中，由于待求解的图的规模较大，所需要的编码较多，这就涉及了编码的质量和数量这一相互矛盾的指标。编码的质量越高，计算的可靠性越高，但是编码的数量反而越小。本文对已有编码的约束条件进行了改进，使得得到了较多的寡核苷酸序列，通过实验验证，这些序列能够保证DNA计算的可靠性。因此本文中提出的编码约束条件可用于其他相关的DNA计算中。
虽然，本章建立的DNA计算模型可用于处理较大规模的问题。然而因为随着问题规模的继续增大，所需要基本的DNA序列数目也会增大，从而导致DNA序列的长度不断增长。当达到一定的规模的时候，利用此DNA计算模型就可能会面临一些新的问题。在本项工作的研究过程中主要是实验过程中，遇到了假阳性现象。这也是DNA计算过程中对应的错误杂交的主要类型。也就是说如何用对定性的生化实验带来的误差给出可靠的定量分析是很重要的。这些问题都将作为我们进一步研究的目标。
致谢
感谢国家自然科学基金项目（61632002、61379059、61572046）的资助。
Compliance with ethics guidelines
Jin Xu, Xiaoli Qiang, Kai Zhang, Cheng Zhang, and Jing Yang declare that they have no conflict of interest or financial conflicts to disclose.
感谢国家自然科学基金项目（61632002、61379059、61572046）的资助。()
PDF
(4958KB)
