| 基于环形DNA分子的一种求解最大集团的计算模型 |
| |
| 引用本文： | 杨静,张成,许进,刘向荣,强小利.基于环形DNA分子的一种求解最大集团的计算模型[J].中国科学：信息科学,2010(8). |
| |
| 作者姓名： | 杨静 张成 许进 刘向荣 强小利 |
| |
| 作者单位： | 北京大学信息科学技术学院;高可信度软件技术教育部重点实验室; |
| |
| 基金项目： | 国家自然科学基金重点项目(批准号:60533010); 面上项目(批准号:30670540,60874036,60503002); 国家高技术研究发展计划(批准号:2006AA01Z104); 国家教育部博士点基金(批准号:20070001020); 中国博士后科学基金(批准号:20060400344)资助 |
| |
| 摘 要： | 文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.
|
| 关 键 词： | DNA计算 环形DNA分子 NP完全问题 环化酶 磁珠 |
| 本文献已被 CNKI 等数据库收录！ |
|
