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

Computation in Chemistry: A Summary of the Development and Models of DNA Computing

作　　者：尹晓尧 李非 伯晓晨 骆志刚[1] 左小磊[3] 

机构地区：[1]国防科技大学计算机学院并行与分布重点实验室,长沙410073 [2]军事医学研究院辐射医学研究所,北京100850 [3]中国科学院上海应用物理研究所物理生物学研究室,上海201800

出　　处：《化学进展》2017年第11期1297-1315,共19页Progress in Chemistry

基　　金：国家自然科学基金项目(No.21422508)资助~~

摘　　要：电子计算机的发展给人类社会进步带来了极大的推动作用,但是随着电子计算机制造工艺趋于极限,人们迫切需要找到一种新的计算体系来满足日益增长的计算需求。DNA计算因其超强的信息存储、大规模的并行计算能力和超低的能耗而受到了广泛的关注。自1994年Adleman博士在实验室利用DNA完成了一个6顶点哈密尔顿路求解问题开始,各种计算模型纷纷涌现。本文首先对DNA计算的基本原理和实验操作手段进行了简单的介绍,然后对DNA相关的理论进行了阐述,包括DNA计算中序列编码设计的理论、DNA计算模型复杂度分析与通用计算能力的证明;在此基础上,对突破性的DNA计算模型进行了概括,进而根据实验操作的具体手段将所有已知模型进行了分类,按照类别进行了综述,并随后挑选了该类别中经典的模型进行更为直观的分析。更进一步,在文章的最后,结合笔者的工作对DNA计算领域的前景进行了展望。The development in computer science has brought a great impetus to the advance of human society.However,as the manufacturing process goes to the limit,there is an urgent need to find a newcomputing system to meet the growing demand for computing. DNA computing has attracted great attention due to its advantages in huge information storage,large scale parallelism and very lowenergy consumption. Many different models have been established ever since the experimental implementation of solving a 6 vertices Hamilton pathway problem by Adleman in 1994. In this paper,a brief introduction to the basic principles and experimental operations in DNA computing is first given,and the theories in this field are illustrated,including the DNA sequence design,complexity of different models and the proof of universal computing power. Moreover,the models regarded as breakthroughs in the field are summarized. All the models are classified based on the specific means inconducting the experiment,and reviewed according to different classes. More detailed descriptions are further set forth for a classical model in each class. At last,a prospect is made based on our work in this area.

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

分 类 号：O69[理学—化学] Q523[生物学—生物化学]