图的最小顶点覆盖问题的质粒DNA计算模型

被引：5

作者：

王淑栋

刘文斌

许进

机构：

[1] 华中科技大学控制科学与工程系

[2] 华中科技大学控制科学与工程系湖北武汉

[3] 湖北武汉

来源：

关键词：

DNA计算; 最小顶点覆盖问题; NP完全问题;

D O I：

10.13245/j.hust.2004.11.021

中图分类号：

Q7-3 [];

学科分类号：

071010 ;

摘要：

给出了图的最小顶点覆盖问题的质粒DNA计算模型及其实现算法 .算法的时间复杂性是O(q) ,编码最小覆盖问题所需的核苷酸片段种类为n ,其中n ,q分别是图的规模和边数 .在算法中 ,所用酶的种类也等于图的规模 .而且 ,算法不需要复杂的单链DNA自身退火反应和PCR扩增

引用

页码：59 / 61

页数：3

共 8 条

[1]

A surfacebased approach to DNA computation. Smith L M,Corn R M,Condon A E,et al. Journal of Computational Biology . 1998

[2]

Molecular computation of solution to combinatorial problems. Adleman L M. Science . 1994

[3]

DNA Solutions of hard computational problem. Lipton R J. Science . 1995

[4]

DNA Solution of the maximal clique problem. Ouyang Q,Kaplan P D,Liu S,et al. Science . 1997

[5]

Computing with DNA by operating on plasmids. Head T,Rozenberg G. Biosystems Engineering . 2000

[6]

Graph Theory with Application. Bondy J A,Murty U S R. . 1976

[7]

An improved surface-based method for DNA computation. Wu Haoyang. Biosystems Engineering . 2001

[8]

DNA Computing on surfaces. Liu Q,Wang L,Frutos A G,et al. Nature . 2000