子集和问题的O(1.414n)链数DNA计算机算法

• 作者: 姚凤娟 李仁发 李肯立 许进
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: DNA计算 子集和问题 分治法 并行处理 NP完全问题
• 年，卷（期）: 2007,（11）
• 所属期刊栏目: 研究论文
• 页码范围: 1947-1953
• 页数: 7页
• 分类号: TP301
• 字数: 7933字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.11.007

摘要

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李仁发	湖南大学计算机与通信学院	468	4582	30.0	44.0
2	许进	华中科技大学分子生物计算机研究所	117	2149	25.0	39.0
3	李肯立	湖南大学计算机与通信学院	130	931	16.0	22.0
7	姚凤娟	湖南大学计算机与通信学院	3	73	3.0	3.0