基于环形DNA分子的一种求解最大集团的计算模型

• 作者: 刘向荣 张成 强小利 杨静 许进
• 来源期刊: 中国科学(信息科学)
• 学科: 数学
• 关键词: DNA计算 环形DNA分子 NP完全问题 环化酶 磁珠
• 年，卷（期）: 2010,（8）
• 页码范围: 1078-1085
• 页数: 8页
• 分类号: O242.1
• 语种: 中文

摘要

文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.