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

摘 要：DNA计算是解决困难问题的一种很重要的方法。应用DNA计算解决图论中的最小支撑树问题。利用DNA的热力学特性，根据边的权长不同，给它们设计不同溶解温度的DNA链。根据温度的不同，电泳时DNA分子的形状不同，电泳的速度也不同，从而根据电泳速度分离出最小支撑树的所有边。在这里给出了5个顶点的赋权图为例来求它的最小支撑树，说明了该方法的简便性。

关键词：DNA计算；温度梯度凝胶电泳；最小支撑树

中图分类号：TP312 文献标识码：A 文章编号：16727800（2013）003005803

0 引言

哈密顿路是图论中的一个NP完全问题，1994年，Adleman博士首先提出了利用DNA解决此问题。先对有向图的哈密顿路问题进行编码，然后借助一系列的生物操作，最后得到了图的哈密顿路。这一研究成果开辟了DNA计算这一崭新的研究领域。随后就有很多的专家学者对DNA计算进行了深刻的研究。1995年，Lipton在Adleman思想的启发下对SAT（可满足性问题）进行了探讨。Narayanan 和Zorbalas解决最短路径问题，使用长度比例恒定的DNA计算技术，其中一个DNA链的编码长度根据实际长度的距离不断提高。Lee等人提出了解决TSP问题的温度梯度DNA计算技术。2011年宋勃升、殷志祥等利用DNA自组装成发夹结构解决可满足性问题，在操作过程中只需要用到凝胶电泳操作，在一定程度上大大减少了因生物操作过多而引起的各种实验误差。2011年Zoraida等人提出了用温度梯度的DNA算法解决中国邮递员问题。文中Zoraida等人提出了变性温度梯度PCR（DTGPCR）技术，温度梯度凝胶电泳（TGGE）技术和溶解温度（Tm）等概念。变性温度梯度PCR技术，这是一种改良的PCR技术，在这过程中分子的变性温度是随着放大周期的变化而变化的，变性温度从70℃开始，然后每一个周期温度升高1℃，直到温度升高到95℃，这个时候在其后的放大过程中温度将保持不变。其它方面的放大的过程和PCR技术一样。 DNA分子单链和其补链对DNA分子的解温度的影响是一样的。溶解温度和分子中的GC含量有关，也会和其它的一些因素有关，在这里仅考虑GC含量。

对DNA分子的操作，既有物理的也有化学的，物理操作包括温度，酸碱度等。传统的电泳分离方法基于分子的大小和带电荷数的多少，在这篇文章中会考虑温度对分子构造间的范德华力的影响。1999年陈汉奎，冯忻在温度梯度凝胶电泳技术及应用的文章中给出了温度梯度凝胶电泳的分析原理（TGGE），在正常情况下， DNA分子呈双链结构状态；当温度升高到一定时，DNA双链开始解开， 由完整的双链变为分叉双链； 如果温度继续升高，DNA双链完全解开，变为DNA单链.这种分子结构的改变会影响DNA分子在电泳时的迁移速度， 因为DNA双链的打开直接导致迁移率下降. 这种影响在两条链即将完全解开时最大， 此时分子的电泳速度最慢； 而当全部形成单链时， 电泳的速度又会变快，对于序列不同但长度相同的DNA链的溶解温度依赖于基本序列。 所以TGGE不仅能分离DNA分子，也给出了DNA分子的溶解性和稳定性特点。本文就利用温度梯度凝胶电泳对DNA分子进行电泳，从而解决一个5个顶点的赋权图的最小支撑树问题， 通过表面荧光技术得到图的最小支撑树。

1 最小支撑树

1.1 算法具体步骤

1.2 DNA算法编码与操作

对应于上述最小支撑树的算法给出最小支撑树的DNA算法。以图1为例，详细介绍温度梯度凝胶电泳的DNA计算方法。

