| DNA缩短法计算模型求解最大独立集问题 |
| |
| 引用本文： | 张成,杨静,许进,赵东明.DNA缩短法计算模型求解最大独立集问题[J].科学通报,2009,54(24):3913-3919. |
| |
| 作者姓名： | 张成 杨静 许进 赵东明 |
| |
| 作者单位： | 北京大学信息科学技术学院, 高可信度软件技术教育部重点实验室, 北京 100871
† 同等贡献 |
| |
| 基金项目： | 国家自然科学基金重点项目(批准号: 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计算模型的可行性, 利用其求解了一个最大独立集问题的实例.
|
| 收稿时间： | 2009-02-13 |
|
| 点击此处可从《科学通报》浏览原始摘要信息 |
| 点击此处可从《科学通报》下载免费的PDF全文 |
|
