第 32 2012 卷 第 年 月 12 4 期 安徽理工大学学报( 自然科学版) ( Journal of Anhui University of Science and Technology Natural Science ) Vol． 32 No． 4 Dec． 2012 最大匹配问题的三链 DNA 计算模型 杨 静1，2，殷志祥1，陈明强3，黄凯峰4 安徽理工大学理学院，安徽 淮南 ( 1． 化学工程学院，安徽 淮南 232001 ; 4． ; 安徽理工大学地球与环境学院，安徽 淮南 2． 232001 淮南职业技术学院信电系，安徽 淮南 ) 232001 232001 ; 3． 安徽理工大学 摘 要: 三螺旋结构的 DNA 链具有稳定性，在一定条件下易分解等特点，因此得到的三链模型 具有错解率低的优点。利用三链模型来讨论最大匹配问题，拓展了 DNA 计算解决问题的方法 和应用领域。 关键词: DNA 中图分类号: Q523∶ TP301 计算; 三链 DNA ; 最大匹配 文献标志码: A 文章编号: 1672 － 1098 ( ) 2012 04 － 0047 － 03 Triple － stranded DNA Computing Model of Maximum Matching Problem YANG Jing1 HUANG Kai － feng4 ， ， China 1． School of Science CHEN Ming － qiang3， YIN Zhi － xiang1， Anhui University of Science and Technology Huainan Anhui 232001 2， ， ， 2． School of Earth ang Envi- ; ( ronment ， Anhui University of Science and Technology ， Huainan Anhui 232001 ， China ; 3． School of Chemical Engineering ， University of Science and Technology ， Huainan Anhui 232001 ， 4． Department of Information and Electrical Engineering Anhui ， ; China ， China ， ) ， Huainan Vocational and Technical College Huainan Anhui 232001 ， : Abstract Triple － stranded DNA has the features of stability and under certain conditions can be easily decom- posed． Triple － stranded DNA model has advantages of low rate of wrong solutions． The triple － stranded DNA model was used to discuss the maximum matching problem which expands method for solving the problem and application field of DNA computation． Key words DNA computing ; triple － stranded DNA ; maximum matching : 但 DNA DNA DNA DNA 。DNA 计算是一种以 与相关某些生物酶 基于某些生化反应原理的一 、 计算的优势是 分子具有海量的存储能力及生化反应的 计算目前还 。 计算模型还很不成熟 。 计算模型中，大多数是应用于图与 模 分子结构，开发和研究新 目前常用的有 半环状的 、 本文将用三链 等作为最基本材料的 种新型的分子生物计算方法 利用 巨大并行性等特点进行计算 在实验室阶段，研究的 在已有的 DNA 组合优化中的 NP － 型首先考虑的就是 的分子结构也是目前研究的热点 单链的 单双链混合的 、 及三螺旋等结构的 。 环状的 、 分子结构 计算模型解决最大匹配问题 双链的 、 完全问题［ 建立 DNA DNA DNA DNA 。 。 ］ 1 － 7 DNA 。 三链 DNA 1 DNA。2004 蛋白及 1957 W － C 年，文献［ ］首次提出了三链核酸的概 8 念，即在经典的 双螺旋中含有多聚嘌呤那条 链，通过 氢键与大沟中 的第 三 条 链 结 合，从 而 形 成 三 螺 旋 结 构 即 三 链 年，文献［ ］发现寡聚脱氧核苷酸在 9 Hoogsteen Hoogsteen 或反 的存在下，与线性双螺旋 ATPγS RecA 可形成稳定的三链结构 聚脱氧核苷酸在 合，然后在目标双螺旋 过程非常迅速并且不打开 找到后，寡聚脱氧核苷酸在 DNA 在形成的过程中，首先寡 。 的存在下与 蛋白结 上寻找同源序列，这一 同源的双链 蛋白的介导下与 ATPγS 双链 RecA DNA DNA 。 RecA 收稿日期: 2012 － 10 － 15 作者简介: 杨静( 1980 － ) ，女，安徽濉溪人，讲师，在读博士，研究方向: DNA 计算与组合优化 。 中国煤炭期刊网 www.chinacaj.net

