化学中的计算——DNA计算的发展与模型概述

来源：化学进展杂志2017年第11期北京时间：

作者：尹晓尧, 李非, 伯晓晨, 骆志刚, 左小磊

单位：1. 国防科技大学计算机学院并行与分布重点实验室 长沙 410073;<br />\r\n2. 军事医学研究院辐射医学研究所 北京 100850;<br />\r\n3. 中国科学院上海应用物理研究所物理生物学研究室 上海 201800

摘要：电子计算机的发展给人类社会进步带来了极大的推动作用，但是随着电子计算机制造工艺趋于极限，人们迫切需要找到一种新的计算体系来满足日益增长的计算需求。DNA计算因其超强的信息存储、大规模的并行计算能力和超低的能耗而受到了广泛的关注。自1994年Adlian博士在实验室利用DNA完成了一个6顶点哈密尔顿路求解问题开始，各种计算模型纷纷涌现。本文首先对DNA计算的基本原理和实验操作手段进行了简单的介绍，然后对DNA相关的理论进行了阐述，包括DNA计算中序列编码设计的理论、DNA计算模型复杂度分析与通用计算能力的证明；在此基础上，对突破性的DNA计算模型进行了概括，进而根据实验操作的具体手段将所有已知模型进行了分类，按照类别进行了综述，并随后挑选了该类别中经典的模型进行更为直观的分析。更进一步，在文章的最后，结合笔者的工作对DNA计算领域的前景进行了展望。

关键词：DNA计算,NP难问题,并行重叠组装模型,粘贴模型,剪接模型,DNA Tile自组装,生化信号逻辑门

基金资助：国家自然科学基金项目（No.21422508）资助