《DNA计算模型》PPT课件.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）构成的部分双链分子结构。 其信息（一般为布尔变量的形式）被编写在存储链上，输入一个初始试管，输出若干个最终试管。分离已退火的粘贴链可以分析存储复合物，从而读出最终试管的输出物，当然试管中也有可能不含任何存储复合物。,文献7中所使用的是一种原始的Adleman-Liption模型和粘贴模型相结合的混合模型（Hybird-model），就是仍然使用Adleman的编码方式来编码信息，使用粘贴链序列来特定的表示二进制的数据，从而将这两部分混合地编到统一DNA分子链上，根据实际问题的需要进行运算。 于是将双链DNA模型中的Adleman-Liption模型和粘贴模型相结合，可以有丰富的生物操作。具体总结如下：,2.3、单链DNA模型,单链DNA模型是指使用单链DNA或者RNA为载体的计算模型。根据其所形成的单链分子的形态具体的分为发夹结构和线性（存储）结构。,发夹结构,“发夹”是单链核酸分子(DNA 或RAN )中由于局部互补杂交而形成的一种空间茎环结构，因其形似发夹而得名。其结构如图所示,文献8使用左图发夹模型解决了3-SAT问题,帽子（cap）结构的发夹，文献9使用右图这种结构作为辅助结构解决了3-SAT问题,链状结构,另外一种线性存储模型是使用单链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计算模型 主要的生物实验为酶切和酶连实验,闭环模型的编码方式,单纯的0-1组合优化问题：使用的双链模型是由不同的限制性内切酶的识别位点的回文序列构成的，每个这样的识别序列记为station，从而可以在station上进行接入和删除操作。 带有其他附加信息：将附加信息编码添加入station中。一般，附加信息为长度变量。 针对单酶切实验在后在进行连接时容易出现的自身环化现象，文献15给出了双酶切实验的解决方案。 闭环DNA作为一种形式：编码方式类似于Adleman模型。文献16中采用闭环DNA进行网格聚类，由于推导过程中说明了哈密顿回路的存在，所以符合要求的片段自然会形成闭环DNA的形式。,单链闭环DNA结构,单链闭环DNA分子存在于雄性大肠杆菌的噬菌体中，周康及其合作者在2006年根据17中指出的用若干识别位点可以将线性DNA 首尾相连形成闭环DN A的操作，使用单链闭环DNA模型求解了边着色的问题18。 单链的形式类似于粘贴模型的形式，不同的是它的构成完全通过识别序列按顺序链接而形成，通过这种特殊的环状结构，作者引入了“批删除”实验。在给出的条件序列中，只要有两个条件被满足（即与单链闭环上的相应部分杂交），通过放入条件序列的内切酶就可以实现对闭环的删除。由于其不同的酶切割了不同的双链位点，故不用担心自环现象出现。,2.6、三维DNA模型,三维DNA模型19是以k-臂DNA分子为其基本运算对象，其优势是能够直接用 k-臂DNA 分子构造图的结构，从而利用三维DNA模型的运算直接完成对图的各种处理。其2-arm、3-arm、4-arm结构如图所示,三维DNA模型的编码方式,K-arm结构双链部分编码顶点信息，延伸的粘性末端部分编码边的信息，同一条边对应的两个粘性末端编码序列互补。 使用2-arm的结构编码边的信息，两端粘性末端编码序列与顶点臂的粘性末端互补。这样编码的好处在于简化了k-arm分子构造的难度，方便携带附加信息,三、DNA计算模型的新发展,DNA计算传统的方法是基于产生大量的候选解，这些方法所需初始数据池的规模随着变量数量的增长而呈指数型增长，这就是所谓的“解空间指数爆炸问题”，从而使DNA计算的能力受到限制。另外，Fu在文献20中指出，对于生物计算来讲，生物大分子的长度会造成计算方法是缺乏空间效率的，以及还要考虑DNA计算模型的容错能力。 于是我们看到，现在的DNA计算，甚至是生物计算发展的一个方向就是改进计算方法，缩减候选解集的规模，改进编码方式使其能以更短的长度解决问题，这还有赖于分子生物学技术的进步。,改进模型,DNA进化算法 case1 使用进化算法产生每一代的种群，使用DNA实验检验其适应度的变化情况。 改进DNA计算，减少数据池中的分子量 case2 用计算机完全模拟DNA遗传、进化中的行为。 改进进化计算，使其能实现有机体在优化过程中的高效率、准确性,DNA进化计算的优点,其与传统的DNA计算方法相比，一方面避免了初始解空间指数爆炸的问题；另一方面对于不完善的DNA生化反应导致的错误，可视为一种变异，其有更好的容错能力。 其与传统的进化算法相比，一方面DNA进化算法的可以实现更大的群体规模；另一方面随着群体规模的增大，DNA计算的并行性不会导致搜索时间的增加。,DNA蛋白质算法 这种方法使用质粒进行运算，将DNA计算与其相应的蛋白质表达相结合。研究表明，通过在质粒上设置开放读取框架(ORF)，我们正在将质粒计算模型与蛋白质表达相结合进行运算。 开放读取框架如图所示：,DNA蛋白质计算的优点,将其转化为蛋白质序列的优点在于三个碱基序列对应一种蛋白质，因此蛋白质序列其信息密度更大，分子更小，从而可以使用质谱分析法对蛋白质序列进行检测。,参考文献,1张成, 杨静, 王淑栋. DNA计算中荧光技术的应用及其发展J.计算机学报, 2009, 32(12):2300-2310. 2孙伟, 尤加宇, 江宏, 等. 纳米粒子标记 DNA 探针的制备与检测应用J. 中国卫生检验杂志, 2005, 15( 8): 1008. 3 Rohani Binti Abu Bakar,Junzo Watada, Witold Pedrycz. DNA approach to solve clustering problem based on a mutual orderJ. BioSystems. 2008, 91: 1-12. 4 Rohani Binti Abu Bakar,Junzo Watada, A Biologically Inspired Computing Approach to Solve Cluster-Based Determination of Logistic ProblemJ. Biomedical Soft Computing and Human Sciences, 2008, 13(2): 59-66. 5 Xiaolong Wang, Zhenmin Bao, Jingjie Hu, Shi Wang, Aibin Zhan. Solving the SAT problem using a DNA computing algorithm based on ligase chain reactionJ. BioSystems. 2008, 91: 117125. 6 Sam Roweis. Eric Winfree, Richard Burgoyng. Nickolas, V. Chelyapov, Myron, F.Goodman. Paul W.K. Rothemund, and Leonard M. A dleman. A Sticker-Based Model for DNA ComputationJ. Computational Biology, 1998(5): 615-629. 7 Carlos Alberto Alonso Sanches , Nei Yoshihiro Soma. A polynomial-time DNA computing solution for the Bin-Packing ProblemJ. Applied Mathematics and Computation. 2009, 215: 20552062. 8 Sakamato K,Gouzu H,Kiga D, Yokoyama S, Yokomori T, Hagiya M.Molecular computation by DNA hairpin formationJ. Science 288:1223-1226.,参考文献,9 Jonoska N, Stephen. A K, Saito M. Three dimensional DNA structure in computingJ. Biosystems. 1999, 52: 143-153. 10 Dirk F，Cukras A R，Lipton R J，et al.Molecular computation：RNA solutions to chess problemJ.Biochemistry， 2000， 97(4)：1385-1389. 11 Braich RS, Chelyapov N, Johnson C, Rothemumd PWK, Adleman L.Solution of a 20-variable 3 -SAT problem on a DNA Computer J.Science. 2002, 296: 499-502. 12 Frutos G. Enzymatic ligation reactions of DNA “wo rds“ on surfaces for DNA ComputingJ . J. Am. Chem. Soc. 120, 1998:10277-10282 13 Wu Haoyang. An improved surface-based method for DNA computationJ. Boisystems. 2001, 59: 1-5. 14 孙伟, 尤加宇, 江宏, 等. 纳米粒子标记 DNA 探针的制备与检测应用J. 中国卫生检验