第27章 DNA计算
DNA是自然界唯一能够自我复制的分子，是重要的遗传物质。DNA计算是利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池。再按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后利用分子生物技术检测出所需要的运算结果。本章介绍DNA计算的生物学基础、基本原理、基本操作、编码方法及DNA计算系统的原型。
27.1 DNA计算的提出
DNA计算（DNA Computing）是1994年由美国南加州大学的Adleman博士提出的[83]。Adleman利用DNA（脱氧核糖核酸）对一个有向图的Hamilton路径问题进行编码，借助一系列生物操作求解出这一图论中的NP-完全问题。DNA计算是利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池。再按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后利用分子生物技术检测出所需要的运算结果。
27.2 DNA计算的生物学基础
构成生物体最小单位的细胞是由细胞膜、细胞质和细胞核组成的。细胞核由核质、染色质、核液三部分组成，是遗传物质存储和复制的场所。细胞核位于细胞的最内层，它内部的染色质在细胞分裂时，在光谱显微镜下可以看到产生的染色体。染色体主要由蛋白质和脱氧核糖核酸（DNA）组成，它是一种高分子化合物，脱氧核糖核酸是组成的基本单位。由于DNA大部分在染色体上，可以传递遗传物质，因此，染色体是遗传物质的主要载体。
DNA的基本元素是核苷酸，核苷酸又分为腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）和胸腺嘧啶（T）。依据其拥有碱基的类型不同，可以将核苷酸分成4类：A核苷酸、G核苷酸、C核苷酸、T核苷酸。一个核苷酸的羟基可与另一个核苷酸的羟基相互作用形成一种较弱的氢键，键的形成遵从互补性配对原则：A和T配对（2个氢键），C和G配对（3个氢键）。DNA的4种核苷酸分子形成各种不同的特殊组合或序列便构成了成千上万种基因，携带着不同的遗传信息，指导和控制着生物体的进化、生理、形态和行为等多种性状的表达。
1953年，Waston和Crick经研究发现DNA是一种高分子化合物，DNA分子是两条各由4种脱氧核糖核酸组成的双螺旋长链结构，它们构造出一个右手双螺旋结构，如图27.1所示。当碱基排列呈现这种结构时，分子能量处于最低状态。利用Watson-Crick互补性原则，单链DNA分子能够形成双链分子。
图27.1 DNA的双螺旋结构
27.3 DNA计算的基本原理及主要步骤
DNA计算是利用巨量的不同的核酸分子杂交，产生类似某些数学运算的一种组合结果并对其进行筛选来完成的。核酸分子杂交应用核酸分子的变性和复性的性质，使来源不同的DNA片段按碱基互补关系形成双链分子。
DNA计算的基本思想是，利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池（Data Pool），再按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后，利用分子生物技术（如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等），检测所需要的运算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入，在试管内或其他载体上经过一定时间完成可控的生物化学反应，以此来完成运算，使得从反应后的产物中能得到全部的解空间。
在DNA计算系统中，DNA分子中的密码作为存储的数据，当DNA分子之间在某种酶的作用下瞬间完成某种生物化学反应时，可以从一种基因代码变为另一种基因代码。如果将反应前的基因代码作为输入数据，那么反应后的基因代码就可以作为运算结果。
DNA计算最大的优点是充分利用海量的DNA分子中的遗传密码，以及巨量的并行性。
DNA计算主要包括以下3个步骤。
（1）编码：将所要解决的问题映射为一个分子的集合。
（2）计算：进行各种生化反应，如杂交、连接及延伸等生成可能解空间。
（3）解的分离和读取：如PCR反应和凝胶电泳。
DNA计算模型运行示意图如图27.2所示。输入的是DNA片段和一些生物酶，然后通过可控的生物化学反应，输出DNA片段，这些DNA片段，就是所需要的问题的解。DNA计算的基本原理可视为将实际问题创造性地映射到DNA计算这种模式上去。
图27.2 DNA计算模型运行示意图
27.4 DNA计算的基本操作
DNA计算的基本操作是通过物理操作和化学操作两种生物操作来实现的。物理操作是指对外部条件（如温度）的调控；化学操作是指起催化剂作用的各种酶。下面介绍一些DNA计算中的基本的生物操作。
（1）变性：DNA双链加热（85～95℃）分解为两条DNA单链。
（2）复性：变性后的两条DNA单链冷却后形成DNA双链。将两个互补的DNA单链结合在一起的过程，也称为退火。
（3）杂交：单链互补形成双链结构。杂交就是利用DNA分子的变性与复性，使DNA片段按照碱基互补原则杂交成双链分子。杂交不仅能在DNA链与DNA链之间，RNA链与DNA链之间，也可以在PNA链与DNA链之间，杂交本质就是在一定条件下使互补核酸链实现复性。
（4）切割：限制性酶在特定位置上把一条DNA链切割成两条。DNA的切割分为外切和内切。图27.3给出了核酸外切酶的作用示意图。图27.4给出了混合DNA分子的单链内切割作用示意图。
图27.3 核酸外切酶的作用示意图
（5）连接：将两个有黏性末端的DNA链通过DNA连接酶连接在一起，如图27.5所示。
图27.4 混合DNA分子的单链内切割作用示意图
图27.5 DNA分子的连接
（6）延长：给DNA分子一端添加核苷酸让DNA链变长，一般用聚合酶，如图27.6所示。
图27.6 DNA分子的延长
（7）缩短：用核苷酸外切酶从DNA链的末端切除核苷酸，如图27.7所示。
图27.7 DNA分子的缩短
（8）分离：用凝胶电泳的方法使DNA链按长度不同分离，如图27.8所示。
（9）提取：将含有特定子串的DNA链提取出来，如图27.9所示。
（10）破坏：利用限制性酶或外切酶，破坏被标记的链。
（11）复制：利用聚合酶链式反应（即PCR扩增），可复制DNA链。这种方法，可使链的数目成指数速度增长，因此复制的效率是非常高的。复制可以分为3个过程，如图27.10所示。
图27.8 凝胶电泳示意图
图27.9 提取的示意图
（12）重组：DNA重组或分子克隆就是将不同来源的DNA分子在体外进行特异切割，重新在一个载体上连接起来，组装成一个新的杂合DNA分子，再将其导入宿主细胞，随着细胞的繁殖而使重组的基因扩增，形成大量子代DNA分子。
图27.10 DNA分子的复制（PCR扩增）
27.5 DNA计算的编码问题
1. DNA编码问题的提出
DNA计算是通过DNA分子的杂交来完成的，编码希望最大程度地使被编码的DNA分子都能够完成杂交，而不希望出现非完全互补的DNA分子的杂交及完全互补的DNA分子不杂交的现象出现。为了降低错误，杂交目前主要有3种途径：一是优化DNA计算中表示每个信息元的编码；二是避免出现不希望的各种二级结构；三是提高生化操作的可靠性和精度。
2. DNA编码问题的描述
DNA计算中编码问题的形式化语言表述为，在由DNA分子4个碱基组成的字母集合∑DNA=｛A，T，C，G｝上，存在一个长度为n的DNA分子的编码集合S，显然集合S的大小|S|=4n。求S的一个子集C⊆S，使∀si，sj∈C满足
τ（si，sj）≥k（27.1）
其中，k为正整数；τ是评价DNA编码性质的准则，如海明距离、移位距离、最小相同子序列数目等。评价DNA编码的指标为编码数量、编码质量。
总之，DNA编码问题就是在满足一定物理约束及化学约束等各种约束条件下筛选出尽可能好的DNA编码，以便应用DNA计算解决各种实际问题。
3. DNA计算编码的约束条件
DNA计算要求DNA编码有足够的码长以表现出特异性，一般要求DNA编码长度L（A）≥10。根据实际问题的规模n，至少需要n个DNA编码，即A中元素个数|A|≥10。
（1）连续性约束。连续相同核苷酸数目过多的DNA序列与正常的DNA序列在二级结构上的差异，会导致解链温度及杂交温度不同，因此，有必要控制DNA序列连续相同的核苷酸数目。
（2）编码距离约束。编码距离是指两个编码之间相似度的参数。一般认为距离与相似度成反比。DNA编码之间的匹配关系可用海明距离来描述。海明距离就是两个等链长的DNA序列之间对应位碱基不相同的碱基对数目，海明距离越小，发生错误杂交的机会越大。因此，好的DNA编码之间海明距离有下界。
（3）解链温度约束。解链温度一般是指一半的DNA分子发生变性时的温度，影响解链温度的因素主要有外部条件（温度）和内部结构（GC含量和分子类型）两种。
（4）Gibb自由能增量约束。自由能的变化通常用ΔG来表示。它是影响DNA分子热力学稳定性的关键参数，影响ΔG的因素主要是反应物的浓度及DNA分子的组成。任意两个DNA分子之间的杂交反应可用化学方程式表示为
其中，yx为杂交后的双链。
4. DNA编码方法
由于DNA计算模型的多样性，目前常见的DNA编码有以下几种方法。
（1）模板-映射方法。分为两个步骤：一是寻找一定要求的二进制串作为模板集T，其中1代表A/T的位置，0代表G/C的位置；二是寻找满足一定要求的二进制串作为映射集合M，由
T×M→S（27.3）
得到满足条件的DNA编码序列S，其规则为，1×1→T，1×0→A，0×1→G，0×0→C。
（2）最小长度子串方法。设长度为ns的DNA序列的相同子串的最大长度为nb-1，而长度为nb的子串出现的次数不能超过一次。于是定义
ϕ=（nb-1）/n（27.4）
为DNA序列之间的相似度。显然ϕ越大，DNA分子的相似度就越小，出错杂交的概率也就越小。
（3）遗传算法。遗传算法研究的是一组对象，而不是一个单一的对象。它有许多搜索轨迹，具有隐含并行性。然而由于影响编码的因素太多，遗传算法很难应用于编码搜索。为此，Deaton等就用DNA遗传算法解决了DNA计算问题。
此外，还有利用智能优化算法、线性编码算法等来解决DNA编码问题，这里不再赘述。
27.6 DNA计算系统的原型
1994年，Adleman用DNA序列和对DNA进行简单的生物操作解决了有向图的Hamilton路径问题。他使用的是具有7个节点的有向图，如图27.11所示。
图27.11 具有7个节点的有向图
Hamilton路径问题：一个具有指定节点vin和vout的有向图，当且仅当存在一个始于vin、止于vout可相容的“单向”边缘线序列e1，e2，…，en（即一条路径），且经过每一个其他节点只有一次，则有一条Hamilton路径。
Adelman生化运算实验计算步骤如下。
（1）问题的编码及输入，每个节点的编码Oi（i=0，1，…，6）长度为20bp（base pair），即20个核苷酸链（字母链），保证编码是可识别的、唯一的。
（2）生成一个通过图的随机路径集，通过温度控制，DNA链接酶，溶液来实现。
（3）搜索出以O0开始O6结束的路径集，通过以O0和O6作引物的聚合酶链反应来实现。
（4）搜索出具有6个边的路径集，层析分离，3%～5%琼脂糖凝胶。
（5）搜索出不重复边的路径集，生物素亲和层析磁珠分离。
（6）选择出最短路径，电泳分离，选取分子量最小者。
上述Adleman应用生化运算实验计算解决了有向图的Hamilton路径问题，可视为DNA计算系统模型的原型。