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

作　　者：杨静[1] 张成[1] 许进[1] 刘向荣[1] 强小利[1] 

机构地区：[1]北京大学信息科学技术学院,高可信度软件技术教育部重点实验室,北京100871

出　　处：《中国科学：信息科学》2010年第8期1078-1085,共8页Scientia Sinica(Informationis)

基　　金：国家自然科学基金重点项目(批准号: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完全问题 环化酶 磁珠 

分 类 号：O242.1[理学—计算数学]