《DNA计算模型》PPT课件

《《DNA计算模型》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DNA计算模型任晓玲2012年4月17日一、引言DNA计算的原理DNA分子作为信息载体（A、C、G、T四种碱基）原始问题映射为DNA分子链数据运算映射为对DNA分子链的生物操作（高度并行）在分子生物实验室完成这一系列的分子生物操作运算载体运算工具：生化酶——连接酶、核算内切酶、聚合酶等生化反应系统：退火、杂交、连接等检测系统：电泳技术（重量、极性）；荧光技术[1]；纳米金粒子技术[2]（一次性检测出某个组合结合的构成情况）等一、引言DNA计算的特点1、高密度的存储量：1gDNA所能存储的信息量相当于10000亿张普通CD光盘；2、高度的并

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的模型发展而来的计算模型，其核心

3、的生物反应为杂交反应。另一种是直接构造DNA双链分子，通过各种生物酶的催化来实现的双链模型，其核心的生物反应为酶切反应和酶联反应。2.1、典型文章第一类JunzoWatada及其合作者使用传统的双链模型解决了基于“距离”的数据聚类问题[3,4]。他们将距离进行预处理，使其可以通过DNA序列的长短进行表示，然后对数据和边进行编码，最终实现其自动聚类。第二类文献[5]将双链模型与酶连锁反应（LCR）相结合，实现了对可满足性问题的求解。LCR所具有的漂亮的性质使我们可以通过控制引物来使那些只有满足条件的双链才能再次形成粘性末端并进行新一轮的链接

4、实验，这种方式是逐个连接变量的一种较好的实验操作。2.2、粘贴模型粘贴模型是一种由存储链（含有个由个碱基组成的不重叠的单链分子）和粘贴链（与存储链上个位置的某个位置特定互补配对的个碱基构成的单链PNA或DNA分子构成[6]）构成的部分双链分子结构。其信息（一般为布尔变量的形式）被编写在存储链上，输入一个初始试管，输出若干个最终试管。分离已退火的粘贴链可以分析存储复合物，从而读出最终试管的输出物，当然试管中也有可能不含任何存储复合物。文献[7]中所使用的是一种原始的Adleman-Liption模型和粘贴模型相结合的混合模型（Hybird-

5、model），就是仍然使用Adleman的编码方式来编码信息，使用粘贴链序列来特定的表示二进制的数据，从而将这两部分混合地编到统一DNA分子链上，根据实际问题的需要进行运算。于是将双链DNA模型中的Adleman-Liption模型和粘贴模型相结合，可以有丰富的生物操作。具体总结如下：2.3、单链DNA模型单链DNA模型是指使用单链DNA或者RNA为载体的计算模型。根据其所形成的单链分子的形态具体的分为发夹结构和线性（存储）结构。发夹结构“发夹”是单链核酸分子(DNA或RAN)中由于局部互补杂交而形成的一种空间茎环结构，因其形似发夹而得名

6、。其结构如图所示文献[8]使用左图发夹模型解决了3-SAT问题帽子（cap）结构的发夹，文献[9]使用右图这种结构作为辅助结构解决了3-SAT问题链状结构另外一种线性存储模型是使用单链DNA或者RNA链来编码信息，然后通过分管-合管操作来实现对问题的求解。特别指出的是文献[10]中使用RNA作为计算底物，其删除操作使用的是核糖核酸酶H，因为该酶的特性就是可以切割RNA的端，进而消化DNA/RNA双螺旋链，而单链结构不被破坏。而2002年由L.Adleman等人提出的一种类似的DNA计算模型[11]在求解3-SAT问题时，由于反应底物使用的

7、是DNA，其删除操作使用的是长度分离法。而二者的编码方法都是对变量及其非进行单独编码，生成变量组成的多重集作为初始试管。2.4、表面模型是将对应于问题解空间的单链DNA分子固定于一块经过特殊化学处理的固体表面如胶片、塑料、玻璃、硅半导体等，然后对表面上的DNA分子重复进行标记（mark）、破坏（destroy）、去标记（unmark）等操作，最终获得运算结果[12]。特点：固定于固体表面的单链分子为静态结构操作过程可实现自动化重复利用性编码方式相对固定表面模型的编码方式2000年Wisconsin大学的L.Smith等在解决SAT问题时，

8、其编码方式是使用DNA序列编码布尔变量的每一种可能的组合。2001年清华大学的Wu对其编码方式进行了改进[13]，其编码方式是对变项和变项的非分别进行编码。对所有变项进行编码，相应的非编码为补