步骤1：对图G=（V，E），对图G的任意顶点vi，用长度为20的寡聚核苷酸片段表示，记为Vi并且它们具有相同的溶解温度。然后利用Vi构造探针记作Ai。对图G的权，每一种权wij都有唯一的长为20的寡聚核苷酸片段与其对应，且权值不同，它们的溶解温度也不同。权值小的，它们的DNA链的溶解温度小，权值大的，它们的DNA链的溶解温度高。这里的溶解温度主要考虑其与GC含量有关。然后将编码好的DNA链进行下列杂交从而得到每条边的DNA链。如任意的边eij它的编码包含3个部分，第一部分是寡聚核苷酸片段Vi的碱基的补链所构成的寡聚核苷酸片段；第二部分是wij的寡聚核苷酸片段；第三部分是寡聚核苷酸片段Vj的碱基的补链所构成的寡聚核苷酸片段。将编码好的每条边的DNA链等量混合在一起，加入缓冲溶液，放入试管T1中。

对图1的顶点及边权进行编码如表1所示。

步骤2：从试管T1中取出溶液进行温度梯度凝胶电泳，不同权长的边有不同的DNA编码，有不同的DNA链溶解温度。权长越小，溶解温度越低，电泳的速度越快。跑子最前的就是权长最小的边的DNA链，收集此DNA链。

步骤3：对步骤2中的产物进行测序，可以把得到的产物固定到表面上，然后将顶点Vi的补链i分别标记上不同的颜色，加到表面上，然后通过激光共聚焦显微镜观察表面上的DNA双链的颜色，就可以确定所得DNA链的碱基排序，找到了图的最小边。不妨记这条边为eij=vivj，用Ai，Aj作探针，将含有顶点vi和vj的边eij从试管中分离出来。然后再用Ai作探针将含有顶点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；v2v3分离出来建立新的试管仍记作T1，转入第二步.经过第二次循环，找到v1v5；v1v4；v2v4；v2v3中最短的边是v2v3，再经过三次循环后就可以找到图G的最小支撑树T。图1的最小支撑树见图2。

4 结语

运用DNA分子的凝胶电泳受温度的影响， 根据序列不同但长度相同的DNA链的溶解温度是依赖于基本序列的，图中的边权及两点间的距离用不同的温度代替设计不同的DNA序列，距离不同，DNA链的溶解温度不同，从而电泳的速度不同.对图的顶点使其DNA序列的溶解温度相同，然后通过温度梯度凝胶电泳得到图的最小支撑树的各条边，最后利用表面荧光技术确定最短边的顶点从而得到所求图的最小支撑树。这种方法很好地克服了电子计算机在存储和速度方面的局限性，加快了反应速度，并且易于操作。

参考文献：

＼[1＼] LEONARD M， ADLEMAN. Molecular computation of solutions to combinatorial problems＼[J＼].Science，1994（5187）.

＼[2＼] LIPTON R J. DNA Solution of hard computation problem＼[J＼].Science，1995（4）.

＼[3＼] AJIT NARAYANAN AND SPIRIDON ZORBALAS. DNA algorithms for computing shortest paths＼[C＼].Proceedings of Genetic Programming，1998.

＼[4＼] JI YOUN LEE， SOOYONG SHIN， TAI HYUN PARK AND BYOUNGTAK ZHANG.Solving traveling salesman problem with DNA molecules encoding numerical values＼[J＼]. Biosystems，2004（3）.

＼[5＼] B S E ZORAIDA. DNA algorithm employing temperature gradient for chinese postman problem＼[J＼].IEEE，2011（4）.

＼[6＼] 宋勃升，殷志祥， 甄诚，等.DNA自组装的可满足性问题模型＼[J＼].小型微型计算系统，2011（32）.

＼[7＼] 陈汉奎，冯忻.温度梯度凝胶电泳技术及应用＼[J＼].生物化学与生物物理进展，1999（3）.

＼[8＼] 殷志祥.图与组合优化中的DNA计算＼[M＼].北京：科学出版社，2004.