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

摘要：

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

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

所属期刊栏目：54

分类号：O1(数学)

资助基金：国家自然科学基金重点项目60533010;家自然科学基金重点项目30670540;60874036;60503002;国家高技术研究发展计划863计划2006AA01Z104;哈尔滨工业大学校科研和教改项目20070001020;教育部人文社会科学规划项目20060400344

在线出版日期：2010-04-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：3913-3919