最大匹配问题的三链dna计算模型

《最大匹配问题的三链dna计算模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最大匹配问题的三链DNA计算模型摘要：三螺旋结构的DNA链具有稳定性，在一定条件下易分解等特点，因此得到的三链模型具有错解率低的优点。利用三链模型来讨论最大匹配问题，拓展了DNA计算解决问题的方法和应用领域。关键词：DNA计算；三链DNA;最大匹配中图分类号：Q523:TP301文献标志码：A［WT］文章编号：1672-1098(2012)04-0047-03作者简介：杨静(1980-)，女，安徽濉溪人，讲师，在读博士，研究方向：DNA计算与组合优化。DNA计算是一种以DNA与相关某些生物酶等作为最基本材料的、基于某些生化反应原理的一种新型的

2、分子生物计算方法。DNA计算的优势是利用DNA分子具有海量的存储能力及生化反应的巨大并行性等特点进行计算。但DNA计算目前还在实验室阶段，研究的DNA计算模型还很不成熟。在已有的DNA计算模型中，大多数是应用于图与组合优化中的NP-完全问题［1-7］。建立DNA模型首先考虑的就是DNA分子结构，开发和研究新的分子结构也是目前研究的热点。目前常用的有单链的、双链的、单双链混合的、环状的、半环状的及三螺旋等结构的DNA分子结构。本文将用三链DNA计算模型解决最大匹配问题。1三链DNA1957年，文献［8］首次提出了三链核酸的概念，即在经典的W-C

3、双螺旋中含有多聚p票呤那条链，通过Hoogsteen或反Hoogsteen氢键与大沟中的第三条链结合，从而形成三螺旋结构即三链DNAO2004年，文献［9］发现寡聚脱氧核苷酸在RecA蛋白及ATPYS的存在下，与线性双螺旋DNA可形成稳定的三链结构。在形成的过程中，首先寡聚脱氧核苷酸在ATPYS的存在下与RecA蛋白结合，然后在目标双螺旋DNA上寻找同源序列，这一过程非常迅速并且不打开DNA双链。同源的双链找到后，寡聚脱氧核苷酸在RecA蛋白的介导下与目标双螺旋DNA形成三链DNA。经证实由RecA蛋白介导形成的三链DNA是相当稳定的［10］

4、。利用三链模型解决最大匹配问题，需要用到下面几种分子操作：①连接。将编码好的DNA链通过连接酶连接成一条DNA链；②复制。将DNA链利用PCR扩增技术进行复制；③内切。利用内切酶在指定位置进行切割；④提取测序。对凝胶电泳中得到的最长的DNA链进行提取测序，已得到所求解。这里所需要的生物操作技术都已经十分成熟，在生物实验上是可行的。2最大匹配问题2.1问题描述给定无向图G=（V，E），对边集E的任一子集ME,如果M中任意两条边在G中都没有公共端点，则称M是G的一个匹配。一般地，G的匹配不是惟一的。若G中没有另外的M'

5、^

6、M

7、,则称M为G的最大

8、匹配。如果M是G的最佳匹配，显然M是G的最大匹配；反过来不成立。但是G的最佳匹配也有可能不是惟一的（见图2），Ml={e2，e3，e7}、M2={e2,e6，e7}、M3={el,e4,e7}和M4={el，e6，e7}为该图的最大匹配，并且均是最佳匹配。2.2DNA算法步骤1:将图G的顶点和边进行编码，将所有边的编码两端加上限制性内切酶，然后把边所对应的寡聚核苷酸片段与连接酶一起加入缓冲液，在特定温度下使其连接成一条长链，根据W-C配对原则，在形成稳定的双链，把此时得到的结果进行提取、纯化、PCR扩增放在一试管中，作为最初的数据池TO。步骤

9、2:将TO分为两个试管Tl、T2。选取图G的一条边el（—般从el开始），检查与el相关联的边。将边el、e2的补链分别制作成探针Pl、P2。利用Pl将含有边el的链分离出来，切掉el从新连接起来，这时得到的T1试管不含有el。同理利用P2得到不含有边e2的试管T2。这时将得到的新的试管Tl、T2再混合一起作为试管TO。步骤3:检查是否有两边关于顶点关联，若有重复步骤1，直到任两边都没有顶点关联。这样得到的试管中就含有需要的解。步骤4:利用凝胶电泳技术测出最长的DNA片段（可能不止一条）读出其解，既是所求的最大匹配。2.3DNA编码步骤1:将

10、图G的顶点和边进行编码，顶点用含20个碱基对的DNA片段表示。边的编码可用20个碱基对的DNA片段表示，将所有边的编码两端加上限制性内切酶，然后把边所对应的寡聚核苷酸片段与连接酶一起加入缓冲液，在特定温度下使其连接成一条长链。加入聚合酶、引物，利用Watson-Crick互补原则，在3'端不断地扩增DNA分子，从而使所有单链DNA链都以双链的形式存在，以增加DNA链的稳定性。在反应后的产物中加入底物DNA分子，适量的引物G的顶点所对应的寡聚核苷酸片段的补链），DNA聚合酶及缓冲液进行PCR-扩增，对这些产物进行纯化，然后对于纯化后的产物进行分

11、离。把这些双链DNA作为最初的数据池T0。TO中含有DNA链｛el,e2，e3，e4，e5，e6,e7｝。步骤2:将TO分为两个试管Tl、T2。选取图G的一条边el