DNA缩短法计算模型求解最大独立集问题  

作　　者：张成[1] 杨静[1] 许进[1] 赵东明[1] 

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

出　　处：《科学通报》2009年第24期3913-3919,共7页Chinese Science Bulletin

基　　金：国家自然科学基金重点项目(批准号:60533010);国家自然科学基金面上项目(批准号:30670540;60874036;60503002);国家高技术研究发展计划(批准号:2006AA01Z104);教育部博士点基金(批准号:20070001020);中国博士后科学基金(批准号:20060400344)资助项目

摘　　要：提出了一种基于环形DNA缩短法的新型计算模型.该模型可以求解n个顶点m条边的图的最大独立集.算法的时间复杂度是O(n+m).随着问题规模的增大,计算所需的试管数量呈线性增长.在计算模型的生物操作中,有两个主要技术:DNA分子内环化和DNA长度逐步缩短.结合反向PCR(聚合酶链式反应),磁珠吸附和环化酶催化等多种方法,在求解步骤中,DNA分子的结构在线性双链DNA(dsDNA)、线性单链DNA(ssDNA)和环形单链DNA之间进行循环变化.利用环形DNA分子的结构特点,在计算过程中避免了DNA分子间重组.为了证实该DNA计算模型的可行性,利用其求解了一个最大独立集问题的实例.

关 键 词：NP完全问题 反向PCR 线性单链DNA环化 DNA长度逐步减短法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]