中国邮递员问题的D N A荧光标记检测

江智兰

（安徽理工大学理学院 安徽 淮南 232001）

0 引言

目前对DNA计算的研究越来越多，并且DNA计算的应用也越来越广。自从1994年Adleman博士开创性地用DNA计算实现了七个顶点的有向图的Hamilton路[1]问题以来，DNA计算就吸引了国内外许多的研究学者，各种DNA计算模型也因很强的实用性成为研究热点，本文主要探讨中国邮递员问题的解的检测问题。DNA自组装是分子与分子在一定的条件下，依赖非共价键分子间作用力自发连接成结构稳定的分子聚体的过程，早在1962年Wang用DNA单链组装成瓦片作为计算的手段[2]，1998年，Winfree在他的博士论文中首先提出一种二维自组装的抽象模型，命名称为瓦片组装模型（TAM）[3]；2000年，Lagoudakis给出了利用二维TAM求解可满足性问题的方法.不断取得成果，尤其是在密码破译和图论与组合优化问题方面[4]。2008年，Cheng提出了一种基于DNA瓦片自组装的椭圆曲线密钥交换算法；同年Chen利用TAM实现了一次一密加密算法Huang利用DNA瓦片自组装解决了0-1规划问题.2009年，zhu等用自组装技术设计了一个软件系统，一体化集成程序来设计DNA图案和相呼应的阵列[5]；2011年宋勃升，殷志祥等利用DNA自组装成发夹结构解决可满足性问题，在计算过程中只需要用到凝胶电泳操作，在一定程度上大大减少了因生物操作过多而引起的各种实验误差[6]。在同年张成等人利用DNA计算和纳米技术相结合研究了自组装DNA/纳米颗粒分子逻辑计算模型摘要将AuNP自组装聚合色变与DNA计算相结合，构建了纳米分子逻辑计算模型[7].2009年，李玮等人提出了虚拟权值和虚拟节点的概念，给出了中国邮递员问题的一种基于DNA计算的求解算法[8]。本文主要探讨中国邮递员问题的解的检测问题。

中国邮递员问题是由我国管梅谷教授首先提出并加以研究的NP完全问题中的一种。

问题描述：邮递员在邮局分拣好需要邮递的邮件后，到他管辖的区域内的每一条街道投递，最后返回邮局。对于这个问题邮递员希望找出一条行走距离最短的路线。

将中国邮递员问题转化为图论模型就可以这样描述：我们把邮递员所管辖的区域看做一个连通的加权无向图G＝（V，E），其中V＝（v1，v2，…vn）是街道的交叉口和端点，E＝（E1，E2，…Em）是街道，权看作街道的长度。解决中国邮递员问题，就是在连通加权无向图总，找一条经过每边至少一次且权和最小的闭链，即对图G中给定的节点vi，需要从所有可能路径集{Pi}中求得一条最优路径Pj，Pj满足：①Pj是从节点vi开始到节点vi结束；②Pj是经过所有边至少一次且权和最小的一条路。

1 中国邮递员问题的DNA计算模型

1.1 基本算法

步骤1：所搜出G的所有闭路径；

步骤2：找出那些开始于G，也结束与G的固定节点的闭路径；

步骤3：找出那些经过图G国有边至少一次的闭路径，即保留G的所有广义Euler回路；

步骤4：找出最短的广义Euler回路，即权和最小的，也就是我们所求的；

步骤5：确定邮递员的路线。

1.2 DNA算法及生物操作

步骤1：对给定图G的节点和边进行编码。对图G中的任意节点vi生成长度为20bp的核酸序列分别记为V1，V2，…Vn，并且对权长wi生成长度为10bp的寡聚核苷酸序列记作d1，d2，…dm。每条边eij即相邻两节点vi和vj之间的路的编码包含三部分。第一部分是寡聚核苷酸片段Vi的后10个碱基的补所构成的寡聚核苷酸片段；第二部分是表示权的编码及表示di的寡聚核苷酸片段；第三部分是寡聚核苷酸片段vj的前10个碱基的补所构成的寡聚核苷酸片段。如果Vi是V1即是起点的时候，路的寡聚核苷酸片段的第一个部分是寡聚核苷酸V1的全部即20个碱基的补构成的，如果vj是V1，那么路的寡聚核苷酸片段的第三部分是寡聚核苷酸V1的全部即20个碱基的补构成的。那么由vj到vi的路eji以类似的方法得到编码。对编码好的核苷酸片段为了生成图G的所有闭路径，我们将一定量的节点vi所对应的DNA片段Vi和边eij所对应的DNA片段混合在一起，加入缓冲溶液，DNA连接酶使之进行连接反应。可以通过考虑各种生物实验的影响因素，进行相应的调节使之达到最优的反应速度。经过反应，相应节点和相应边的核苷酸片段会连接起来。形成了包含所有或者一些节点和边的DNA片段。

