最小支撑树的DNA凝胶电泳算法

1、最小支撑树的 DNA 凝胶电泳算法最小支撑树的 DNAS胶电泳算法-权威资料本文档格式为 WORD,不是 word 文档,则说明不是原文档。最新最全的 学术论文 期刊文献 年终总结 年终报告 工作总结 个人总结 述 职报告 实习报告 单位总结摘要:DNA 计算是解决困难问题的一种很重要的方法。应用DNA 计算解决图论中的最小支撑树问题。利用 DNA 的热力学特性，根据边的权长不同，给它们设计不 同溶解温度的 DNA 链。根据温度的不同，电泳时 DNA 分子的形状不同，电泳的速度 也不同，从而根据电泳速度分离出最小支撑树的所有边。在这里给出了 5 个顶点的 赋权图为例来求它的最小支撑树，说明了该

2、方法的简便性。关键词:DNA 计算;温度梯度凝胶电泳；最小支撑树TP312 A 16727800(2013)0030058030 引言哈密顿路是图论中的一个 NP 完全问题， 1994 年， Adleman 博士首先提出了利 用 DNA解决此问题。先对有向图的哈密顿路问题进行编码，然后借助一系列的生物 操作，最后得到了图的哈密顿路。这一研究成果开辟了DNA 计算这一崭新的研究领域。 随后就有很多的专家学者对 DNA 计算进行了深刻的研究。 1995 年， Lipton 在 Adleman思想的启发下对 SAT 可满足性问题)进行了探讨。 Narayanan 和 Zorbalas 解决最短路径问

