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

DNA Algorithm Temperature Gradient Gel Electrophoresis for Minimum Cost Spanning Tree Problem

作　　者：江智兰[1] 周金凤[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001

出　　处：《软件导刊》2013年第3期58-60,共3页Software Guide

摘　　要：DNA计算是解决困难问题的一种很重要的方法。应用DNA计算解决图论中的最小支撑树问题。利用DNA的热力学特性,根据边的权长不同,给它们设计不同溶解温度的DNA链。根据温度的不同,电泳时DNA分子的形状不同,电泳的速度也不同,从而根据电泳速度分离出最小支撑树的所有边。在这里给出了5个顶点的赋权图为例来求它的最小支撑树,说明了该方法的简便性。DNA computing was an extraordinary important method to solve difficult issues. In this paper, it solves a mini- mum cost spanning tree that is one of the most difficult question in the graph theory by DNA computing. And the thermodynamics properties of DNA strand needed. The weight of the edge is different the melting temperature of DNA strand is not alike and the speed of the gel eleetrophoresis is different. According this method to get all the edges of the graph minimum cost spanning tree. A graph has five vertexes as an example for proof the simple of this method.

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]