基于自组装模型的最大团问题DNA计算算法

作     者：李肯立 罗兴 吴帆 周旭 黄鑫 Li Kenli;Luo Xing;Wu Fan;Zhou Xu;Huang Xin

作者机构：湖南大学信息科学与工程学院长沙410082 

基　　金：国家自然科学基金项目(61133005 61070057 61202109 61173013) 国家科技支撑计划基金项目(2012BAH09B02) 湖南省杰出青年基金项目(12JJ011) 

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

年 卷 期：2013年第50卷第3期

页      码：666-675页

摘      要：DNA计算在解决NP完全问题时,有着传统图灵机无法比拟的优势.但是随着DNA计算研究的不断深入,传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点.如何提高DNA计算结果的准确性在DNA计算研究中日显重要.针对NP完全的最大团问题,引入DNA自组装模型,提出了一种求解最大团问题的DNA计算算法.算法通过减少实验的操作步骤数,以降低生化解的错误率,给出了DNA分子的编码方案及结果检测的实验方法.算法设计的tiles种类为Θ(n+|E|),生化操作复杂性为Θ(1),其中n为图的顶点数,|E|为边数.与求解最大团问题的其他DNA算法的对比分析表明,本算法不仅明显提高了生化解的准确性,且算法的生化实验复杂度低,具有良好的实验操作性.

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203704158...