步骤2：以V1为引物，用PCR放大技术，使以V1为起始并以V1为终点的DNA链进行放大。因为在第一步还有其他的DNA链生成，所有需要对所求的DNA链进行放大，第一次用V1作引物放大，在第二次用PCR进行放大时用V1的补链作引物。然后加热使DNA双链变性生成相应的DNA单链。

步骤3：亲和纯化第二步得到的产物，为了分离出我们所需的DNA链，我们可以用各个边eij或eji的补链作探针，将含有eij或eji边的DNA链经过滤池从数据池中分离。然后再把分离出的DNA链进行相同的操作，直到分离出含有每边至少一次的所有DNA链。得到问题的可行解。

步骤4：对步骤3得到的DNA链用凝胶电泳，由于长的DNA链的移动速度小于短的DNA链，所以分离出移动速度最快的DNA链。步骤5：对步骤4得到的DNA链用下列方法确定边的访问顺序。（1）得到的DNA单链固定到表面上。

（2）∀eij是图中的一条从 vi到 vj的边，eji是从 vj到 vi的边，将边的补连接上不同的荧光素。

（3）将加上不同荧光素的边的补链加到表面上。

（4）重复上述操作直到DNA单链变为DNA双链，利用激光共聚显微镜观察表面上的DNA双链的荧光素的颜色，就可以确定其对应的路径中包含的各条边的访问顺序。

2 实例分析

我们根据图1给出中国邮递员问题的DNA算法的详细解答，v1是邮

图1 6个顶点的完全图

步骤1：对上图可记作 G＝（V，E），其中 V＝{v1，v2，…，v6}，E＝{e1，e2，…，e}。其中边权为1，2，3.我们对图的顶点和边进行编码，具体情况如下表：

步骤5：对步骤4得到的DNA链利用荧光加到表面的方法来测序，得到我们所需的路线。

表1 顶点及权长的编码

其中任一边长，如e23的编码为AATTGGCAGCattagcaacgGGGAAA CGTG，然后在试管中大量生产顶点和边的DNA片段，加入缓冲溶液，加入链接酶，使得顶点和边的DNA片段链接在一起生成包含所有节点或部分节点的路的DNA片段。

步骤2：用V1作引物用PCR放大技术，使以V1为起始并以V1为终点的DNA链进行放大。第一次用V1作引物放大，在第二次用PCR进行放大时用V1的补链作引物。然后加热使DNA双链变性生成相应的DNA单链。

步骤3：亲和纯化第二步得到的产物，直到分离出含有每边至少一次的所有DNA链。得到问题的可行解。本例题中的可能的可行解有如：V1-V2-V3-V4-V5-V6-V

步骤4：对步骤3得到的DNA链用凝胶电泳，由于长的DNA链的移动速度小于短的DNA链，所以分离出移动速度最快的DNA链。

3 结论

中国邮递员问题是困难计算问题中的一个，电子计算机的存储量小，运算速度慢，对于解这样的难题是非常困难的。DNA计算具有很好的并行性，因此在解决这类难题时，具有电子计算机无法比拟的优势在本文中主要是运用了PCR放大技术和凝胶电泳技术得到我们所需的DNA链，然后再用在表面加上荧光素来检测序列，最终确定我们邮递员所经过的路线。

具有方法简单，易于解读到结果的特点。

［1］Leonard M.Adleman.Molecular Computation of Solutions to Combinatorial Problems[J].Science，1994，266（5187）：1021-1024.

［2］Wang Hao.Dominoes and theSEA case of the decision problem[C].Proceedings of the Symposium in the Mathematical Theory of Automata.Brooklyn，1962：23-55.

［3］Winfree E，Liu F，Wenzler LA，eta1.Design and self-assembly of two-dimensional DNA crystals[J].Nature，l998，394（6693）：539-544.

［4］LagoudakisMG，LaBeanTH.2DDNA self-assembly for satisfiability[Z].In DNA BasedComputers V：DIMACS Workshop.Providence，2000，139·152.

［5］Zhu Jin hao， Wei Bryan，i YuanYuan， et a.l Uuniquimer3D， asoftware system for structuralDNAnanotechnologydesign，analy sisand evaluation[J].NucleicAcids Research，2009，37（7）：2164-2175.

［6］宋勃升，殷志祥，甄诚，华程.DNA自组装的可满足性问题模型[J].小型微型计算机系统，2011，9（32）：1872-1875.

［7］张成，杨静，许进.自组装DNA/纳米颗粒分子逻辑计算模型[J].科学通报，2011，27（57）：2276-2282.

［8］李玮，王雷.中国邮递员问题的 DNA 计算[J].计算机应用，2009，29（7）：1880-1883.