一种基于分治的三维匹配问题DNA计算算法

• 作者: 乐光学 周旭 李肯立 杨志邦
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: DNA计算 三维匹配问题 分治策略 NP完全问题
• 年，卷（期）: 2010,（8）
• 页码范围: 1831-1836
• 分类号: T18
• 字数: 6100字
• 语种: 中文

摘要

本文基于Aldeman-Lipton模型的生物操作与粘贴模型的解空间,提出一种三维匹配问题的DNA计算新模型;同时基于此模型和传统计算机中分治策略,提出一种求解三维匹配问题的DNA计算新算法.将提出的算法与已有文献结论的对比分析表明:本算法将穷举算法中的DNA链数从0(2n)减少至0(2nη)≈0(1.414n),同时生物操作数由O(n2)减少至O(15n+30q),测试试管数由所需的O(n)减少至O(1),最大链长由0(15n+45q)减少至O(15n/2+45q).因此,本算法理论上在试管级生化反应条件下能将求解三维匹配问题的规模从67(267≈1022)提高到134(67×2=134).同时,与传统的穷举搜索算法相比,该算法具有高效的空间利用率及容错技术的优点.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨志邦	湖南大学计算机间与通信学院	13	105	7.0	9.0
2	李肯立	湖南大学计算机间与通信学院	130	931	16.0	22.0
3	周旭	嘉兴学院数学与信息工程学院	18	115	7.0	10.0
4	乐光学	嘉兴学院数学与信息工程学院	67	251	9.0	13.0