最小顶点覆盖问题的DNA分子算法

• 作者: 许进 高琳
• 来源期刊: 系统工程与电子技术
• 学科: 工学
• 关键词: DNA计算 NP-完全问题 顶点覆盖问题 限制酶
• 年，卷（期）: 2004,（4）
• 所属期刊栏目: 软件、算法与仿真
• 页码范围: 544-548
• 页数: 5页
• 分类号: TP301.6
• 字数: 3996字
• 语种: 中文
• DOI: 10.3321/j.issn:1001-506X.2004.04.035

摘要

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP-完全问题.给出了基于分子生物技术的图的顶点覆盖问题的DNA算法.算法的关键是数学问题到DNA链的映射,对图中的项点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离.依据分子生物学的实验方法,提出的算法是有效和可行的.最后指出了该算法的优点、存在问题及下一步的研究方向.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	华中科技大学系统科学研究所	117	2149	25.0	39.0
2	高琳	西安电子科技大学计算机学院	43	810	16.0	28.0