基于DNA计算的无向赋权图哈密顿路径问题  

Undirected Weighted Graph Hamilton Path Question Based on DNA Algorithm

作　　者：鲍士军[1] 殷志祥[2] 王伟[1] 

机构地区：[1]安徽理工大学电子与信息工程学院,安徽淮南232001 [2]安徽理工大学理学院,安徽淮南232001

出　　处：《科技广场》2008年第7期6-8,共3页Science Mosaic

摘　　要：本文给出一种通过DNA序列编码来处理权值的方式,对无向赋权图哈密顿路径问题进行了描述。首先用寡核苷酸片段编码图中的顶点和边,然后将这些寡核苷酸片段放入缓冲溶液中,利用连接酶将它们连接起来,从而产生所有无向边不同的DNA链,最后利用PCR扩增、探针、电泳等生物手段寻找对应于只经过图的顶点一次的无向Hamilton路的DNA链,通过比较以及前面实验条件的控制最终找到最短的Hamilton路径。This article gave a way to process the weight by the DNA sequence code, and described the question of an undirected weighted graph Hamilton way. First, the apexes and cdges of the graph were coded by the oligodeoxynucleotide fragments and then they were put in the buffer solution and were connected by the ligase to produce different DNA chains of all undirected edges. Finally the DNA chain of undirected Hamilton path which passed through the chart apexes only one time were found by PCR amplification, probes, electrophoresis and some biological methods. By comparison the control of the front experimental condition, the shortest Hamilton way was found finally.

关 键 词：DNA计算 无向赋权图 哈密顿路径 生物操作 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]