文献类型：期刊文章

作　　者：许进[1] 李三平[2] 董亚非[1] 魏小鹏[3]

机构地区：[1]华中科技大学分子生物计算机研究所,武汉430074 [2]陕西师范大学数学与信息学科学院,西安710062 [3]大连大学先进设计制造中心,大连116622

出　　处：《科学通报》

年　　份：2004

卷　　号：49

期　　号：4

起止页码：299-307

语　　种：中文

收录情况：BDHX、BDHX2000、CAS、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、JST、MR、RCCSE、WOS、ZGKJHX、核心刊

摘　　要：经典的粘贴DNA计算模型采用单、双链混合型DNA分子编码, 其生物操作具有无需DNA链的延伸、无需生物酶以及DNA链可重复使用等优点, 已经受到不同学科学者的关注. 在经典模型的基础上, 进行一定的扩展与完善, 必对DNA计算机的研究有良好的贡献. 基于此, 对粘贴DNA计算机模型进行了较为深入的研究: (1) 提出了基于粘贴模型的矩阵表达模型; (2) 对经典粘贴模型应用于图与组合优化等方面的研究成果给予综述, 诸如集合覆盖问题、图的顶点覆盖问题、图的Hamilton路与圈问题、图的团与独立集问题、图的生成树与Steiner树问题等; (3) 给出了基于粘贴模型的图的同构问题的算法.

关 键 词：DNA计算机 粘贴模型 K-进制粘贴模型  组合优化问题 矩阵表达模型  NP-完全问题

分 类 号：TP301.6]