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

• 作者: 吴帆 周旭 李肯立 罗兴 黄鑫
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: DNA计算 自组装 并行计算 NP完全问题 最大团问题
• 年，卷（期）: 2013,（3）
• 所属期刊栏目: 算法理论
• 页码范围: 666-675
• 页数: 10页
• 分类号: TP301.6
• 字数: 5670字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学信息科学与工程学院	130	931	16.0	22.0
2	周旭	湖南大学信息科学与工程学院	14	149	6.0	12.0
3	吴帆	湖南大学信息科学与工程学院	5	48	3.0	5.0
4	黄鑫	湖南大学信息科学与工程学院	16	41	3.0	6.0
5	罗兴	湖南大学信息科学与工程学院	2	28	2.0	2.0