论文部分内容阅读
摘 要：自从Adleman博士最早利用DNA计算成功求解了7个顶点有向图的Hamilton问题以来，DNA计算[1]被引入多个研究领域，成为当今科技发展的热点之一。首先介绍DNA计算的基本原理及编码方法，其次阐述了DNA计算的主要模型，再次总结了国内外研究学者应用DNA计算解决的实际问题，最后列举了DNA计算改进的相关方向。
关键词：DNA计算；模型；NP完全问题；智能算法
中图分类号：TP301.4 文献标识码：A DoI: 10.3969/j.issn.1003-6970.2012.05.056
The Models and Applications of DNA Computing
BaI Xue
(Shandong Normal University College of management science and Engineering, Jinan 250014, China)
【Abstrac】Since Dr. adleman used DNa computing to achieve HPP with seven vertices successfully, DNa computing has been brought in various research areas and become one of the focuses of scientific development. Firstly, the basic principles and coding methods are introduced, following with the main models of it. In addition, we summed up the applications of DNa computing to solve practical problems. finally, several improved directions are listed.
【Key words】DNa computing; Model; the NP-complete problem; Intelligent algorithm
1 DNA计算简介
1.1 DNA计算原理
DNA是一种由许多脱氧核苷酸分子连接而成的高分子化合物，其中脱氧核苷酸由脱氧核糖、磷酸和含氮碱基三部分组成。因为碱基有腺嘌呤A、鸟嘌呤G、胸腺嘧啶T和胞嘧啶C四种类型，所以与之对应的核苷酸也有四种表现形式。DNA计算的基本原理是把需要运算的对象映射成DNA分子链，在生物酶的作用下生成初始数据池，然后按照一定的规则将原始问题高度并行地映射成DNA分子链的可控的生化过程，最后
利用现代分子生物技术[2-9]获得最终运算结果[10]。
1.2 DNA编码方法
Baum于1996年提出了降低DNA序列间相似度的假设，随后Garzon等人定义了DNA计算中的编码问题。DNA编码方法主要包括模板-映射方法、最小长度子串方法和随机搜索方法，其中模板-映射方法是由Wisconsin大学的Frutos等人提出的，2003年，刘文斌在该方法的基础上提出了模板框的概念；Feldkamp等人提出了一种最小长度子串评价方法，通过限制子序列出现的次数降低了编码之间的相似程度；2003年，Tulpant提出了随机搜索编码方法，采用随机方式生成DNA编码解空间，然后根据约束条件筛选出解空间中较好的DNA编码序列。
2 DNA计算模型
2.1 基于理论研究的DNA计算模型
1996 年，Roweis提出一种基于分子操作和随机访问内存的DNA计算粘贴模型，在运算过程中不需要酶的作用和DNA链的延伸，主要有合并、分离、设置和清除四种基本操作。随后，Kari等人在粘贴模型的基础上提出了粘贴系统的概念，由Paun等人[3，7，11]将其推广到更加普遍的形式上。2004年，许进等人对粘贴模型给予了更为详细的讨论。
1987年，Head在利用形式语言对DNA序列进行分析的基础上提出了剪接系统的概念[1，3，7]，Paun等人对该系统的通用性、计算能力和剪接运算等方面进行了详细的讨论[3，7，12]。2001年，Benenson等人利用剪接系统研制出一台具有编程能力的有穷自动机，并说明了剪接系统是计算完备的。
插入/删除模型是建立在上下文插入和删除基础上的抽象模型[3，4，11]，Paun等人于1998年利用上下文插入文法描述了递归可列语言，2002年，Takahara在第8届国际DNA计算机会议上阐述了插入/删除系统的计算能力。
k-臂模型是1999年由Jonoska等人提出的一种DNA计算模型，Seeman等人的研究结果表明3-臂和4-臂DNA分子是相当稳定的，而且k-臂DNA分子的3’端一般为单链延伸。
发夹模型是通过巧妙的DNA编码，使非可行解的DNA链在生化反应中形成发夹结构，通过DNA分子中BSTNI内切酶的识别位来清除这些发夹结构。2000年，Sakatomo等人利用该模型建立了一种求解可满足性问题的DNA计算模型。
质粒DNA模型是Head等人于2000年提出来的，质粒模型充分利用质粒DNA分子上的基因位，通过插入和删除操作，使每个质粒体与传统计算机中数据寄存器的作用相同。
2.2 基于生物操作的DNA计算模型
试管型DNA计算模型就是使DNA分子和生物酶在试管中进行生化反应，以验证DNA计算原理的可行性，整个计算分为实验准备阶段、计算中阶段和读出解阶段，Adleman的DNA计算实验就是在试管中进行的。
在表面型DNA计算模型中，DNA 链被固定在经过特殊化学处理后的固体表面上，通过对DNA分子进行重复标记、破坏、检测等操作，获得最后的运算结果[5-7，11]。表面DNA计算模型的主要创始人是Frutos等人，2000年，Liu等人介绍了一种基于表面方式的DNA计算模型，用于求解SAT问题。
DNA 芯片是由Forder等人提出的，是DNA片段以预先设计的排列方式固定在支持物表面形成的密集分子排列。芯片阶段是DNA计算机研制的最终阶段，芯片型的DNA计算机应是IT与BT相结合的产物，在芯片上可能集成了DNA分子的生化操作、生化反应，以及由DNA分子形成的解空间库、PCR扩增等等。
3 DNA计算解决的有关问题
3.1 某些NP完全问题
DNA计算是伴随着生物技术的发展而出现的分子生物学和计算机科学之间的交叉学科，其作为一种新生事物拓宽了人们对于自然计算现象的理解，特别是对生物计算的理解。目前，有关DNA计算和DNA计算机的研究进展迅速，并且将应用的触角伸向计算机网络、现代物流等方方面面：上海交通大学生命科学研究中心和中科院上海生命科学院成功研制出DNA计算机的试管雏形，首次在实验上将表面DNA计算和自动机结合到了一起；Rohani利用DNA计算算法，基于集群技术，首先分组所有城市，然后再选择一个配送中心，解决了对城市之间物流问题的分配与测定；杨磊等人提出了一种基于DNA计算的指定节点路由算法，殷脂等人提出了针对移动AdHoc网络QoS路由问题的闭环DNA计算模型。展望未来，DNA计算的发展充满着机遇与挑战，DNA计算的理论基础和实际实现值得人们的进一步探索，与智能系统中其他计算方法的结合也需要更好地研究[2]，科学地归纳出一套适合DNA计算的规则模式更是一项艰巨的任务。
关键词：DNA计算；模型；NP完全问题；智能算法
中图分类号：TP301.4 文献标识码：A DoI: 10.3969/j.issn.1003-6970.2012.05.056
The Models and Applications of DNA Computing
BaI Xue
(Shandong Normal University College of management science and Engineering, Jinan 250014, China)
【Abstrac】Since Dr. adleman used DNa computing to achieve HPP with seven vertices successfully, DNa computing has been brought in various research areas and become one of the focuses of scientific development. Firstly, the basic principles and coding methods are introduced, following with the main models of it. In addition, we summed up the applications of DNa computing to solve practical problems. finally, several improved directions are listed.
【Key words】DNa computing; Model; the NP-complete problem; Intelligent algorithm
1 DNA计算简介
1.1 DNA计算原理
DNA是一种由许多脱氧核苷酸分子连接而成的高分子化合物，其中脱氧核苷酸由脱氧核糖、磷酸和含氮碱基三部分组成。因为碱基有腺嘌呤A、鸟嘌呤G、胸腺嘧啶T和胞嘧啶C四种类型，所以与之对应的核苷酸也有四种表现形式。DNA计算的基本原理是把需要运算的对象映射成DNA分子链，在生物酶的作用下生成初始数据池，然后按照一定的规则将原始问题高度并行地映射成DNA分子链的可控的生化过程，最后
利用现代分子生物技术[2-9]获得最终运算结果[10]。
1.2 DNA编码方法
Baum于1996年提出了降低DNA序列间相似度的假设，随后Garzon等人定义了DNA计算中的编码问题。DNA编码方法主要包括模板-映射方法、最小长度子串方法和随机搜索方法，其中模板-映射方法是由Wisconsin大学的Frutos等人提出的，2003年，刘文斌在该方法的基础上提出了模板框的概念；Feldkamp等人提出了一种最小长度子串评价方法，通过限制子序列出现的次数降低了编码之间的相似程度；2003年，Tulpant提出了随机搜索编码方法，采用随机方式生成DNA编码解空间，然后根据约束条件筛选出解空间中较好的DNA编码序列。
2 DNA计算模型
2.1 基于理论研究的DNA计算模型
1996 年，Roweis提出一种基于分子操作和随机访问内存的DNA计算粘贴模型，在运算过程中不需要酶的作用和DNA链的延伸，主要有合并、分离、设置和清除四种基本操作。随后，Kari等人在粘贴模型的基础上提出了粘贴系统的概念，由Paun等人[3，7，11]将其推广到更加普遍的形式上。2004年，许进等人对粘贴模型给予了更为详细的讨论。
1987年，Head在利用形式语言对DNA序列进行分析的基础上提出了剪接系统的概念[1，3，7]，Paun等人对该系统的通用性、计算能力和剪接运算等方面进行了详细的讨论[3，7，12]。2001年，Benenson等人利用剪接系统研制出一台具有编程能力的有穷自动机，并说明了剪接系统是计算完备的。
插入/删除模型是建立在上下文插入和删除基础上的抽象模型[3，4，11]，Paun等人于1998年利用上下文插入文法描述了递归可列语言，2002年，Takahara在第8届国际DNA计算机会议上阐述了插入/删除系统的计算能力。
k-臂模型是1999年由Jonoska等人提出的一种DNA计算模型，Seeman等人的研究结果表明3-臂和4-臂DNA分子是相当稳定的，而且k-臂DNA分子的3’端一般为单链延伸。
发夹模型是通过巧妙的DNA编码，使非可行解的DNA链在生化反应中形成发夹结构，通过DNA分子中BSTNI内切酶的识别位来清除这些发夹结构。2000年，Sakatomo等人利用该模型建立了一种求解可满足性问题的DNA计算模型。
质粒DNA模型是Head等人于2000年提出来的，质粒模型充分利用质粒DNA分子上的基因位，通过插入和删除操作，使每个质粒体与传统计算机中数据寄存器的作用相同。
2.2 基于生物操作的DNA计算模型
试管型DNA计算模型就是使DNA分子和生物酶在试管中进行生化反应，以验证DNA计算原理的可行性，整个计算分为实验准备阶段、计算中阶段和读出解阶段，Adleman的DNA计算实验就是在试管中进行的。
在表面型DNA计算模型中，DNA 链被固定在经过特殊化学处理后的固体表面上，通过对DNA分子进行重复标记、破坏、检测等操作，获得最后的运算结果[5-7，11]。表面DNA计算模型的主要创始人是Frutos等人，2000年，Liu等人介绍了一种基于表面方式的DNA计算模型，用于求解SAT问题。
DNA 芯片是由Forder等人提出的，是DNA片段以预先设计的排列方式固定在支持物表面形成的密集分子排列。芯片阶段是DNA计算机研制的最终阶段，芯片型的DNA计算机应是IT与BT相结合的产物，在芯片上可能集成了DNA分子的生化操作、生化反应，以及由DNA分子形成的解空间库、PCR扩增等等。
3 DNA计算解决的有关问题
3.1 某些NP完全问题
DNA计算是伴随着生物技术的发展而出现的分子生物学和计算机科学之间的交叉学科，其作为一种新生事物拓宽了人们对于自然计算现象的理解，特别是对生物计算的理解。目前，有关DNA计算和DNA计算机的研究进展迅速，并且将应用的触角伸向计算机网络、现代物流等方方面面：上海交通大学生命科学研究中心和中科院上海生命科学院成功研制出DNA计算机的试管雏形，首次在实验上将表面DNA计算和自动机结合到了一起；Rohani利用DNA计算算法，基于集群技术，首先分组所有城市，然后再选择一个配送中心，解决了对城市之间物流问题的分配与测定；杨磊等人提出了一种基于DNA计算的指定节点路由算法，殷脂等人提出了针对移动AdHoc网络QoS路由问题的闭环DNA计算模型。展望未来，DNA计算的发展充满着机遇与挑战，DNA计算的理论基础和实际实现值得人们的进一步探索，与智能系统中其他计算方法的结合也需要更好地研究[2]，科学地归纳出一套适合DNA计算的规则模式更是一项艰巨的任务。