最小生成树DNA算法

第４０卷　第１期 ２０１２年　１月　 华 中 科 技 大 学 学 报 （自 然 科 学 版） Ｊ．Ｈｕａｚｈｏｎｇ　Ｕｎｉｖ．ｏｆ　Ｓｃｉ．＆Ｔｅｃｈ．（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ） Ｖｏｌ．４０Ｎｏ．１ 　Ｊａｎ．　２０１２ 收稿日期　２０１１－０３－２２． 作者简介　周　康（１９６５－），男，教授，Ｅ－ｍａｉｌ：ｚｈｏｕｋａｎｇ－ｗｈ＠ｙａｈｏｏ．ｃｏｍ．ｃｎ． 基金项目　国家自然科学基金资助项目 （６１１７９０３２）；湖北省自然科学基金资助项目 （２０１１ＣＤＢ２２９）；湖北省教育 科学“十一五”规划资助项目 （２０１０Ｂ２９０，２００９Ｂ２１７）；湖北省教育厅科学技术研究（重点）项目 （Ｄ２０１１１７０２）；湖北省建设厅建设科技计划资助项目（２０１１－２９）． 最小生成树ＤＮＡ算法 周　康　李　刚　谢振林　徐　伟 （武汉工业学院数学与计算机学院，湖北 武汉４３００２３） 摘要　为了改进粘贴模型，提出了用生化实验实现求解割集的计算方法，并基于该方法给出了最小生成树 ＤＮＡ算法．首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验，所提出的最小生成树 ＤＮＡ算法打破了ＤＮＡ计算的计算模式———用求解割集的最小边的方法逐步产生最小生成树．用该方法求 解割集利用了分离实验运算的高度并行性，最小生成树ＤＮＡ算法的时间复杂度是线性的，从而降低了算法 的时间复杂度． 关键词　粘贴模型；ＤＮＡ算法；最小生成树问题；分离实验；割集 中图分类号　ＴＰ３０１．６　　文献标志码　Ａ　　文章编号　１６７１－４５１２（２０１２）０１－００３０－０５ ＤＮＡ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｍｉｎｉｍａｌ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｐｒｏｂｌｅｍ Ｚｈｏｕ　Ｋａｎｇ　Ｌｉ　Ｇａｎｇ　Ｘｉｅ　Ｚｈｅｎｌｉｎ　Ｘｕ　Ｗｅｉ （Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ，Ｗｕｈａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００２３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　Ｓｔｉｃｋｅｒ　ｍｏｄｅｌ　ｗａｓ　ｉｍｐｒｏｖｅｄ，ｃａｌｃｕｌａｔｉｏｎ　ｍｅｔｈｏｄｓ　ｏｆ　ｃｕｔ　ｓｅｔ　ｕｓｉｎｇ　ｂｉｏｃｈｅｍｉｓｔｒｙ　ｅｘｐｅｒｉｍｅｎｔ ｗａｓ　ｆｏｕｎｄ，ａｎｄ　ＤＮＡ （ｄｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃ　ａｃｉｄ）ａｌｇｏｒｉｔｈｍ　ｏｆ　ｍｉｎｉｍａｌ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｐｒｏｂｌｅｍ　ｂａｓｅｄ　ｏｎ ｔｈｅ　ｍｅｔｈｏｄｓ　ｗａｓ　ｐｕｔ　ｆｏｒｗａｒｄ．Ｓｅｐａｒａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ　ｗａｓ　ｆｉｒｓｔ　ｅｘｔｅｎｄｅｄ，ｗｈｉｃｈ　ｃｏｎｔａｉｎｅｄ　ｓｅｐａｒａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ　ｂａｓｅｄ　ｏｎ　ｓｅｐａｒａｔｉｏｎ　ｂｏａｒｄ　ａｎｄ　ｓｅｐａｒａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ　ｂａｓｅｄ　ｏｎ　ｅｌｅｃｔｒｏｐｈｏｒｅｓｉｓ　ｔｅｃｈｎｉｑｕｅ． Ｔｈｅ　ＤＮＡ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｍｉｎｉｍａｌ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｐｒｏｂｌｅｍ　ｆｉｒｓｔ　ｂｒｅａｋｓ　ｃａｌｃｕｌａｔｉｏｎ　ｍｏｄｅｌ　ｏｆ　ＤＮＡ　ｃｏｍｐｕ－ ｔｉｎｇ—ｔｏ　ｆｏｒｍ　ｍｉｎｉｍａｌ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｇｒａｄｕａｌｌｙ　ｂｙ　ｍｅａｎｓ　ｏｆ　ｓｏｌｖｉｎｇ　ｍｉｎｉｍａｌ　ｅｄｇｅ　ｏｆ　ｃｕｔ　ｓｅｔ．Ｔｈｅ　ｍｅｔｈ－ ｏｄｓ　ｓｏｌｖｉｎｇ　ｃｕｔ　ｓｅｔ　ｒｅｄｕｃｅｓ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ａｌｇｏｒｉｔｈｍ　ｂｙ　ｍｅａｎｓ　ｏｆ　ｈｉｇｈ　ｐａｒａｌｌｅｌｉｓｍ　ｏｆ　ｓｅｐａｒａｔｉｏｎ　ｅｘ－ ｐｅｒｉｍｅｎｔ，ｓｏ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ＤＮＡ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｍｉｎｉｍａｌ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｐｒｏｂｌｅｍ　ｉｓ　ｌｉｎｅａｒ． Ｋｅｙ　ｗｏｒｄｓ　ｓｔｉｃｋｅｒ　ｍｏｄｅｌ；ＤＮＡ（ｄｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃ　ａｃｉｄ）ａｌｇｏｒｉｔｈｍ；ｍｉｎｉｍａｌ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｐｒｏｂｌｅｍ； ｓｅｐａｒａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ；ｃｕｔ　ｓｅｔ 　　ＤＮＡ计算模型［１－５］中粘贴模型［６－７］发展迅速． Ｂｒａｉｃｈ等［８］用粘贴模型解决了有２０个变量的３－ 可满足问题，周康等改进Ｂｒａｉｃｈ粘贴模型解决了 最优指派问题［９］和八皇后问题［１０］．本研究基于分 离实验的改进粘贴模型给出了最小生成树问题的 算法．长期以来，ＤＮＡ计算的主要计算模式是首 先产生包含最优解的所有可能解，然后筛选最优 解．本研究提出的算法改变了这种计算模式． １　粘贴模型的改进 粘贴模型的运算主体是存储合成物（由存储 链和粘贴链构成）．存储链为单链ＤＮＡ，粘贴链为 与存储链的子链互补的单链 ＤＮＡ形成，存储合 成物构成的混合物称为试管Ｓ． 改进粘贴模型包含２部分：ａ．改进粘贴模型 的物质基础是存储合成物（不等长单链ＤＮＡ）和 分离探针（与存储链的子链互补的ＤＮＡ，且固定 在充满聚丙烯酰胺凝胶体的玻璃板上）．ｂ．改进 粘贴模型的生化实验是合并、分离、扩增、电泳和 检测． 改进粘贴模型存储链的各 ＤＮＡ 片段取自 ＤＮＡ编码集合 Ｈ＝｛ａｉ｜ｉ＝１，２，…，ｒ｝．设试管 ＋（Ｓ，ａｉ）由试管Ｓ中所有含ａｉ的不等长存储链 组成；试管－（Ｓ，ａｉ）由试管Ｓ中所有不含ａｉ 的 不等长存储链组成．分离板ａ′ｉ是固定分离探针ａ′ｉ 的分离板，其中ａ′ｉ是ａｉ的补链． 这里主要使用４个基本生化实验：ａ．合并， 将２个试管Ｓ１ 和Ｓ２ 中的存储合成物组合在一个 试管Ｓ中（将试管Ｓ１ 和Ｓ２ 均匀混合为试管Ｓ）； ｂ．基于分离板的分离，将试管Ｓ分离成２个试管 ＋（Ｓ，ａｉ）和－（Ｓ，ａｉ）；ｃ．基于电泳的分离，将试 管Ｓ按照链长的不同 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 分离成试管Ｓ１，Ｓ２，…， Ｓｔ；ｄ．检测，对待测的存储合成物用分离和电泳 的方法确定其序列． 对ＤＮＡ编码ａｉ的基于分离板的分离实验过 程为：ａ．将分离板ａ′ｉ 初始化（变为单链探针）； ｂ．将试管Ｓ与分离板ａ′ｉ充分混合，升温至９４℃ 左右再缓慢冷却至６８℃左右，使探针与存储合成 物进行充分杂交；用６８℃的缓冲液冲洗移出的分 离板ａ′ｉ得到试管－（Ｓ，ａｉ）；ｃ．将该分离板与９４ ℃左右的缓冲液均匀混合，发生变性反应，再用 ９４℃的缓冲液冲洗移出的分离板ａ′ｉ 得到试管 ＋（Ｓ，ａｉ），且使分离板ａ′ｉ初始化． 基于电泳的分离实验过程为：ａ．对试管Ｓ的 存储合成物进行聚丙烯酰胺凝胶电泳实验；ｂ．将 聚丙烯酰胺凝胶支持介质按照实验要求分割成ｔ 份区带；ｃ．对每份区带分别并行地进行电泳实 验，释放区带上的存储合成物，得到试管Ｓ１，Ｓ２， …，Ｓｔ． 检测实验过程如下．ａ．对待测的存储合成物 进行荧光素标记，设待测的试管为Ｓ．确定待测的 ＤＮＡ编码集合Ｈ１＝｛ａｉ｜ｉ＝１，２，…，ｋ｝，并取出 与Ｈ１ 对应的分离板集合Ｒ１．ｂ．分离板集合Ｒ１ 与试管Ｓ均匀混合，升温至９４℃左右再缓慢冷 却至６８℃左右，进行杂交实验；再用６８℃左右的 缓冲液冲洗取出的分离板集合Ｒ１．ｃ．并行地对分 离板集合Ｒ１ 的每块分离板进行激光共聚焦显微 镜扫描，分析杂交实验结果：若分离板ａ′ｊ 的图像 的像素点（亮点）最多，则说明试管Ｓ中存储有合 成物． ２　最小生成树问题及ＤＮＡ算法 ２．１　最小生成树问题 设Ｇ＝ （Ｖ（Ｇ），Ｅ（Ｇ），Ｗ （Ｇ））和 Ｔ＝ （Ｖ（Ｔ），Ｅ（Ｔ），Ｗ（Ｔ））是２个赋权无向图，若 Ｖ（Ｔ）＝Ｖ（Ｇ）且Ｔ是树（不含圈的连通图），则称 Ｔ为Ｇ 的生成树．Ｔ的权值为 Ｗ（Ｔ）＝∑（Ｗ（ｅ）｜ｅ∈Ｅ（Ｔ））． 　　若对于生成树Ｔ′有Ｗ（Ｔ）≤Ｗ（Ｔ′），则称生 成树Ｔ是图Ｇ 的最小生成树．最小生成树问题是 在赋权无向图Ｇ中求一个最小生成树的问题． 设（Ｒ，Ｖ＼Ｒ）是赋权无向图Ｇ的二分划，图Ｇ 的边割｛Ｒ，Ｖ＼Ｒ｝是一顶点在Ｒ 中，另一顶点在 Ｖ＼Ｒ中的边集合．若从Ｇ中删除｛Ｒ，Ｖ＼Ｒ｝的边，Ｇ 的连通分支数恰好增加１，则边割｛Ｒ，Ｖ＼Ｒ｝称为 割集． 基于割集的Ｄｉｊｋｓｔｒａ算法的计算过程是：从 一个初始割集｛Ｒ，Ｖ＼Ｒ｝（Ｒ为由一个顶点组成的 集合）开始，若Ｒ．≠Ｖ，则进行如下循环：取出割 集｛Ｒ，Ｖ＼Ｒ｝中权最小的边，作为最小生成树的一 条边；该边在Ｖ＼Ｒ中的顶点从Ｖ＼Ｒ中去掉，放入 Ｒ中．本文基于粘贴模型以Ｄｉｊｋｓｔｒａ算法的思想 设计ＤＮＡ算法，该算法须要设计新的割集的产 生方法． 定理１　设｛Ｒ，Ｖ＼Ｒ｝为连通图Ｇ的割集，对 于ｖＲ，有｛｛ｖ｝，Ｖ＼｛ｖ｝｝＝Ｐ１∪Ｐ２，其中Ｐ１＝ ｛Ｒ，Ｖ＼Ｒ｝∩｛｛ｖ｝，Ｖ＼｛ｖ｝｝，Ｐ２＝｛｛ｖ｝，Ｖ＼｛ｖ｝｝＼ Ｐ１，则割集 　｛Ｒ∪ ｛ｖ｝，Ｖ＼｛Ｒ∪ ｛ｖ｝｝｝＝ ｛｛Ｒ，Ｖ＼Ｒ｝＼Ｐ１｝∪Ｐ２． 　　 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 　（Ｒ，Ｖ＼Ｒ）和（Ｒ∪｛ｖ｝，Ｖ＼｛Ｒ∪｛ｖ｝｝） 是二分划，且Ｐ１＝｛〈ｖｉ，ｖ〉｜ｖｉ∈Ｒ｝，Ｐ２＝｛〈ｖ， ｖｉ〉｜ｖｉ∈Ｖ＼｛Ｒ∪｛ｖ｝｝｝． ｅｋ＝〈ｖｉ，ｖｊ〉∈｛Ｒ∪｛ｖ｝，Ｖ＼｛Ｒ∪｛ｖ｝｝｝，有 ｖｉ∈Ｒ∪ ｛ｖ｝且ｖｊ∈Ｖ＼｛Ｒ∪｛ｖ｝｝，即有ｖｉ∈Ｒ且 ｖｊ∈Ｖ＼｛Ｒ∪｛ｖ｝｝或ｖｉ∈｛ｖ｝且ｖｊ∈Ｖ＼｛Ｒ∪｛ｖ｝｝； 因此ｅｋ∈｛Ｒ，Ｖ＼Ｒ｝且ｖｊ｛ｖ｝或ｅｋ∈Ｐ２，即ｅｋ∈ ｛Ｒ，Ｖ＼Ｒ｝＼Ｐ１ 或ｅｋ∈Ｐ２，ｅｋ∈｛Ｒ，Ｖ＼Ｒ｝＼Ｐ１∪Ｐ２． 上述推导可逆．结论得证． ｖＲ，由Ｒ∪｛ｖ｝产生割集的计算方法为： ａ．求出ｖ的割集｛｛ｖ｝，Ｖ＼｛ｖ｝｝；ｂ．将割集｛｛ｖ｝， Ｖ＼｛ｖ｝｝划分为顶点在Ｒ中的边集合Ｐ１ 和顶点在 Ｖ＼｛Ｒ∪｛ｖ｝｝中的边集合Ｐ２；ｃ．在｛Ｒ，Ｖ＼Ｒ｝中去 掉边集Ｐ１，得到Ｐ３；ｄ．由Ｒ∪｛ｖ｝产生的割集为 ·１３·第１期 　 　 周康，等：最小生成树ＤＮＡ算法　　　　　 　　 Ｐ３∪Ｐ２． ２．２　ＤＮＡ计算的算法 对连通正整数权无向图Ｇ＝（Ｖ，Ｅ，Ｗ），其中 Ｖ（Ｇ）＝｛ｖｉ｜ｉ＝１，２，…，ｎ｝为 Ｇ 的顶点集， Ｅ（Ｇ）＝｛ｅｉ｜ｉ＝１，２，…，ｍ｝为Ｇ的边集，Ｗ（Ｇ）＝ ｛ｗｉ｜ｅｉ∈Ｅ（Ｇ）｝为Ｇ的边权集．最小生成树问题 ＤＮＡ算法如下． 步骤１　对图Ｇ的每条边设计ＤＮＡ编码， 生成存储合成物和分离探针． ａ．每条边ｅｋ＝〈ｖｉ，ｖｊ〉∈Ｅ（Ｇ）（ｋ＝１，２，…， ｍ）对应一条存储合成物，并进行荧光素标记，其 编码分ａｉ，ａｊ和ｔｉｊ（ｉ，ｊ＝１，２，…，ｎ）３部分，其中： 前２部分ａｉ和ａｊ分别代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 边ｅｋ 的端点ｖｉ和ｖｊ， ｜ａｉ｜＝｜ａｊ｜＝１５ｂｐ；第３部分ｔｉｊ与边ｅｋ 的权ｗｋ 有关，｜ｔｉｊ｜＝３０（ｗｋ－１）ｂｐ．因此存储合成物 ａｉａｊｔｉｊ既代表图Ｇ 的边ｅｋ，也表示边权ｗｋ．存储合 成物的编码结构如图１所示． 图１　存储合成物编码结构 ｂ．每个顶点ｖｉ（ｉ＝１，２，…，ｎ）对应分离板 ａ′ｉ，其中｜ａ′ｉ｜＝１５ｂｐ，分离探针ａ′ｉ 为编码ａｉ的补 序列． 步骤２　从某个顶点ｖｉ 开始，构造初始割 集． ａ．合成所有存储合成物（有荧光素标记）得 到试管Ｐ０．制作所有分离板，得到分离板集合Ｓ＝ ｛ａ′１，ａ′２，…，ａ′ｎ｝．置ｋ＝１． ｂ．对某顶点ｖｉ，通过基于分离板的分离实验 将试管Ｐｋ－１分为试管Ｐｋ＝＋（Ｐｋ－１，ａｉ）（代表由 顶点ｖｉ产生的割集）和Ｑｋ＝－（Ｐｋ－１，ａｉ）（代表 该割集的补集）． ｃ．记录３个集合数据为：边集Ｅ（Ｔ）＝，分 离板集合Ｒ＝｛ａ′ｉ｝，分离板集合Ｓ＝｛ａ′１，ａ′２，…， ａ′ｉ－１，ａ′ｉ＋１，…，ａ′ｎ｝． 步骤３　求割集中最小权边，并记录实验结 果． ａ．通过基于电泳的分离实验将试管Ｐｋ 分为 链长最短的存储合成物试管Ｐ１ｋ 和剩余试管Ｐ２ｋ． ｂ．用分离板集合Ｓ检测试管Ｐ１ｋ，得到试管 ＋（Ｐ１ｋ，ａｊ）和试管－（Ｐ１ｋ，ａｊ）．即试管＋（Ｐ１ｋ，ａｊ） 有存储合成物，其他存储合成物组成试管－（Ｐ１ｋ， ａｊ）． ｃ．更新３个集合数据为：Ｅ（Ｔ）＝Ｅ（Ｔ）∪ ｛〈ｖｉ，ｖｊ〉｝，Ｒ＝Ｒ∪｛ａ′ｊ｝，Ｓ＝Ｓ＼｛ａ′ｊ｝． ｄ．合并试管Ｐ２ｋ 和试管－（Ｐ１ｋ，ａｊ），得到试 管Ｐｋ． 步骤４　产生最小生成树． ａ．通过基于分离板的分离实验将试管Ｐｋ 分 成试管＋（Ｐｋ，ａｊ）和－（Ｐｋ，ａｊ）；通过基于分离板 的分离实验将试管Ｑｋ 分成试管＋（Ｑｋ，ａｊ）和 －（Ｑｋ，ａｊ）；将试管－（Ｐｋ，ａｊ）和＋（Ｑｋ，ａｊ）合并 为试管Ｐｋ＋１（代表由Ｒ和Ｓ形成的割集），置试管 Ｑｋ＋１＝－（Ｑｋ，ａｊ）． ｂ．若ｋ＝ｎ－１，则Ｅ（Ｔ）为最小生成树Ｔ 的 边集；否则，置ｋ＝ｋ＋１，返回步骤３． ２．３　算法正确性和复杂性分析 定理２　设Ｔ是Ｇ 的生成树，则Ｔ是Ｇ 的最 小生成树的充分必要条件是对任意ｅ∈Ｅ（Ｔ），有 Ｗ（ｅ）＝ｍｉｎ（Ｗ（ｅ′）｜ｅ′ ∈Ω（ｅ））， 式中Ω（ｅ）是Ｔ－ｅ的２个连通分支Ｔ１ 和Ｔ２ 的顶 点集Ｓ１ 和Ｓ２ 构成的割集｛Ｓ１，Ｓ２｝． 定理３　在最小生成树问题ＤＮＡ算法的步 骤４中，当ｋ＝ｎ－１时，Ｅ（Ｔ）为最小生成树Ｔ的 边集． 证明　代表边〈ｖｉ，ｖｊ〉的存储合成物ａｉａｊｔｉｊ链 长｜ａｉａｊｔｉｊ｜＝３０ｗｋｂｐ表示该边的权值，ａｉ代表点 ｖｉ． 步骤２得到的试管Ｐ１＝＋（Ｐ０，ａｉ）代表由顶 点ｖｉ产生的割集，试管Ｑ１＝－（Ｐ０，ａｉ）代表该 割集的补集，此时Ｒ＝｛ａ′ｉ｝，Ｓ＝｛ａ′１，ａ′２，…，ａ′ｉ－１， ａ′ｉ，ａ′ｉ＋１，…，ａ′ｎ｝分别代表Ｒ＝｛ｖｉ｝，Ｓ＝｛ｖ１，ｖ２，…， ｖｉ－１，ａ′ｉ，ｖｉ＋１，…，ｖｎ｝． 当步骤３第１次迭代时，从试管Ｐ１ 中分离出 链长最短的存储合成物得到的试管Ｐ１１，并对试管 Ｐ１１ 检测出试管＋（Ｐ１１，ａｊ）．此操作过程代表的含 义是从由Ｒ产生的割集中取出权值最小的边，若 有多条最小边，则只取其中的一条．此时Ｅ（Ｔ）增 加一条边〈ｖｉ，ｖｊ〉，然后从Ｓ中取出一个点ｖｊ添加 到Ｒ中． 根据定理１及由此设计的计算方法，步骤４ 的ａ就是计算由Ｒ∪｛ｖｊ｝产生的割集． 在步骤３的第ｋ次迭代中，从试管Ｐｋ 中分离 出链长最短的存储合成物得到的试管Ｐ１ｋ，并对试 管Ｐ１ｋ 检测出试管＋（Ｐ１ｋ，ａｊ）．即从由Ｒ产生的割 集中取出最小权的一条边，此时Ｅ（Ｔ）达到ｋ条 边，Ｒ中含有ｋ＋１个顶点；因此，当ｋ＝ｎ－１时， Ｅ（Ｔ）有ｎ－１条边，根据定理２，得到最小生成 ·２３· 　　 华 中 科 技 大 学 学 报 （自 然 科 学 版） 　 第４０卷 树，Ｅ（Ｔ）为最小生成树Ｔ的边集．结论成立． 定理４　在正整数权无向图Ｇ＝（Ｖ，Ｅ，Ｗ） 中，Ｖ（Ｇ）＝｛ｖｉ｜ｉ＝１，２，…，ｎ｝为Ｇ 的顶点集， Ｅ（Ｇ）＝｛ｅｉ｜ｉ＝１，２，…，ｍ｝为Ｇ的边集，Ｗ（Ｇ）＝ ｛ｗｉ｜ｅｉ∈Ｅ（Ｇ）｝为Ｇ的边权集．则最小生成树问 题ＤＮＡ算法的实现过程使用了２×∑（ｗｋ｜ｋ＝ １，２，…，ｍ）个ＤＮＡ编码、ｎ块分离板、１１个试管 （每次迭代试管循环使用时），总的操作次数为 ９ｎ＋３次． 证明　分析步骤１的编码过程可以看出：实 验过程进行了２×∑（ｗｋ｜ｋ＝１，２，…，ｍ）个ＤＮＡ 编码，并需要ｎ块分离板． 步骤２共使用了３个试管，进行了３次实验． 步骤３中，ａ需要２个试管，进行了１次实验；ｂ需 要２个试管，进行了３次实验；ｃ进行了１次实 验；ｄ进行了１次实验，共需要４个试管，进行了６ 次实验．步骤４需要２＋２个试管，进行了１＋１＋１ 次实验，共需要４个试管，进行了３次实验． 迭代循环在步骤３和步骤４之间进行，因此 迭代循环共进行了９ｎ次实验，且每次循环得到２ 个试管作为循环的实验结果，因此其他的试管经 过处理后可以重复使用，即整个循环共需要８个 试管．结合步骤２的分析，整个算法的实现共需要 １１个试管，进行了９ｎ＋３次实验． ３　仿真实验 为说明ＤＮＡ计算求解最小生成树问题的有 效性和正确性，讨论如图２所示的４阶连通的赋 权简单图Ｇ＝（Ｖ，Ｅ，Ｗ），式中：Ｖ（Ｇ）＝｛ｖ１，ｖ２， ｖ３，ｖ４｝；Ｅ（Ｇ）＝｛ｅ１，ｅ２，ｅ３，ｅ４，ｅ５｝；Ｗ（Ｇ）＝｛１，３， ２，３，４｝．计算过程和结果如下． 图２　最小生成树问题的赋权无向图 ａ．构造图Ｇ的顶点的ＤＮＡ编码（左端为５′ 端，右端为３′端），即 ｖ１：ＡＡＡＣＴＡＣＴＴＡＴＣＣＴＣ，记为ａ１； ｖ２：ＡＡＣＴＡＡＴＴＣＡＴＣＣＴＣ，记为ａ２； ｖ３：ＴＴＴＡＣＴＣＡＴＡＣＡＡＣＣ，记为ａ３； ｖ４：ＣＴＴＴＣＴＡＡＴＡＣＡＣＡＣ，记为ａ４． ｂ．对应图Ｇ 的边ｅｋ 的权值ｗｋ 构造ｔｉｊ的 ＤＮＡ编码（左端为５′端，右端为３′端），即 ｗ２： ＡＣＴＡＡＣＣＡＣＡＣＴＴＴＴＴＴＣＣＴＡＴ－ ＴＡＡＡＣＣＡＣＡＡＡＣＴＣＡＴＴＡＴＣＣＣＴＣＡＴＴＴ－ ＴＡＴＣＡＣＡＣＡＣ，记为ｔ１３； ｗ３： ＴＴＣＣＴＴＴＣＣＡＡＣＡＡＡＡＡＣＴＡＡＣ－ ＣＣＡＴＴＣＴＴ，记为ｔ２３； ｗ４：ＣＣＡＡＴＴＡＣＴＡＴＣＴＣＡＡＡＡＣＴＴＡＣ－ ＴＡＴＴＣＣＣＡＡＣＴＡＴＴＡＣＡＴＴＣＣＣＡＣＴＡ－ ＡＴＴＴＴＡＣＣＡＣＣ，记为ｔ２４； ｗ５： ＡＡＡＣＴＴＣＡＴＡＣＴＴＣＣＡＣＴＡＡＡＴ－ ＴＣＡＣＴＴＣＣＴＣＴＴＡＴＴＣＡＡＡＣＣＡＣＡＡＣＴＡ－ ＣＡＴＴＡＣＴＴＣＣＣＣＴＣＡＣＡＴＴＡＡＴＡＴＣＡＡＣＴ－ ＡＣＴＣＴＡＴＴＡＣＣ，记为ｔ３４． ｃ．对应每条边ｅｋ 合成存储合成物组，得到试 管Ｐ０，其编码（左端为５′端，右端为３′端）为ｅ１： ａ１ａ２；ｅ２：ａ１ａ３ｔ１３；ｅ３：ａ２ａ３ｔ２３；ｅ４：ａ２ａ４ｔ２４；ｅ５：ａ３ａ４ｔ３４， 其 中 Ｐ０ ＝ ｛ａ１ａ２，ａ１ａ３ｔ１３，ａ２ａ３ｔ２３，ａ２ａ４ｔ２４， ａ３ａ４ｔ３４｝． ｄ．取顶点ｖ１，用分离板ａ′１ 对试管Ｐ０ 进行基 于分离板的分离实验得到试管 Ｐ１ ＝ ｛ａ１ａ２， ａ１ａ３ｔ１３｝和试管Ｑ１＝｛ａ２ａ３ｔ２３，ａ２ａ４ｔ２４，ａ３ａ４ｔ３４｝，并 记录Ｅ（Ｔ）＝，Ｒ＝｛ａ′１｝，Ｓ＝｛ａ′２，ａ′３，ａ′４｝． ｅ．对试管Ｐ１ 进行基于电泳的分离实验，得 到试管Ｐ１１＝｛ａ１ａ２｝和试管Ｐ２１＝｛ａ１ａ３ｔ１３｝．用Ｓ检 测试管Ｐ１１，得到试管＋（Ｐ１１，ａ２）＝｛ａ１ａ２｝和试管 －（Ｐ１１，ａ２）＝．更新记录Ｅ（Ｔ）＝｛ｅ１｝，Ｒ＝｛ａ′１， ａ′２｝，Ｓ＝｛ａ′３，ａ′４｝．置Ｐ１＝Ｐ２１＝｛ａ１ａ３ｔ１３｝． ｆ．用分离板ａ′２ 分离试管 Ｐ１，得到试管 ＋（Ｐ１，ａ２）＝ 和试管－（Ｐ１，ａ２）＝｛ａ１ａ３ｔ１３｝．用 分离板ａ′２ 对试管Ｑ１ 进行分离实验，得到试管 ＋（Ｑ１，ａ２）＝｛ａ２ａ３ｔ２３，ａ２ａ４ｔ２４｝和－（Ｑ１，ａ２）＝ ｛ａ３ａ４ｔ３４｝．对－（Ｐ１，ａ２）和＋（Ｑ１，ａ２）合并得到试 管Ｐ２＝｛ａ１ａ３ｔ１３，ａ２ａ３ｔ２３，ａ２ａ４ｔ２４｝，置试管Ｑ２＝ －（Ｑ１，ａ２）＝｛ａ３ａ４ｔ３４｝． ｇ．对试管Ｐ２ 进行基于电泳的分离实验，得 到试管 Ｐ１２ ＝ ｛ａ２ａ３ｔ２３｝和试管 Ｐ２２ ＝ ｛ａ１ａ３ｔ１３， ａ２ａ４ｔ２４｝．用Ｓ检测试管Ｐ１２，得试管＋（Ｐ１２，ａ３）＝ ｛ａ２ａ３ｔ２３｝和－（Ｐ１２，ａ３）＝．更新记录Ｅ（Ｔ）＝ ｛ｅ１，ｅ３｝，Ｒ＝｛ａ′１，ａ′２，ａ′３｝，Ｓ＝｛ａ′４｝．置 Ｐ２ ＝ ｛ａ１ａ３ｔ１３，ａ２ａ４ｔ２４｝． ｈ．用分离板ａ′３ 分离试管 Ｐ２，得到试管 ＋（Ｐ２，ａ３）＝｛ａ１ａ３ｔ１３｝和－（Ｐ２，ａ３）＝｛ａ２ａ４ｔ２４｝． 用分离板ａ′３ 对试管Ｑ２ 进行分离实验，得到试管 ＋（Ｑ２，ａ３）＝｛ａ３ａ４ｔ３４｝和－（Ｑ２，ａ３）＝．合并 －（Ｐ２，ａ３）和＋（Ｑ２，ａ３）得到试管Ｐ３＝｛ａ２ａ４ｔ２４， ａ３ａ４ｔ３４｝，置试管Ｑ３＝－（Ｑ２，ａ３）＝． ｉ．对试管Ｐ３ 进行基于电泳的分离实验，得 到试管Ｐ１３＝｛ａ２ａ４ｔ２４｝和试管Ｐ２３＝｛ａ３ａ４ｔ３４｝．用Ｓ ·３３·第１期 　 　 周康，等：最小生成树ＤＮＡ算法　　　　　 　　 检测试管Ｐ１３，得到试管＋（Ｐ１３，ａ４）＝｛ａ２ａ４ｔ２４｝和 试管－（Ｐ１３，ａ４）＝，更新记录Ｅ（Ｔ）＝｛ｅ１，ｅ３， ｅ４｝，Ｒ＝｛ａ′１，ａ′２，ａ′３，ａ′４｝，Ｓ＝．得到最小生成树， 其边集为Ｅ（Ｔ）＝｛ｅ１，ｅ３，ｅ４｝． 本文首次将分离实验扩展为基于分离板的分 离实验和基于电泳技术的分离实验，用生化实验 实现了求解割集的计算． 参 考 文 献 ［１］周康，刘朔，覃磊，等．质粒ＤＮＡ计算模型的计算体 系［Ｊ］．华中科技大学学报：自然科学版，２０１１， ３９（２）：３２－３５． ［２］周康，魏传佳，程珍，等．ＤＮＡ计算模型的研究［Ｊ］． 计算机工程与应用，２００９，４５（１８）：１－５，１２． ［３］周康，同小军，许进．基于ＤＮＡ计算的指派问题［Ｊ］． 华中科技大学学报：自然科学版，２００８，３６（２）：３５－ ３８． ［４］周康，覃磊，高婧，等．ＤＮＡ计算在电路设计中的应 用［Ｊ］．华中科技大学学报：自然科学版，２００８， ３６（８）：１０７－１１０． ［５］周康，强小利，同小军，等．求解ＴＳＰ算法［Ｊ］．计算 机工程与应用，２００７，４３（２９）：４３－４７． ［６］许进，李三平，董亚非，等．粘贴 ＤＮＡ 计算机模型 （Ⅱ）：应用［Ｊ］．科学通报，２００４，４９（４）：２９９－３０７． ［７］许进，董亚非，魏小鹏，等．粘贴 ＤＮＡ 计算机模型 （Ⅰ）：理论［Ｊ］．科学通报，２００４，４９（３）：２０５－２１２． ［８］Ｂｒａｉｃｈ　Ｒ　Ｓ，Ｃｈｅｌｙａｐｏｖ　Ｎ，Ｊｏｈｎｓｏｎ　Ｃ，ｅｔ　ａｌ．Ｓｏｌｕｔｉｏｎ ｏｆ　ａ　２０－ｖａｒｉａｂｌｅ　３－ＳＡＴ　ｐｒｏｂｌｅｍ　ｏｎ　ａ　ＤＮＡ　ｃｏｍｐｕｔｅｒ ［Ｊ］．Ｓｃｉｅｎｃｅ，２００２，２９６（５５６７）：４９９－５０２． ［９］周康，同小军，许进．最优指派问题ＤＮＡ算法［Ｊ］．系 统工程与电子技术，２００７，２９（７）：１１８３－１１８７． ［１０］周康，同小军，许进．基于粘贴ＤＮＡ芯片模型的八 皇后问题算法［Ｊ］．系统工程学报，２００８，２３（３）： 檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 檪 殏 殏殏 殏 ３７２－３７６． 比利时和德国２高校代表团访问我校 ２０１１年１１月３０日和１２月１日，比利时新鲁汶大学、德国拜罗伊特大学代 表团先后来我校访问，校领导骆清铭、邵新宇分别会见了来宾． １１月３０日，副校长邵新宇会见了来访的新鲁汶大学副校长马克一行，就研 究生联合培养、研究人员互换等达成共识．双方决定，今后将在通信、图像处理等 研究领域展开合作，共同资助学者和研究人员交流，联合培养博士研究生．马克 表示，华中科技大学研究人员可赴新鲁汶大学工程学院进行１～３个月的访问研 究，也可共同申请欧盟课题，并希望２０１２年４月来华中科技大学讲授研究生国 际化课程． １２月１日，我校与德国拜罗伊特大学续签合作 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ，副校长骆清铭为拜罗 伊特大学副校长施特凡·莱布勒颁发了客座教授聘书．莱布勒希望进一步推进 合作、深化交流，并愿为法学院师生赴德交流提供更为广阔的平台．我校与拜罗 伊特大学的合作始于２００３年，双方的交流合作包括交换生培养、互派访问教师、 学术交流等． ·４３· 　　 华 中 科 技 大 学 学 报 （自 然 科 学 版） 　 第４０卷