DNA缩短法计算模型求解最大独立集问题

CORC > 北京大学 > 信息科学技术学院

	DNA缩短法计算模型求解最大独立集问题
	张成 ; 杨静 ; 许进 ; 赵东明
刊名	科学通报
	2009
关键词	NP完全问题反向PCR 线性单链DNA环化 DNA长度逐步减短法
英文摘要	提出了一种基于环形DNA缩短法的新型计算模型.该模型可以求解n个顶点m条边的图的最大独立集.算法的时间复杂度是O(n+m).随着问题规模的增大,计算所需的试管数量呈线性增长.在计算模型的生物操作中,有两个主要技术:DNA分子内环化和DNA长度逐步缩短.结合反向PCR(聚合酶链式反应),磁珠吸附和环化酶催化等多种方法,在求解步骤中,DNA分子的结构在线性双链DNA(dsDNA)、线性单链DNA(ssDNA)和环形单链DNA之间进行循环变化.利用环形DNA分子的结构特点,在计算过程中避免了DNA分子间重组.为了证实该DNA计算模型的可行性,利用其求解了一个最大独立集问题的实例.; 中文核心期刊要目总览(PKU); 中国科技核心期刊(ISTIC); 中国科学引文数据库(CSCD); 0; 24; 3913-3919
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/23252]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	张成,杨静,许进,等. DNA缩短法计算模型求解最大独立集问题[J]. 科学通报,2009.
APA	张成,杨静,许进,&赵东明.(2009).DNA缩短法计算模型求解最大独立集问题.科学通报.
MLA	张成,et al."DNA缩短法计算模型求解最大独立集问题".科学通报 (2009).