基于质粒DNA匹配问题的分子算法

被引：13

作者：

高琳

马润年

许进

机构：

[1] 西安电子科技大学电子工程研究所

[2] 华中科技大学系统科学研究所西安

[3] 西安

[4] 武汉

来源：

生物化学与生物物理进展 | 2002年 / 05期

关键词：

质粒; DNA计算; NP完全问题; 最大匹配;

D O I：

暂无

中图分类号：

Q75 [分子遗传学];

学科分类号：

071007 ;

摘要：

给定无向图 ,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者 ,这个问题是著名的NP 完全问题 .1994年Adleman博士首次提出用DNA计算解决NP 完全问题 ,以编码的DNA序列为运算对象 ,通过分子生物学的运算操作解决复杂的数学难题 ,使得NP 完全问题的求解可能得到解决 .提出了基于质粒DNA的无向图的最大匹配问题的DNA分子生物算法 ,通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离 ,依据分子生物学的实验手段 ,算法是有效并且可行的

引用

页码：820 / 823

页数：4

共 6 条

[1]

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

[2]

DNA solution of computation problems. Lipton R J. Science . 1995

[3]

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

[4]

DNA computing on surface. Liu Q H,Wang L,Anthony G F,et al. Nature . 2000

[5]

Molecular Biology. Turner P C,McLennan A G,Bates A D,et al. . 2001

[6]

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

← 1 →