DNA计算是借助于分子生物技术进行计算的新方法。凭借着极大的存储密度和高度并行性，DNA计算为求解NP完全问题等复杂组合优化问题提供了一条全新的途径，开创了广阔的应用前景。《DNA计算核酸编码原理及方法》主要介绍DNA计算核酸编码原理及方法，具体包括DNA计算的研究进展和背景、DNA计算的生物化学基础、DNA编码问题及其复杂性分析、DNA二级结构预测和最小自由能模型、隐枚举核酸序列编码算法、DNA编码在图着色DNA计算中的应用。
更多科学出版社服务，请扫码获取。
《DNA计算核酸编码原理及方法》可作为从事DNA计算、纳米结构设计、分子自组装、高性能的计算的研究学者和学生的参考书，对相关专业的教师和科研人员进行科学研究也具有一定的参考价值。
第1章DNA计算的产生与发展
DNA（deoxyribonucleic acid）计算是借助于分子生物技术进行计算的新方法，凭借极大的存储密度和高度并行性，DNA计算为求解NP完全问题等复杂组合优化问题，提供了一种全新的途径，开创了广阔的应用前景。DNA编码质量的优劣决定了DNA计算的效率，DNA编码数量的多少决定了DNA计算可求解问题的规模，因此核酸编码是DNA计算研究中的重要课题。
随着20世纪70年代初期计算复杂性理论的形成，科学工作者发现并证明了大量来源于实际的组合优化问题是非常难求解的问题，即NP完全问题和NP难问题。20世纪80年代初期，应运而生了一系列现代优化计算方法，如模拟退火算法、遗传算法、蚁群优化算法、粒子群算法和人工神经网络算法等。这类算法中的每一个算法都以自然、人类、生物的行为方式或物质运动形态为背景，经过数学抽象建立算法模型，通过电子计算机来求解组合优化问题。然而，这些基于仿生计算的优化计算方法不能在有效的时间中找到最优解，而用次优可行解来代替最优解；即使算法找到了最优解，算法本身也并不能证明其是最优解。因此这一系列建立在模仿分子运动、遗传学、动物学、神经系统的现代优化算法并不能彻底解决复杂的组合优化问题。
DNA计算是一种基于DNA分子的并行计算模型，是在计算科学和分子生物学的基础上发展起来的一个新颖而极具发展潜力的交叉学科，这种基于生物分子的计算模式在求解NP完全问题时显示出了极大潜力。
1994年，美国南加州大学的Adleman\[1\]用DNA分子进行计算，求解出7个顶点的有向Hamilton路问题，成功地利用现代分子生物技术在DNA溶液的试管中进行了实验。这一研究成果很快引起了计算机、数学、分子生物学等领域的科学家的极大兴趣。它的重要意义不仅在于算法和速度，更在于采用了一种全新的介质作为计算要件，以生物技术来实现电子计算机无法解决的复杂组合优化问题。随后，在1995年召开的第一届国际DNA计算会议上，来自各个国家和地区的200多名科学家共同探讨并充分肯定了DNA计算机的可行性。该领域的专家普遍认为：一旦DNA计算机研制成功，其运算量是目前的传统计算机望尘莫及的，DNA计算是一个极具开发价值的研究领域。与传统的电子计算机相比，DNA计算机具有三个突出的优点：高度并行性、海量的存储能力、极低的能耗。
然而，当前DNA分子的操作技术的发展远不如电子计算机中的集成电路成熟。在DNA计算过程中，DNA分子间会发生非特异性杂交，导致实验出现错误甚至失败，极大降低DNA计算的可靠性和有效性。对DNA序列进行编码设计是DNA计算机研制中最为核心的问题。首先，编码质量的优劣决定了DNA计算的可靠性和有效性，直接影响着DNA计算能否按照预期的设计相互反应；其次，编码数量的多少决定了DNA计算求解问题规模的大小，与DNA计算机研究能否深入发展息息相关。所以，本书在详细分析编码质量和编码数量的主要影响因素的基础上，对DNA计算机中的编码问题及其算法进行了深入研究。
DNA计算的基本思想：DNA计算是以DNA相关的生物酶等作为基本材料，基于生化反应原理的一种新型的分子生物计算方法。利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，然后在生物酶的作用下，按照一定的规则将原始问题的数据运算映射成高度并行的DNA分子链可控的生化反应。最后，利用分子生物技术如聚合酶链反应（PCR）、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等，检测所需要的运算结果。DNA计算的关键是将经过编码的DNA分子作为输入，在试管内或其他载体上经过一定时间完成可控的生物化学反应，最后提取出代表问题解的DNA分子。
1994年Adleman求解7个顶点有向Hamiltion路的实验解释了DNA计算过程的三个基本步骤，其有向图G如图1.1所示。
图1.1有向图G存在唯一Hamiltan路v0→v1→v2→v3→v4→v5→v6
(1) 有向图的每一个顶点都编码为唯一的DNA分子，有向图的每一条边用相邻两顶点的DNA分子补链各取一半组成。
(2) 在一定的反应条件下，代表顶点和代表边的DNA分子相互杂交，相互连接形成长的DNA分子，产生这个有向图的路径。
(3)最后检测出代表该Hamiltion路的DNA分子。具体计算过程如下。
（1）解的产生。首先将图1.1中各顶点vi用长度为20个碱基的单链DNA(Oi)来代替，vi和Oi一一对应。若顶点vi和vj之间存在边e(i，j)，再根据Oi，Oj来合成图中各条边Oi→j，Oi→j同样由长度为20个碱基的单链DNA构成，前10个碱基取Oi的3′端10个碱基，后10个碱基取Oj的5′端10个碱基。这种DNA序列设计使得如果存在路径i→j和j→k，通过添加Oj的补链Oj，可以产生路径i→j→k。
如图1.2所示，以产生路径2→3→4为例，O2、O3、O4分别为20个碱基组成的单链DNA，代表v2、v3、v4三个顶点，O3是O3的补链。单链DNAO2→3和O3→4代表该有向图的边e(2，3)和e(3，4)。其中O2→3由O2的3′端10个碱基和O3的5′端10个碱基组成，O3→4由O3的3′端10个碱基和O4的5′端10个碱基组成。在O2→3和O3→4共同存在的DNA溶液中，加入一定浓度的O3，则代表路径2→3→4的双链DNA 就产生了。依此类推，当这一步连接反应包括了图1.1中所有的边e(i，j)时，图1.1中所有随机路径的DNA就可以在一步之间全部产生了。
图1.2产生DNA分子Hamiltion路径2→3→4
（2） 解的分离。在第（1）步中产生了各种路径，首先需要选出起点和终点分别为O0和O6的路径。使用O0和O′6作为引物，利用PCR对第（1）步的结果进行扩增，就能选择性地扩增那些从O0至O6的DNA路径。PCR扩增完毕后，DNA溶液中存在以O0为起点、O6为终点的不同长度的双链DNA，如图1.3所示。
图1.3以0开始6结尾的所有路径
由于从O0开始，每增加一个顶点，该双链DNA的长度就增加20个碱基。通过所有7个顶点的DNA路径，对应的碱基个数必须为140bp。通过凝胶电泳技术，在电镜下观察得到140个碱基对应的谱带，割下这条胶带，浸入双蒸水中提取DNA。（3） 解的检测。第（2）步得到了长度为140bp的DNA溶液，还要选出其中经过每个顶点各一次的DNA路径，如图1.4所示。应用亲和纯化法，选出经过所有顶点至少一次的DNA路径。先将DNA双链解开双螺旋成单链DNA，让其通过接有O1补的磁珠，只有含有O1序列的单链DNA才能由于互补链的结合而被滞留，这个操作分离出了经过O1的DNA。这样依次通过接有O2补、O3补、O4补和O5补的磁珠，最终得到了经过所有顶点至少一次的Hamilton路DNA分子。
图1.4以0开始6结尾的等长DNA链通过磁珠
将第（3）步的产物再进行PCR扩增，通过DNA测序等方法，检测目标DNA是否存在即可。1997年Garzon等\[2\]归纳了使用DNA分子解决计算问题的三个基本步骤：①问题编码(encoding)，这个步骤将现实计算问题映射转换为DNA分子计算模型；②相互反应(interaction)，这个步骤将设计好的DNA分子在一定温度、盐度和催化剂的作用下执行核心的生化计算；③解的提取(extraction)，这个步骤利用生物检测技术将代表解的DNA分子提取出来，使纳米级的DNA分子在宏观世界可见。
1.1国内外研究进展
Adleman实验的成功标志着科学家试图利用生物大分子(DNA、RNA、蛋白质等)来解决电子计算机无法求解的NP完全问题和构建新型的计算机的设想取得了重要突破，使DNA计算成为一个备受关注的学科，也使构建新型的计算机——DNA计算机成为可能。随后，国内外学者在Adleman 的分子计算模型基础上广泛开展了DNA 计算的研究工作，建立了一系列求解NP完全问题的DNA计算模型，如SAT、图着色、0-1规划、背包问题等计算问题的DNA 计算模型。1995年，受Adleman的启发，Lipton\[3\]提出DNA计算可以解决另一种NP完全问题——可满足性问题(SAT)。Lipton通过构造一个接触网络图，将SAT问题的解空间映射为通过接触网络图的起点和终点的所有哈密顿路。他首先利用DNA分子表示问题的所有可能解，然后利用生化反应删除非解。1996年，Roweis等介绍了一种新的DNA计算模型——粘贴模型，并用此模型解决了最小集合覆盖问题和数据加密问题。1997年，Ouyang等将另一个NP完全问题——图的最大团问题转化为最大独立集问题，利用并行重叠组装(parallel overlap assembly，POA)技术在实验室解决了一个6个顶点的最大团问题实例。1998年，Winfree等\[4\]设计出双交叉瓦片（tile)分子DX，利用到DNA 分子间的碱基互补配对特性，由几条DNA 单链在特定位置互补，交错位置而形成分子结构，如图1.5所示。Winfree发现以DX分子作为组件可以实现规则结构的自组装。
图1.5Winfree自组装模型
书单推荐
