一种最大团问题的Tile自组装高效模型

作     者：周旭 周炎涛 欧阳艾嘉 李肯立 Zhou Xu;Zhou Yantao;Ouyang Aijia;Li Kenli

作者机构：湖南大学信息科学与工程学院长沙410082 嘉兴学院数理与信息工程学院浙江嘉兴314001 湖南大学电气与信息工程学院长沙410082 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2014年第51卷第6期

页      面：1253-1262页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金重点项目(61133005) 国家自然科学基金项目(61173013 61202109 61070057) 湖南省教育厅项目(08D092) 湖南省杰出青年基金项目(12JJ1011) 浙江省教育厅科研计划项目(Y201226110) 浙江省自然科学基金项目(LY12F02019) 

主　　题：DNA计算 Tile自组装模型 最大团问题 NP完全问题 并行计算 

摘      要：Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现:模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n^2n,求解成功率由0.5n0增加至0.5n^0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.