DNA计算模型.ppt

DNA计算模型 任晓玲 2012年4月17日 一、引言 DNA计算的原理 DNA分子作为信息载体（A、C、G、T四种碱基） 原始问题映射为DNA分子链 数据运算映射为对DNA分子链的生物操作（高度并行） 在分子生物实验室完成这一系列的分子生物操作 运算载体 运算工具：生化酶——连接酶、核算内切酶、聚合酶等 生化反应系统：退火、杂交、连接等 检测系统：电泳技术（重量、极性）；荧光技术[1]；纳米金粒子技术[2] （一次性检测出某个组合结合的构成情况）等 一、引言 DNA计算的特点 1、高密度的存储量：1gDNA所能存储的信息量相当于10000亿张普通CD光盘； 2、高度的并行性：DNA串的并行操作数可达1014 ； 3、极低的能耗：DNA计算的能耗仅仅相当于当前电子计算机的十亿分之一。 二、DNA计算模型 对目前出现的DNA计算模型按照所使用的计算主体的分子形态进行较为系统的分类： 2.1、双链DNA模型 2.2、粘贴模型（单双链交替） 2.3、单链DNA模型 RNA模型 发夹模型 2.4、表面模型 2.5、闭环DNA模型 2.6、三维DNA模型 2.1、双链DNA模型 双链DNA模型包括两种形式。一种是根据碱基互补配对原则使单链DNA分子杂交形成的双链模型，这一系列是指利Adleman-Liption的模型发展而来的计算模型，其核心的生物反应为杂交反应。 另一种是直接构造DNA双链分子，通过各种生物酶的催化来实现的双链模型，其核心的生物反应为酶切反应和酶联反应。 2.1、典型文章 第一类 Junzo Watada及其合作者使用传统的双链模型解决了基于“距离”的数据聚类问题[3,4]。他们将距离进行预处理，使其可以通过DNA序列的长短进行表示，然后对数据和边进行编码，最终实现其自动聚类。 第二类 文献[5]将双链模型与酶连锁反应（LCR）相结合，实现了对可满足性问题的求解。LCR所具有的漂亮的性质使我们可以通过控制引物来使那些只有满足条件的双链才能再次形成粘性末端并进行新一轮的链接实验，这种方式是逐个连接变量的一种较好的实验操作。 2.2、粘贴模型 粘贴模型是一种由存储链（含有个由个碱基组成的不重叠的单链分子）和粘贴链（与存储链上个位置的某个位置特定互补配对的个碱基构成的单链PNA或DNA分子构成[6]）构成的部分双链分子结构。 其信息（一般为布尔变量的形式）被编写在存储链上，输入一个初始试管，输出若干个最终试管。分离已退火的粘贴链可以分析存储复合物，从而读出最终试管的输出物，当然试管中也有可能不含任何存储复合物。 2.3、单链DNA模型 单链DNA模型是指使用单链DNA或者RNA为载体的计算模型。根据其所形成的单链分子的形态具体的分为发夹结构和线性（存储）结构。 发夹结构 “发夹”是单链核酸分子(DNA 或RAN )中由于局部互补杂交而形成的一种空间茎环结构，因其形似发夹而得名。其结构如图所示 链状结构 另外一种线性存储模型是使用单链DNA或者RNA链来编码信息，然后通过分管-合管操作来实现对问题的求解。特别指出的是文献[10]中使用RNA作为计算底物，其删除操作使用的是核糖核酸酶H，因为该酶的特性就是可以切割RNA的端，进而消化DNA/RNA双螺旋链，而单链结构不被破坏。 而2002年由L. Adleman等人提出的一种类似的DNA计算模型[11]在求解3-SAT问题时，由于反应底物使用的是DNA，其删除操作使用的是长度分离法。而二者的编码方法都是对变量及其非进行单独编码，生成变量组成的多重集作为初始试管。 2.4、表面模型 是将对应于问题解空间的单链DNA分子固定于一块经过特殊化学处理的固体表面如胶片、塑料、玻璃、硅半导体等，然后对表面上的DNA分子重复进行标记（mark）、破坏（destroy）、去标记（unmark）等操作，最终获得运算结果[12]。 特点： 固定于固体表面的单链分子为静态结构 操作过程可实现自动化 重复利用性 编码方式相对固定 表面模型的编码方式 2000年Wisconsin大学的L.Smith等在解决SAT问题时，其编码方式是使用DNA序列编码布尔变量的每一种可能的组合。 2001年清华大学的W u对其编码方式进行了改进[13]，其编码方式是对变项和变项的非分别进行编码。 对所有变项进行编码，相应的非编码为补链，结合荧光分析法测定纳米粒子标记物的技术[14] ，可以解决3-SAT问题 2.5、闭环DNA模型 其结构由若干个限制性内切酶的识别序列首尾相连而成的环状DNA分子的计算模型。 超螺旋形式的双链的闭环DNA分子计算模型 （包含质粒模型 ） 由线性DNA分子构成的闭环DNA计算模型 主要的生物