84 安徽理工大学学报( 自然科学版) 第 32 卷 目标双螺旋 蛋白介导形成的三链 DNA 形成三链 DNA。 是相当稳定的［ 经证实由 ］ 10 DNA RecA 。 。 ① DNA 连接 利用三链模型解决最大匹配问题，需要用到下 链通 面几种分子操作: 过连接酶连接成一条 链利用 切酶在指定位置进行切割; 电泳中得到的最长的 到所求解 分成熟，在生物实验上是可行的 将编码好的 链; 复制 扩增技术进行复制; 内切 提取测序 DNA 将 DNA 利用内 对凝胶 ④ 链进行提取测序，已得 这里所需要的生物操作技术都已经十 DNA PCR 。 ② 。 ③ 。 。 。 图 1 三链中第三条链的形成 最大匹配问题 2 2. 1 问题描述 给定无向图 ( ， E V G = M  E 点，则称 惟一的 ，如果 是 M 若 。 G M 中任意两条边在 的一个匹配 G 中没有另外的 G 的最大匹配 的最大匹配; 反过来不成立 如果 。 G 也有可能不是惟一的( 见图 是 M G G E ) ，对边集 一般地， 。 G 的任一子集 中都没有公共端 的匹配不是 ，则称 为 | M' | ≥| M | 的最佳匹配，显然 是 的最佳匹配 { 但是 M M G { e2 M4 = } 为该图的最大匹配，并且均是最佳匹配 M1 = } 和 2 ， e4 、M3 = ， e6 ， e7 e2 e1 } { 。 ) ， ， e7 、 ， ， e3 { } ， e7 ， e6 e1 。 M2 = e7 定温度下使其连接成一条长链，根据 配对原 则，在形成稳定的双链，把此时得到的结果进行提 扩增放在一试管中，作为最初的数 取 纯化 、 据池 W － C 、PCR T0 。 步骤 2: 将 分为两个试管 T0 ( 一般从 开始) ，检查与 的补链分别制作成探针 e1 T1 、T2 。 选取图 的 相关联的边 G 。 利用 e1 P1 、P2 。 P1 从新连接起来， 得到不 P2 T1 、T2 一条边 e1 将边 e1 、e2 将含有边 e1 这时得到的 含有边 T2 。 再混合一起作为试管 的试管 T1 e2 的链分离出来，切掉 e1 试管不含有 同理利用 e1 。 这时将得到的新的试管 T0 。 步骤 3: 检查是否有两边关于顶点关联，若有 这样得 ，直到任两边都没有顶点关联 重复步骤 到的试管中就含有需要的解 1 。 步骤 4: 利用凝胶电泳技术测出最长的 DNA 片段( 可能不止一条) 读出其解，既是所求的最大 匹配 。 。 2. 3 DNA 编码 步骤 1: 将图 个碱基对的 含 G 。 。 DNA DNA 片段表示 20 个碱基对的 的顶点和边进行编码，顶点用 边的编码可用 片段表示，将所有边的编码两 20 端加上限制性内切酶，然后把边所对应的寡聚核苷 酸片段与连接酶一起加入缓冲液，在特定温度下使 其连接成一条长链 加入聚合酶 互补原则，在 端不断地扩增 DNA 链的稳定性 son － Crick 子，从而使所有单链 以增加 底物 的寡聚核苷酸片段的补链) ， 进行 纯化后的产物进行分离 初的数据池 Wat- 分 3' 链都以双链的形式存在， 在反应后的产物中加入 的顶点所对应 G 聚合酶及缓冲液 扩增，对这些产物进行纯化，然后对于 作为最 ， ， e4 分子，适量的引物( 图 DNA ， ， e2 e3 。 中含有 把这些双链 引物，利用 、 PCR － T0 。T0 ， e5 DNA DNA DNA DNA DNA 链{ 。 e1 } ， e7 e6 。 图 2 无向图 G 与其最大匹配 M1 、M2 、M3 、M4 : : : : : : : e1 e2 e3 e4 e5 e6 e7 ATGCCTCATACGGCTTTCAG GGCTTATGCAAAGCTTTCTA CCATATAGCTAACCTGCTAG TTGACTCTAGAATTCTCGAT GTAGACTAGCTAGGTTTCTA GATCTAGCTTACTAGTCCCC AAAATTGCCTTGCATATACA 3 图 边的编码 分为两个试管 2. 2 DNA 算法 步骤 1: 将图 的顶点和边进行编码，将所有 边的编码两端加上限制性内切酶，然后把边所对应 的寡聚核苷酸片段与连接酶一起加入缓冲液，在特 G 步骤 2: 将 T0 ( 一般从 关联，将边 一条边 点 v1 e1 e1 e1 、e2 选取图 T1 、T2 。 与 的 关于顶 G 开始) ，检测到 的补链分别制作成探针 e2 e1 P1 、 中国煤炭期刊网 www.chinacaj.net

第 4 期 杨 静，等: 最大匹配问题的三链 计算模型 DNA 94 A e1 e1 DNA DNA P1 。 ATPγS 在表示 Hoogsteen 端添加一个聚酯纤维 链作为模板构造探针 结合生成三螺旋结构的 的寡聚核苷酸片段的补链 单链和抗原蛋白质在含有 DNA ，在标记上生物素 配对原则，这个探针将与含有 单链 P2 。 使 的 。 5' 这些 溶液 混合，在一定条件下生成核蛋白细状体，把这些核 蛋白细状体的 将 第一个探针混合到数据池中，在一定条件下根据 的双链 ，再利用生物操 除 边的编码从链上连同 加热解链，冲洗掉补链，得到的探 ， 利用同样的方法可以得到不含有 ，将两个试管混合作 ， DNA 作中的分离操作将没有生成三链的双链 去 探针一起切除 针可以再用 还作为试管 T1 。 链，作为试管 的 边 为试管 这时 T0 ， ， ， e4 e7 e3 步骤 3: 检测图 G 试管中含有 ， e5 中是否还有边关联，若有，重 必将含有所需 利用内切酶的作用将 。 这时得到的 链不再含有边 T0 。 } 和{ ， e6 ， e7 ， e3 ， e6 ， e4 DNA DNA DNA DNA DNA 链{ 复上述步骤，得到最终的试管 的解 T0 。 。 。 。 T2 e1 e1 e1 e5 e2 e2 } PCR 扩增和纯化后，提取这些链 。 步骤 4: 利用凝胶电泳技术测出最长的 。 DNA 采用非 测序的方法，进行测序，可得到最 链的碱基排序，也即知道了图的最大匹 { ， DNA { } { ， e6 ， e7 e2 、M3 = e1 e2 ， ， e7 e3 { e1 } 、M2 = ， } e6 ， e7 。 M4 = 片段，用 放射性标记 长的 配， M1 = ， } 和 e7 DNA e4 结论 3 DNA DNA DNA 链，而双链 利用三链模型来解决最大匹配问题相对其他 模型计算时错解率要低一些，因为生成数据池时， 存在的都是双螺旋结构的 的 的稳定性强，在数据池中就不 稳定性较单链 结构，从而 会出现由于编码问题而出现的 ” 使生物化学反应更为充分，效率更高 而对于三链 的分离较容易些 DNA 。 当然对于实际问题的求解，还存在着一些生物技术 另外，此模型的复杂度 上的问题，需进一步研究 条边的无 与顶点的度有关 作为有 个顶点和 向图，利用三链模型计算它的最大匹配 根据模型 分析，编码及生物操作的复杂度仅随顶点和边的增 的分离也相对双链 发夹 DNA “ 。 。 。 。 m n ) O 。 DNA 加而增加，且呈线性关系 ( 模型中由于需要 n 片段切除，可能 利用内切酶把某条边对应的 会因为生物技术或是问题规模的扩大，而产生伪解 随着生物技术的发展，这些问题会得到解 或错解 目前，在理论上用三链模型已经解决了不少问 决 题，更加体现了这种模型得优点 随着分子生物学 技术的发展，这种 计算模型的生物操作将会 得以更好的实现，模型的通用性将进一步提升 DNA 。 。 。 。 参考文献: ［ ］ 1 ［ ］ 2 ［ ］ 3 ［ ］ 4 ［ ］ 5 ， ， 403 2000 GAO LIN LIU QINGHUA ， LIMAN WANG ， TOS et al． DNA computing on surfaces ANTHONY G FRU- ， ［ ］ J ． Nature 13 ) : ( ， XU JIN． DNA solution of vertex cover prob- 175 － 178． lem based on sticker model ． Chinese Joumal of Elec- ［ ］ J tronics ， 2002 ， 11 ( 2 ) : 280 － 284． KARL HEINZ ZIMMERMANN． Efficient DNA sticker algorithms for NP complete graph problems ． Com- puter Physics Communications ， 2002 ， 144 : ［ ］ J 297 － 309． ， ， BRAICH R S CHELYAPOV N JOHNSON et al． Solu- tion of a 20 － varaiable3 － SAT problem on a DNA com- ［ ］ J puter ， 2002 ． Science ， TAMAR P : ， 296 ， ADAR R 499 － 502． ， et al． Programma- BENENSON Y ble and autonomous computing machine made of bio- 430 － 434． 22 计算机模型( ) : 理 I ， 414 ( ) : ［ ］ J moleccules ． Nature ［ ］ 许进，董亚非，魏小鹏 6 ， 2001 粘贴 ， ( 49 ］ 许 进，李 三 平，董 亚 非，等 ［ 7 ． 科学通报， 科学通报， 论［ ］ ． J 2004 ) : 应用［ ］ J ． ( ． Ⅱ DNA ) : 粘 贴 ， 49 2004 DNA ( ) : 4 3 205 － 212． S TYAGI ， F R KRAMER． Molecular beacon : fluoresce upon hybridization ． Nat Biotechnol ［ ］ J 计 算 机 模 型 299 － 307． probes that ， ， 1996 ［ ］ 8 ［ ］ 9 : 14 303 － 308． SHIGEMORI Y ， OISHI M． Specific cleavage of DNA molecules at RecA － mediated triple － stranded struc- ［ ］ J ture ． Nucleic Acids Research 2004 32 15 ， ， ( ) : 4 563 － 4 575． ［ ］ 10 RAO B J ， DUTREIX M ， RADDING C M． Stable three － stranded DNA made by RecA protein ． ProNatl Acad Sci USA ， 1991 ， 88 ( 8 ) : 2 984 － 2 988． ［ ］ J ( 责任编辑: 何学华，吴晓红) 中国煤炭期刊网 www.chinacaj.net