图的最大团与最大独立集粘贴DNA计算模型

强小利1范月科2许进1

1.华中科技大学; 2.北京大学;

摘要：

粘贴模型(sticker model)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.

关键词：DNA计算、粘贴模型、最大团问题

所属期刊栏目：33

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60533010,60910002,60974112,60971085,30970969;国家"八六三"高技术研究发展计划项目基金2009AA012413;中国教育部博士点基金20070001020

在线出版日期：2010-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：305-310