《DNA计算模型》PPT课件.ppt
《《DNA计算模型》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《DNA计算模型》PPT课件.ppt(28页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、DNA计算模型任晓玲2012年4月17日一、引言nDNA计算的原理DNA分子作为信息载体(A、C、G、T四种碱基)原始问题映射为DNA分子链数据运算映射为对DNA分子链的生物操作(高度并行)在分子生物实验室完成这一系列的分子生物操作运算载体运算工具:生化酶连接酶、核算内切酶、聚合酶等生化反应系统:退火、杂交、连接等检测系统:电泳技术(重量、极性);荧光技术1;纳米金粒子技术2(一次性检测出某个组合结合的构成情况)等一、引言nDNA计算的特点 1、高密度的存储量:1gDNA所能存储的信息量相当于10000亿张普通CD光盘;2、高度的并行性:DNA串的并行操作数可达1014;3、极低的能耗:DNA
2、计算的能耗仅仅相当于当前电子计算机的十亿分之一。二、DNA计算模型n对目前出现的DNA计算模型按照所使用的计算主体的分子形态进行较为系统的分类:2.1、双链DNA模型2.2、粘贴模型(单双链交替)2.3、单链DNA模型 RNA模型 发夹模型 2.4、表面模型2.5、闭环DNA模型2.6、三维DNA模型 2.1、双链DNA模型n双链DNA模型包括两种形式。一种是根据碱基互补配对原则使单链DNA分子杂交形成的双链模型,这一系列是指利Adleman-Liption的模型发展而来的计算模型,其核心的生物反应为杂交反应。n另一种是直接构造DNA双链分子,通过各种生物酶的催化来实现的双链模型,其核心的生物
3、反应为酶切反应和酶联反应。2.1、典型文章n第一类Junzo Watada及其合作者使用传统的双链模型解决了基于“距离”的数据聚类问题3,4。他们将距离进行预处理,使其可以通过DNA序列的长短进行表示,然后对数据和边进行编码,最终实现其自动聚类。n第二类文献5将双链模型与酶连锁反应(LCR)相结合,实现了对可满足性问题的求解。LCR所具有的漂亮的性质使我们可以通过控制引物来使那些只有满足条件的双链才能再次形成粘性末端并进行新一轮的链接实验,这种方式是逐个连接变量的一种较好的实验操作。2.2、粘贴模型n粘贴模型是一种由存储链(含有个由个碱基组成的不重叠的单链分子)和粘贴链(与存储链上个位置的某个
4、位置特定互补配对的个碱基构成的单链PNA或DNA分子构成6)构成的部分双链分子结构。n其信息(一般为布尔变量的形式)被编写在存储链上,输入一个初始试管,输出若干个最终试管。分离已退火的粘贴链可以分析存储复合物,从而读出最终试管的输出物,当然试管中也有可能不含任何存储复合物。文献7中所使用的是一种原始的Adleman-Liption模型和粘贴模型相结合的混合模型(Hybird-model),就是仍然使用Adleman的编码方式来编码信息,使用粘贴链序列来特定的表示二进制的数据,从而将这两部分混合地编到统一DNA分子链上,根据实际问题的需要进行运算。于是将双链DNA模型中的Adleman-Lipt
5、ion模型和粘贴模型相结合,可以有丰富的生物操作。具体总结如下:2.3、单链DNA模型 n单链DNA模型是指使用单链DNA或者RNA为载体的计算模型。根据其所形成的单链分子的形态具体的分为发夹结构和线性(存储)结构。发夹结构n“发夹”是单链核酸分子(DNA 或RAN)中由于局部互补杂交而形成的一种空间茎环结构,因其形似发夹而得名。其结构如图所示 文献8使用左图发夹模型解决了3-SAT问题 帽子(cap)结构的发夹,文献9使用右图这种结构作为辅助结构解决了3-SAT问题链状结构n另外一种线性存储模型是使用单链DNA或者RNA链来编码信息,然后通过分管-合管操作来实现对问题的求解。特别指出的是文献
6、10中使用RNA作为计算底物,其删除操作使用的是核糖核酸酶H,因为该酶的特性就是可以切割RNA的端,进而消化DNA/RNA双螺旋链,而单链结构不被破坏。n而2002年由L.Adleman等人提出的一种类似的DNA计算模型11在求解3-SAT问题时,由于反应底物使用的是DNA,其删除操作使用的是长度分离法。而二者的编码方法都是对变量及其非进行单独编码,生成变量组成的多重集作为初始试管。2.4、表面模型n是将对应于问题解空间的单链DNA分子固定于一块经过特殊化学处理的固体表面如胶片、塑料、玻璃、硅半导体等,然后对表面上的DNA分子重复进行标记(mark)、破坏(destroy)、去标记(unmar
7、k)等操作,最终获得运算结果12。n特点:固定于固体表面的单链分子为静态结构操作过程可实现自动化重复利用性编码方式相对固定表面模型的编码方式n2000年Wisconsin大学的L.Smith等在解决SAT问题时,其编码方式是使用DNA序列编码布尔变量的每一种可能的组合。n2001年清华大学的W u对其编码方式进行了改进13,其编码方式是对变项和变项的非分别进行编码。n对所有变项进行编码,相应的非编码为补链,结合荧光分析法测定纳米粒子标记物的技术14,可以解决3-SAT问题2.5、闭环DNA模型 n其结构由若干个限制性内切酶的识别序列首尾相连而成的环状DNA分子的计算模型。n超螺旋形式的双链的闭
8、环DNA分子计算模型(包含质粒模型)由线性DNA分子构成的闭环DNA计算模型 n主要的生物实验为酶切和酶连实验闭环模型的编码方式n单纯的0-1组合优化问题:使用的双链模型是由不同的限制性内切酶的识别位点的回文序列构成的,每个这样的识别序列记为station,从而可以在station上进行接入和删除操作。n带有其他附加信息:将附加信息编码添加入station中。一般,附加信息为长度变量。n针对单酶切实验在后在进行连接时容易出现的自身环化现象,文献15给出了双酶切实验的解决方案。n闭环DNA作为一种形式:编码方式类似于Adleman模型。文献16中采用闭环DNA进行网格聚类,由于推导过程中说明了哈
9、密顿回路的存在,所以符合要求的片段自然会形成闭环DNA的形式。单链闭环DNA结构n单链闭环DNA分子存在于雄性大肠杆菌的噬菌体中,周康及其合作者在2006年根据17中指出的用若干识别位点可以将线性DNA 首尾相连形成闭环DN A的操作,使用单链闭环DNA模型求解了边着色的问题18。n单链的形式类似于粘贴模型的形式,不同的是它的构成完全通过识别序列按顺序链接而形成,通过这种特殊的环状结构,作者引入了“批删除”实验。在给出的条件序列中,只要有两个条件被满足(即与单链闭环上的相应部分杂交),通过放入条件序列的内切酶就可以实现对闭环的删除。由于其不同的酶切割了不同的双链位点,故不用担心自环现象出现。2
10、.6、三维DNA模型n三维DNA模型19是以k-臂DNA分子为其基本运算对象,其优势是能够直接用 k-臂DNA 分子构造图的结构,从而利用三维DNA模型的运算直接完成对图的各种处理。其2-arm、3-arm、4-arm结构如图所示三维DNA模型的编码方式nK-arm结构双链部分编码顶点信息,延伸的粘性末端部分编码边的信息,同一条边对应的两个粘性末端编码序列互补。n使用2-arm的结构编码边的信息,两端粘性末端编码序列与顶点臂的粘性末端互补。这样编码的好处在于简化了k-arm分子构造的难度,方便携带附加信息三、DNA计算模型的新发展nDNA计算传统的方法是基于产生大量的候选解,这些方法所需初始数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DNA计算模型 DNA 计算 模型 PPT 课件
限制150内