3、题，使用长度比例恒定的 DNA 计算技术，其中一个 DNA 链的编码长 度根据实际长度的距离不断提高。Lee 等人提出了解决 TSP 问题的温度梯度 DNA 计 算技术。2011 年宋勃升、殷志祥等利用 DNA 自组装成发夹结构解决可满足性问 题，在操作过程中只需要用到凝胶电泳操作，在一定程度上大大减少了因生物操作 过多而引起的各种实验误差。 2011年 Zoraida 等人提出了用温度梯度的 DNA 算法解决中国邮递员问题。文中 Zoraida 等人提出了 变性温度梯度 PCR(DTGPC 技术，温度梯度凝胶电泳(TGGE 技术和溶解温度(Tm)等 概念。变性温度梯度 PCR 技术，这是一种

4、改良的 PCR 技术，在这过程中分子的变性 温度是随着放大周期的变化而变化的，变性温度从 70?开始，然后每一个周期温度 升高 1?，直到温度升高到 95?，这个时候在其后的放大过程中温度将保持不变。其 它方面的放大的过程和PCR 技术一样。DNA 分子单链和其补链对 DNA 分子的解温 度的影响是一样的。溶解温度和分子中的 GC 含量有关，也会和其它的一些因素有 关，在这里仅考虑 GC 含量。对 DNA 分子的操作，既有物理的也有化学的，物理操作包括温度，酸碱度等。 传统的电泳分离方法基于分子的大小和带电荷数的多少，在这篇文章中会考虑温度 对分子构造间的范德华力的影响。 1999 年陈汉奎，

5、冯忻在温度梯度凝胶电泳技术 及应用的文章中给出了温度梯度凝胶电泳的分析原理(TGGE，在正常情况下，DNA分子呈双链结构状态；当温度升高到一定时，DNA 双链开始解开， 由完整的双链变 为分叉双链；如果温度继续升高，DNA 双链完全解开，变为 DNA 单链.这种分子结 构的改变会影响 DNA 分子在电泳时的迁移速度，因为 DNA 双链的打开直接导致迁移率下降 . 这种影响在两条链即将完全解开时最大， 此时分子的电泳速度最慢；而当全部形成单链时，电泳的速度又会变快，对于序列不同但长度相同的 DNA 链的溶解温度依赖于基本序列。所以 TGG 环仅能分离 DNA 分子，也给出了 DNA 分子的溶解性

6、和稳定性特点。本文就利用温度梯度凝胶电泳对DNA 分子进行电泳，从而解决一个 5 个顶点的赋权图的最小支撑树问题， 通过表面荧光技术得到图的最小 支撑树。1 最小支撑树1.1算法具体步骤1.2 DNA 算法编码与操作对应于上述最小支撑树的算法给出最小支撑树的DNA 算法。以图 1 为例，详细介绍温度梯度凝胶电泳的 DNA 计算方法。步骤 1:对图 G=(V, E)，对图 G 的任意顶点 vi，用长度为 20 的寡聚核苷酸片段 表示，记为 Vi 并且它们具有相同的溶解温度。然后利用Vi 构造探针记作 Ai。对图 G 的权，每一种权 wij 都有唯一的长为 20 的寡聚核苷酸片段与其对应，且权值

7、不同，它们的溶解温度也不同。权值小的，它们的DNA 链的溶解温度小，权值大的，它们的 DNA 链的溶解温度高。这里的溶解温度主要考虑其与GC 含量有关。然后将编码好的 DNA 链进行下列杂交从而得到每条边的 DNA 链。如任意的边 eij 它的 编码包含 3 个部分，第一部分是寡聚核苷酸片段 Vi 的碱基的补链所构成的寡聚核 苷酸片段 ;第二部分是 wij 的寡聚核苷酸片段 ; 第三部分是寡聚核苷酸片段 Vj 的碱 基的补链所构成的寡聚核苷酸片段。将编码好的每条边的DNA 链等量混合在一起，加入缓冲溶液，放入试管 T1 中。对图 1 的顶点及边权进行编码如表 1 所示。步骤 2: 从试管 T1

8、 中取出溶液进行温度梯度凝胶电泳，不同权长的边有不同的 DNAS码，有不同的 DNA 链溶解温度。权长越小，溶解温度越低，电泳的速度越 快。跑子最前的就是权长最小的边的 DNA 链，收集此 DNA 链。步骤 3: 对步骤 2 中的产物进行测序，可以把得到的产物固定到表面上，然后将 顶点Vi 的补链 i 分别标记上不同的颜色，加到表面上，然后通过激光共聚焦显微 镜观察表面上的 DNA 双链的颜色，就可以确定所得 DNA 链的碱基排序，找到了图的 最小边。不妨记这条边为 eij=vivj ，用 Ai ， Aj 作探针，将含有顶点 vi 和 vj 的边 eij 从试管中分离出来。然后再用 Ai 作探

9、针将含有顶点 vi 的边分离出来，对顶点 vj 作相同的操作，然后将它们放到新的试管中，加入缓冲溶液。步骤 4:如果 Vi=V(G)，则操作停止，将得到的边根据顶点连接起来就是所需的 最小支撑树。如果 ViV(G) ，转入步骤 2。对于图 1 来说将顶点 Vi 的补链 i 加上不同的荧光素，然后都加到表面上，再通过观察表面上的荧光颜色确定最短边的顶点，对于该例题来说是v1v2,记V1=v1, v2。再利用探针 A1, A2 将含顶点 v1 和 v2 的边从试管 T1 中分离出来， 然后分离利用 A1 和 A2 将试管 T1 中含顶点 v1 和 v2 的边， 如:v1v5;v1v4;v2v4;v

10、2v3 分离出来建立新的试管仍记作 T1，转入第二步.经过第二 次循环，找到 v1v5;v1v4;v2v4;v2v3 中最短的边是 v2v3，再经过三次循环后就可 以找到图 G 的最小支撑树 T。图 1 的最小支撑树见图 2。4 结语运用 DNA 分子的凝胶电泳受温度的影响，根据序列不同但长度相同的 DNA 链的溶解温度是依赖于基本序列的，图中的边权及两点间的距离用不同的温度代替设 计不同的 DNA 序列，距离不同，DNA 链的溶解温度不同，从而电泳的速度不同.对 图的顶点使其DNA 序列的溶解温度相同，然后通过温度梯度凝胶电泳得到图的最小 支撑树的各条边，最后利用表面荧光技术确定最短边的顶点

11、从而得到所求图的最小 支撑树。这种方法很好地克服了电子计算机在存储和速度方面的局限性，加快了反 应速度，并且易于操作。参考文献 :,1, LEONARD M， ADLEMAN. Molecular computation of solutions to combinatorialproblems,J,.Science， 1994(5187).,2, LIPTON R J. DNA Solution of hardcomputation problem,J,.Science， 1995(4).,3, AJIT NARAYANAN AND SPIRIDON ZORBALAS.DNA algorit

12、hms for computing shortest paths,C,.Proceedings ofGenetic Programming ， 1998.,4, JI YOUN LEE ， SOOYONG SH，IN TAI HYUN PARK AND BYOUNGTAKZHANG.Solving traveling salesmanproblem with DNA molecules encoding numerical values,J,.Biosystems ，2004(3).,5, B S E ZORAIDA. DNA algorithm employingtemperature gr

13、adient for chinese postman problem,J,.IEEE， 2011(4).,6, 宋勃升，殷志祥， 甄诚，等.DNA 自组装的可满足性问题模型，J,.小 型微型计算系统， 2011(32).,7, 陈汉奎，冯忻 . 温度梯度凝胶电泳技术及应用 ,J,. 生物化学与生物物 理进展，1999(3).,8, 殷志祥.图与组合优化中的 DNA 计算,M,.北京：科学出版社，2004.( 责任编辑 : 余 晓 )阅读相关文档：利用负载均衡实现服务交互和优化 软件事务存储系统设计选择 基于 CMM 模型的软件规模估计方法研究 春天身体干燥由内补水 变频多联空调系 统在建筑中的应用技术 多元智能理论对网络课程开发的启示 蔡同一 一辈子“向 科技进军” IT 展望与预测 ( 一) 管好家庭药箱 春天赏花胜服药 免疫细胞治疗不 适合晚期癌症病人 莫为貌似肿瘤的病担忧 远离癌症 要牢记 7 个“