描述
开 本: 16开包 装: 平装胶订是否套装: 否国际标准书号ISBN: 9787030664747
编辑推荐
脱氧核糖核酸,计算模型
内容简介
《DNA计算模型设计与实现》围绕DNA计算领域的前沿热点问题，结合新型DNA计算模型，提出了相应的解决方案：构建了大规模图顶点着色计算模型、基于环形DNA分子的**团问题计算模型，并予以实验验证。同时，利用多种纳米技术，如链置换及自组装技术，并结合金颗粒、DNA核酶等纳米材料，构建了多种DNA分子逻辑电路。《DNA计算模型设计与实现》阐述的内容能够为DNA计算领域的重要热点问题，以及大规模级联逻辑电路提供新的解决思路。同时也从侧面证明了DNA新型计算的可实现性。
目 录
目录
前言
第1章 绪论 1
1.1 DNA计算的研究背景及意义 1
1.2 国内外研究现状 3
1.2.1 理论计算模型 5
1.2.2 实验操作模型 6
1.2.3 DNA计算的优势与存在问题 22
1.3 DNA计算涉及的研究领域 24
1.4 本书的内容结构安排 25
第2章 DNA基础知识 28
2.1 DNA分子结构 28
2.1.1 DNA的发现历史 28
2.1.2 DNA的组成与碱基互补配对 29
2.1.3 Watson-Crick模型的发现 30
2.1.4 不同的DNA双螺旋结构 31
2.2 实验手段部分 33
2.2.1 PCR扩增技术 33
2.2.2 聚丙烯酰胺凝胶电泳 36
2.2.3 琼脂糖凝胶电泳 38
2.2.4 实时荧光定量PCR 41
2.2.5 原子力显微镜 43
2.2.6 透射电子显微镜 45
第3章 基于线性DNA分子图顶点着色计算模型 49
3.1 图顶点着色问题概述 50
3.2 模型设计及算法步骤 50
3.3 实验验证 52
3.3.1 子图分解 52
3.3.2 合成各个子图代表顶点颜色集合的DNA编码与探针 53
3.3.3 子图求解 55
3.3.4 子图合并 69
3.3.5 解的测序 70
3.4 本章小结 71
第4章 **团问题计算模型 73
4.1 **团问题概述 74
4.2 理论模型设计与算法(两个模型) 74
4.2.1 基于环形DNA分子的**团计算模型理论构建 74
4.2.2 基于环形DNA分子增长法的**团计算模型理论构建 77
4.3 实验验证及分析 81
4.3.1 基于环形DNA分子的**团计算模型 81
4.3.2 基于环形DNA分子增长法的**团计算模型 90
4.4 本章小结 97
第5章 基于分子电路的DNA计算 99
5.1 逻辑电路概述 99
5.1.1 逻辑电路的简介 99
5.1.2 DNA逻辑电路的物质基础 100
5.1.3 DNA逻辑电路的基础实验操作 100
5.1.4 DNA逻辑电路的发展 101
5.1.5 DNA逻辑电路的意义 101
5.2 基于纳米颗粒的逻辑电路 102
5.2.1 纳米颗粒简介 102
5.2.2 基于纳米颗粒的逻辑电路的发展 104
5.2.3 基于纳米颗粒的逻辑电路研究工作 105
5.3 基于链置换的分子逻辑电路 122
5.3.1 链置换简介 122
5.3.2 基于链置换的分子逻辑电路的发展 122
5.3.3 基于链置换的分子逻辑电路常用工具 123
5.3.4 基于链置换级联效应的DNA电路 124
5.3.5 基于链置换催化效应的DNA电路 127
5.3.6 基于链置换的分子逻辑电路研究工作 130
5.4 基于自组装技术的分子逻辑电路 150
5.4.1 自组装技术的发展应用 150
5.4.2 基于自组装技术的分子逻辑电路的发展 156
5.4.3 基于自组装技术的逻辑电路研究工作 157
5.5 本章小结 169
第6章 总结与展望 172
6.1 DNA计算小结 172
6.2 DNA计算基本模型综述 172
6.3 DNA计算的优缺点 173
6.4 DNA计算面对的问题以及展望 174
参考文献 176
彩图
前言
第1章 绪论 1
1.1 DNA计算的研究背景及意义 1
1.2 国内外研究现状 3
1.2.1 理论计算模型 5
1.2.2 实验操作模型 6
1.2.3 DNA计算的优势与存在问题 22
1.3 DNA计算涉及的研究领域 24
1.4 本书的内容结构安排 25
第2章 DNA基础知识 28
2.1 DNA分子结构 28
2.1.1 DNA的发现历史 28
2.1.2 DNA的组成与碱基互补配对 29
2.1.3 Watson-Crick模型的发现 30
2.1.4 不同的DNA双螺旋结构 31
2.2 实验手段部分 33
2.2.1 PCR扩增技术 33
2.2.2 聚丙烯酰胺凝胶电泳 36
2.2.3 琼脂糖凝胶电泳 38
2.2.4 实时荧光定量PCR 41
2.2.5 原子力显微镜 43
2.2.6 透射电子显微镜 45
第3章 基于线性DNA分子图顶点着色计算模型 49
3.1 图顶点着色问题概述 50
3.2 模型设计及算法步骤 50
3.3 实验验证 52
3.3.1 子图分解 52
3.3.2 合成各个子图代表顶点颜色集合的DNA编码与探针 53
3.3.3 子图求解 55
3.3.4 子图合并 69
3.3.5 解的测序 70
3.4 本章小结 71
第4章 **团问题计算模型 73
4.1 **团问题概述 74
4.2 理论模型设计与算法(两个模型) 74
4.2.1 基于环形DNA分子的**团计算模型理论构建 74
4.2.2 基于环形DNA分子增长法的**团计算模型理论构建 77
4.3 实验验证及分析 81
4.3.1 基于环形DNA分子的**团计算模型 81
4.3.2 基于环形DNA分子增长法的**团计算模型 90
4.4 本章小结 97
第5章 基于分子电路的DNA计算 99
5.1 逻辑电路概述 99
5.1.1 逻辑电路的简介 99
5.1.2 DNA逻辑电路的物质基础 100
5.1.3 DNA逻辑电路的基础实验操作 100
5.1.4 DNA逻辑电路的发展 101
5.1.5 DNA逻辑电路的意义 101
5.2 基于纳米颗粒的逻辑电路 102
5.2.1 纳米颗粒简介 102
5.2.2 基于纳米颗粒的逻辑电路的发展 104
5.2.3 基于纳米颗粒的逻辑电路研究工作 105
5.3 基于链置换的分子逻辑电路 122
5.3.1 链置换简介 122
5.3.2 基于链置换的分子逻辑电路的发展 122
5.3.3 基于链置换的分子逻辑电路常用工具 123
5.3.4 基于链置换级联效应的DNA电路 124
5.3.5 基于链置换催化效应的DNA电路 127
5.3.6 基于链置换的分子逻辑电路研究工作 130
5.4 基于自组装技术的分子逻辑电路 150
5.4.1 自组装技术的发展应用 150
5.4.2 基于自组装技术的分子逻辑电路的发展 156
5.4.3 基于自组装技术的逻辑电路研究工作 157
5.5 本章小结 169
第6章 总结与展望 172
6.1 DNA计算小结 172
6.2 DNA计算基本模型综述 172
6.3 DNA计算的优缺点 173
6.4 DNA计算面对的问题以及展望 174
参考文献 176
彩图
免费在线读
第1章 绪论
1.1 DNA计算的研究背景及意义
电子计算机作为20世纪的三大科学革命之一，它的发展深刻地改变并影响着人们的日常生活，并且已广泛应用于经济、科技、军事等各个领域。然而，随着科学技术的飞速发展，传统计算机面临越来越多的困境与挑战，其中一个主要原因便是传统计算机复杂的集成电路和存储已经达到硅芯片的极限，难以再有很大的突破。19世纪60年代，时任仙童半导体公司工程师的戈登 摩尔提出了著名的摩尔定律：即集成电路芯片上所集成的晶体管数量，每18个月会扩大一倍，因此集成电路的计算能力也会提升一倍。过去的半个世纪，摩尔定律确实被一次次验证为“真理”，然而，摩尔定律真的没有尽头吗？越来越多的信息技术专家学者以及从业人员给出了否定答案。研究表明，当硅芯片上的晶体管达到纳米级别(10?9米)时，其大小只相当于几个分子，物理性质、化学性质都将会发生巨大变化导致芯片不能正常运行，这时便是摩尔定律的终点。
未来的计算机技术将向超高速、超小型、平行处理、智能化的方向发展。尽管受到物理极限的约束，采用硅芯片的计算机的核心部件CPU的性能还会持续增长。作为微处理器的重要衡量指标，每个微处理器上的晶体管数量由1971年的2308枚到2000年的3178万枚再到2017年的192亿枚；神威 太湖之光作为世界上首台运算速度超过十亿亿次的超级计算机，在2016年～2017年的两年四次超级计算机评比之中连续四次获得冠军；现如今的计算机已具备更多的智能成分，它具有多种感知能力、一定的思考与判定能力及一定的自然语言能力。除了提供自然的输入手段(如语音输入、手写输入)外，让人能产生身临其境感觉的各种交互设备已经出现，虚拟现实技术是这一领域发展的集中体现；传统的磁存储、光盘存储容量继续攀升，新的海量存储技术趋于成熟，新型的存储器每立方厘米存储容量可达10TB(以一本书30万字计，它可存储约1500万本书)。
硅芯片技术的高速发展同时也意味着硅技术越来越接近其物理极限，为此，世界各国的研究人员正在加紧研究开发新型计算机，计算机从体系结构的变革到器件与技术革命都要产生一次量的乃至质的飞跃。科学家们在探索过程中，不断算机模型[4-6]等，这些成果极大地拓宽了计算机领域的边界，为计算机领域注 入了新的活力。新型的量子计算机、光子计算机、生物计算机、纳米计算机等将在不久的将来走进我们的生活，遍布各个领域。量子计算机是基于量子效应开发的，它利用一种链状分子聚合物的特性来表示开与关的状态，利用激光脉冲来改变分子的状态，使信息沿着聚合物移动，从而进行运算。量子计算机中数据用量子位存储，同样数量的存储位，其存储量比通常的计算机大许多。同时量子计算机能够实行量子并行计算，其运算速度可能比目前个人计算机的PentiumⅢ晶片快10亿倍。目前正在开发中的量子计算机有三种类型：核磁共振(nuclear magnetic resonance，NMR)量子计算机、硅基半导体量子计算机、离子阱量子计算机。光子计算机即全光数字计算机，以光子代替电子，光互连代替导线互连，光硬件代替计算机中的电子硬件，光运算代替电运算。与电子计算机相比，光子计算机的“无导线计算机”信息传递平行通道密度极大。一枚直径为5分硬币大小的棱镜，它的通过能力超过全世界现有电话电缆的许多倍。光的并行、高速特性，天然地决定了光子计算机的并行处理能力很强，具有超高速的运算速度。生物计算是以生物分子作为信息载体，用生物酶和各种生化操作作为信息处理工具的一种新型计算模型。根据基本信息载体的不同，可分为DNA计算模型、RNA计算模型和蛋白质计算模型等。生物计算机完成一项运算，所需的时间仅为10微微秒，比人的思维速度快100万倍。DNA分子计算机具有惊人的存储容量，1立方米的DNA溶液，可存储1万亿亿的二进制数据。DNA计算机消耗的能量非常小，只有电子计算机的十亿分之一。由于生物芯片的原材料是生物分子，所以生物计算机既有自我修复的功能，又可直接与生物活体相连。
各国政府在新型计算模型的研究中给予了足够的关注与资助，大大推进了相关领域的研究进程。例如，日本的DNA计算机研究计划已在1996年开始；随后，美国、欧盟各国相继出台了“生物计算”相关研究项目的一揽子计划。面对政府机构的导向性资助，相关商业公司和集团也敏锐地嗅到了分子计算新型技术的潜在商机。近年来，世界各国的大公司也大力投入，试图开创非传统计算的新时代。2002年，日本奥林巴斯公司正式宣布他们已经开发出**台可投入商业应用的分子计算样机；2009年，IBM公司宣布用DNA和纳米技术开发下一代微处理芯片，开创了分子计算的新纪元；2013年5月D-Wave System公司宣称NASA和Google共同预定了一台采用512量子位的D-Wave Two量子计算机；2019年7月，由澳大利亚新南威尔士大学的米歇尔 西蒙斯领导的团队，创建出了首个硅中双原子量子比特门，操作在0.8纳秒内完成，比现有其他基于自旋的双量子比特门快200倍，是迄今为止速度*快的，成为构建原子级量子计算机的一个重要里程碑；在2019年4月16日召开的全球分析师大会上，华为宣布成立战略研究院，由华为董事徐文伟担任院长，这个研究院将是华为统筹创新2.0的关键，其主要负责5年以上的前沿技术的研究，华为列举了三个新型技术的例子，包括光计算、DNA存储及原子级的制造。
近年来，DNA计算作为新兴计算领域的一部分，凭借其天然的微观分子特异性及优异的并行计算能力，吸引了越来越多研究人员的目光，已成为国际前沿热点研究领域。DNA分子具有微小、高并行、特异识别等优秀特性，从而具有极强的并行计算能力和海量信息存储等优势。同时，分子生物学家研究发现了一系列操作DNA的方法与技术：内切酶切割、连接酶连接、聚合酶链式反应(polymerase chain reaction，PCR)扩增、DNA测序技术、荧光标记以及分子自组装技术等，这些方法使DNA分子在生物操作上具有高度的可行性。早在20世纪60年代，Feynman已经提出了运用生物分子进行计算的设想，即构建一种“亚微观尺度的计算机”。1994年，美国南加州大学的Adleman教授将生物技术与DNA分子结合起来，成功求解了一个7个顶点6条边的有向哈密尔顿路径问题，他利用DNA分子作为信息载体，编码数学问题，并用内切酶来完成运算，*终通过电泳、测序等生物技术读取问题的解。Adleman实验的成功预示着以生物分子作为信息处理载体的新型计算机成为可能。这一研究成果迅速吸引了计算机、数学、化学及生物学等各个领域学者们的关注，之后，越来越多的研究人员开始投入到DNA计算的研究中，提出了很多DNA计算模型，并用其解决了很多相关的NP问题和经典逻辑问题。例如，Lipton建立的解决可满足性问题的DNA计算机[5]；Ouyang等采用平行折叠技术(parallel over lapassembly，POA)解决NP问题中图**团问题的DNA计算模型[7]；Liu等建立的表面计算模型[8]等。
随着生物计算学的不断发展，DNA计算这一交叉领域有了越来越广泛的应用前景，不断为新型计算机的发展拓宽道路。计算机的发展水平已成为衡量国家现代化程度及综合实力的重要指标，在社会经济发展中发挥着极其重要的作用。计算机产业已在世界范围内发展成为具有战略意义的产业。传统通用性CPU芯片在并行处理、多重处理以及解决NP问题等方面存在瓶颈，而DNA计算具有动态可变的开放式拓扑结构以及巨大的并行能力，因此在解决图染色等经典NP问题时具有先天优势。同时，DNA计算在纳米机器、海量信息存储、复杂计算、分子智能以及疾病检测等领域具有广泛的应用前景。
1.2 国内外研究现状
与传统的电子计算机不同，DNA计算是一种基于生化反应机理的新型信息处理模式。诺贝尔奖获得者Feynman在20世纪60年代初首次提出了分子计算的概念。1994年，Adleman使用DNA分子成功解决了一个哈密尔顿路径问题，开启了全新的分子计算，特别是DNA计算领域[4]。1995年，美国普林斯顿大学的Lipton教授提出了一种求解可满足性问题的DNA计算模型[5]。该模型是通过对DNA进行编码，使得到的DNA具有逻辑判断能力，从而使它能进行简单的“是”与“非”判断，这一思想被Faulhammer在实验中进行了相应的实现。1996年，Roweis等通过对生物计算机理的进一步研究，提出了新的DNA计算模型——粘贴模型[9]。然而，随着问题规模的扩大，编码信息的DNA链的数目呈指数增长，合成的初始解空间出现了指数爆炸现象。这使得基于粘贴模型的DNA计算进入了发展瓶颈，为了解决这种问题，一些研究学者提出不产生初始解空间，通过逐步生成解的方法来完成计算，这样就克服了试管存储能力有限的弊端，从而进一步开发了DNA计算的巨大潜力，促进了DNA计算的长足发展。到2000年，由于一种新的DNA计算实现方式——基于表面技术的DNA计算模型被Liu等提出，DNA计算迎来了一个新的阶段[8]。
自从1994年Adleman的实验成功以来，DNA计算经历了二十几年的蓬勃发展。在这期间，美国、英国、加拿大、中国、日本等国家的很多大学以及科研机构都相继加入到DNA计算这一新兴领域，并开展了一系列的研究工作。在该领域的研究中，每年在Nature、Science、Proceedings of the National Academy of Sciences of the United States of America等国际**权威期刊上都有**研究成果的论文发表。同时，国内外很多研究小组及机构也在进行着紧密地协作，并定期进行技术交流与讨论，例如，每年定期召开International Conferenceon DNA Computing and Molecular Programming和Bio-inspired Computation Conference:Theory and Application国际会议。正因为如此，DNA计算领域的研究发展迅速，在理论计算模型、实验操作模型以及检测技术方面都取得了很大的突破。有很多DNA计算模型如剪接模型、粘贴模型、插入/删除系统、*小计算模型等被提出。以上模型也表明了DNA计算模型具有高度并行性，存储容量巨大，降低问题复杂度，能量消耗极低，能在纳米级水平上精确操控的优势。
DNA计算目前主要可分为两大类计算模型，即理论计算模型和实验操作模型。理论计算模型是指通过建模，以DNA串为译码信息，用不同的生物操作即算子在DNA序列上执行操作并完成计算。实验操作模型是指在建立计算理论模型后，通过多种生化操作，在试管或特定的容器中完成的运算。这种模型与理论模型不同，其中所有的运算都必须通过实验操作完成。实验中存在的不确定因素很多，如PCR中将误差放大、杂交中DNA序列间的非特异性识别以及检测中出现假阳性现象等，这些问题的存在使实验操作模型比理论模型更难完成。因此，生化操作的改进与创新是推动该领域前进的必要条件，也为建立自动化的、通用的DNA计算机奠定了实验基础。
1.2.1 理论计算模型
在分子计算中，大量的理论模型被研究人员提出并验证。迄今为止，提出的理论模型主要有粘贴模型[9，10]、剪接模型[11，12]、插入-删除DNA计算模型[13，14]、k-臂DNA计算模型[15，16]、三链核酸DNA计算模型[17]、瓦片型计算模型[18-20]以及图灵机模型[21，22]等，其中研究*多的两类模型是粘贴模型和剪接模型。
1)粘贴模型
粘贴模型(sticker model)是一种基于Watson-Crick碱基互补配对的计算模型。这种模型包含一条长的储存链和许多条短的粘贴链，每条短的粘贴链与储存链上的特定区域互补。其基本原理是：利用DNA分子自身固有的碱基互补配对原则进行信息编码，将所要处理的问题映射为特
1.1 DNA计算的研究背景及意义
电子计算机作为20世纪的三大科学革命之一，它的发展深刻地改变并影响着人们的日常生活，并且已广泛应用于经济、科技、军事等各个领域。然而，随着科学技术的飞速发展，传统计算机面临越来越多的困境与挑战，其中一个主要原因便是传统计算机复杂的集成电路和存储已经达到硅芯片的极限，难以再有很大的突破。19世纪60年代，时任仙童半导体公司工程师的戈登 摩尔提出了著名的摩尔定律：即集成电路芯片上所集成的晶体管数量，每18个月会扩大一倍，因此集成电路的计算能力也会提升一倍。过去的半个世纪，摩尔定律确实被一次次验证为“真理”，然而，摩尔定律真的没有尽头吗？越来越多的信息技术专家学者以及从业人员给出了否定答案。研究表明，当硅芯片上的晶体管达到纳米级别(10?9米)时，其大小只相当于几个分子，物理性质、化学性质都将会发生巨大变化导致芯片不能正常运行，这时便是摩尔定律的终点。
未来的计算机技术将向超高速、超小型、平行处理、智能化的方向发展。尽管受到物理极限的约束，采用硅芯片的计算机的核心部件CPU的性能还会持续增长。作为微处理器的重要衡量指标，每个微处理器上的晶体管数量由1971年的2308枚到2000年的3178万枚再到2017年的192亿枚；神威 太湖之光作为世界上首台运算速度超过十亿亿次的超级计算机，在2016年～2017年的两年四次超级计算机评比之中连续四次获得冠军；现如今的计算机已具备更多的智能成分，它具有多种感知能力、一定的思考与判定能力及一定的自然语言能力。除了提供自然的输入手段(如语音输入、手写输入)外，让人能产生身临其境感觉的各种交互设备已经出现，虚拟现实技术是这一领域发展的集中体现；传统的磁存储、光盘存储容量继续攀升，新的海量存储技术趋于成熟，新型的存储器每立方厘米存储容量可达10TB(以一本书30万字计，它可存储约1500万本书)。
硅芯片技术的高速发展同时也意味着硅技术越来越接近其物理极限，为此，世界各国的研究人员正在加紧研究开发新型计算机，计算机从体系结构的变革到器件与技术革命都要产生一次量的乃至质的飞跃。科学家们在探索过程中，不断算机模型[4-6]等，这些成果极大地拓宽了计算机领域的边界，为计算机领域注 入了新的活力。新型的量子计算机、光子计算机、生物计算机、纳米计算机等将在不久的将来走进我们的生活，遍布各个领域。量子计算机是基于量子效应开发的，它利用一种链状分子聚合物的特性来表示开与关的状态，利用激光脉冲来改变分子的状态，使信息沿着聚合物移动，从而进行运算。量子计算机中数据用量子位存储，同样数量的存储位，其存储量比通常的计算机大许多。同时量子计算机能够实行量子并行计算，其运算速度可能比目前个人计算机的PentiumⅢ晶片快10亿倍。目前正在开发中的量子计算机有三种类型：核磁共振(nuclear magnetic resonance，NMR)量子计算机、硅基半导体量子计算机、离子阱量子计算机。光子计算机即全光数字计算机，以光子代替电子，光互连代替导线互连，光硬件代替计算机中的电子硬件，光运算代替电运算。与电子计算机相比，光子计算机的“无导线计算机”信息传递平行通道密度极大。一枚直径为5分硬币大小的棱镜，它的通过能力超过全世界现有电话电缆的许多倍。光的并行、高速特性，天然地决定了光子计算机的并行处理能力很强，具有超高速的运算速度。生物计算是以生物分子作为信息载体，用生物酶和各种生化操作作为信息处理工具的一种新型计算模型。根据基本信息载体的不同，可分为DNA计算模型、RNA计算模型和蛋白质计算模型等。生物计算机完成一项运算，所需的时间仅为10微微秒，比人的思维速度快100万倍。DNA分子计算机具有惊人的存储容量，1立方米的DNA溶液，可存储1万亿亿的二进制数据。DNA计算机消耗的能量非常小，只有电子计算机的十亿分之一。由于生物芯片的原材料是生物分子，所以生物计算机既有自我修复的功能，又可直接与生物活体相连。
各国政府在新型计算模型的研究中给予了足够的关注与资助，大大推进了相关领域的研究进程。例如，日本的DNA计算机研究计划已在1996年开始；随后，美国、欧盟各国相继出台了“生物计算”相关研究项目的一揽子计划。面对政府机构的导向性资助，相关商业公司和集团也敏锐地嗅到了分子计算新型技术的潜在商机。近年来，世界各国的大公司也大力投入，试图开创非传统计算的新时代。2002年，日本奥林巴斯公司正式宣布他们已经开发出**台可投入商业应用的分子计算样机；2009年，IBM公司宣布用DNA和纳米技术开发下一代微处理芯片，开创了分子计算的新纪元；2013年5月D-Wave System公司宣称NASA和Google共同预定了一台采用512量子位的D-Wave Two量子计算机；2019年7月，由澳大利亚新南威尔士大学的米歇尔 西蒙斯领导的团队，创建出了首个硅中双原子量子比特门，操作在0.8纳秒内完成，比现有其他基于自旋的双量子比特门快200倍，是迄今为止速度*快的，成为构建原子级量子计算机的一个重要里程碑；在2019年4月16日召开的全球分析师大会上，华为宣布成立战略研究院，由华为董事徐文伟担任院长，这个研究院将是华为统筹创新2.0的关键，其主要负责5年以上的前沿技术的研究，华为列举了三个新型技术的例子，包括光计算、DNA存储及原子级的制造。
近年来，DNA计算作为新兴计算领域的一部分，凭借其天然的微观分子特异性及优异的并行计算能力，吸引了越来越多研究人员的目光，已成为国际前沿热点研究领域。DNA分子具有微小、高并行、特异识别等优秀特性，从而具有极强的并行计算能力和海量信息存储等优势。同时，分子生物学家研究发现了一系列操作DNA的方法与技术：内切酶切割、连接酶连接、聚合酶链式反应(polymerase chain reaction，PCR)扩增、DNA测序技术、荧光标记以及分子自组装技术等，这些方法使DNA分子在生物操作上具有高度的可行性。早在20世纪60年代，Feynman已经提出了运用生物分子进行计算的设想，即构建一种“亚微观尺度的计算机”。1994年，美国南加州大学的Adleman教授将生物技术与DNA分子结合起来，成功求解了一个7个顶点6条边的有向哈密尔顿路径问题，他利用DNA分子作为信息载体，编码数学问题，并用内切酶来完成运算，*终通过电泳、测序等生物技术读取问题的解。Adleman实验的成功预示着以生物分子作为信息处理载体的新型计算机成为可能。这一研究成果迅速吸引了计算机、数学、化学及生物学等各个领域学者们的关注，之后，越来越多的研究人员开始投入到DNA计算的研究中，提出了很多DNA计算模型，并用其解决了很多相关的NP问题和经典逻辑问题。例如，Lipton建立的解决可满足性问题的DNA计算机[5]；Ouyang等采用平行折叠技术(parallel over lapassembly，POA)解决NP问题中图**团问题的DNA计算模型[7]；Liu等建立的表面计算模型[8]等。
随着生物计算学的不断发展，DNA计算这一交叉领域有了越来越广泛的应用前景，不断为新型计算机的发展拓宽道路。计算机的发展水平已成为衡量国家现代化程度及综合实力的重要指标，在社会经济发展中发挥着极其重要的作用。计算机产业已在世界范围内发展成为具有战略意义的产业。传统通用性CPU芯片在并行处理、多重处理以及解决NP问题等方面存在瓶颈，而DNA计算具有动态可变的开放式拓扑结构以及巨大的并行能力，因此在解决图染色等经典NP问题时具有先天优势。同时，DNA计算在纳米机器、海量信息存储、复杂计算、分子智能以及疾病检测等领域具有广泛的应用前景。
1.2 国内外研究现状
与传统的电子计算机不同，DNA计算是一种基于生化反应机理的新型信息处理模式。诺贝尔奖获得者Feynman在20世纪60年代初首次提出了分子计算的概念。1994年，Adleman使用DNA分子成功解决了一个哈密尔顿路径问题，开启了全新的分子计算，特别是DNA计算领域[4]。1995年，美国普林斯顿大学的Lipton教授提出了一种求解可满足性问题的DNA计算模型[5]。该模型是通过对DNA进行编码，使得到的DNA具有逻辑判断能力，从而使它能进行简单的“是”与“非”判断，这一思想被Faulhammer在实验中进行了相应的实现。1996年，Roweis等通过对生物计算机理的进一步研究，提出了新的DNA计算模型——粘贴模型[9]。然而，随着问题规模的扩大，编码信息的DNA链的数目呈指数增长，合成的初始解空间出现了指数爆炸现象。这使得基于粘贴模型的DNA计算进入了发展瓶颈，为了解决这种问题，一些研究学者提出不产生初始解空间，通过逐步生成解的方法来完成计算，这样就克服了试管存储能力有限的弊端，从而进一步开发了DNA计算的巨大潜力，促进了DNA计算的长足发展。到2000年，由于一种新的DNA计算实现方式——基于表面技术的DNA计算模型被Liu等提出，DNA计算迎来了一个新的阶段[8]。
自从1994年Adleman的实验成功以来，DNA计算经历了二十几年的蓬勃发展。在这期间，美国、英国、加拿大、中国、日本等国家的很多大学以及科研机构都相继加入到DNA计算这一新兴领域，并开展了一系列的研究工作。在该领域的研究中，每年在Nature、Science、Proceedings of the National Academy of Sciences of the United States of America等国际**权威期刊上都有**研究成果的论文发表。同时，国内外很多研究小组及机构也在进行着紧密地协作，并定期进行技术交流与讨论，例如，每年定期召开International Conferenceon DNA Computing and Molecular Programming和Bio-inspired Computation Conference:Theory and Application国际会议。正因为如此，DNA计算领域的研究发展迅速，在理论计算模型、实验操作模型以及检测技术方面都取得了很大的突破。有很多DNA计算模型如剪接模型、粘贴模型、插入/删除系统、*小计算模型等被提出。以上模型也表明了DNA计算模型具有高度并行性，存储容量巨大，降低问题复杂度，能量消耗极低，能在纳米级水平上精确操控的优势。
DNA计算目前主要可分为两大类计算模型，即理论计算模型和实验操作模型。理论计算模型是指通过建模，以DNA串为译码信息，用不同的生物操作即算子在DNA序列上执行操作并完成计算。实验操作模型是指在建立计算理论模型后，通过多种生化操作，在试管或特定的容器中完成的运算。这种模型与理论模型不同，其中所有的运算都必须通过实验操作完成。实验中存在的不确定因素很多，如PCR中将误差放大、杂交中DNA序列间的非特异性识别以及检测中出现假阳性现象等，这些问题的存在使实验操作模型比理论模型更难完成。因此，生化操作的改进与创新是推动该领域前进的必要条件，也为建立自动化的、通用的DNA计算机奠定了实验基础。
1.2.1 理论计算模型
在分子计算中，大量的理论模型被研究人员提出并验证。迄今为止，提出的理论模型主要有粘贴模型[9，10]、剪接模型[11，12]、插入-删除DNA计算模型[13，14]、k-臂DNA计算模型[15，16]、三链核酸DNA计算模型[17]、瓦片型计算模型[18-20]以及图灵机模型[21，22]等，其中研究*多的两类模型是粘贴模型和剪接模型。
1)粘贴模型
粘贴模型(sticker model)是一种基于Watson-Crick碱基互补配对的计算模型。这种模型包含一条长的储存链和许多条短的粘贴链，每条短的粘贴链与储存链上的特定区域互补。其基本原理是：利用DNA分子自身固有的碱基互补配对原则进行信息编码，将所要处理的问题映射为特
评论
还没有评论。