| 图的最小顶点覆盖问题的质粒DNA计算模型 |
| |
| 引用本文： | 王淑栋,刘文斌,许进.图的最小顶点覆盖问题的质粒DNA计算模型[J].华中科技大学学报(自然科学版),2004,32(11):59-61. |
| |
| 作者姓名： | 王淑栋 刘文斌 许进 |
| |
| 作者单位： | 华中科技大学,控制科学与工程系,湖北,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金资助项目 (6 0 2 74 0 2 6,6 0 174 0 4 7) |
| |
| 摘 要： | 给出了图的最小顶点覆盖问题的质粒DNA算模型及其实现算法．算法的时间复杂性是O(q)，编码最小覆盖问题所需的核苷酸片段种类为n，其中n，q分别是图的规模和边数．在算法中，所用酶的种类也等于图的规模．而且，算法不需要复杂的单链DNA自身退火反应和PCR扩增．
|
| 关 键 词： | 顶点覆盖问题 最小覆盖 时间复杂性 实现算法 片段 编码 计算模型 质粒DNA 单链DNA 核苷酸 |
| 文章编号： | 1671-4512(2004)11-0059-03 |
| 修稿时间： | 2003年12月2日 |
A DNA computing model for the minimal covering by plasmids |
| |
| Wang Shudong Liu Wenbin Xu Jin Wang Shudong Lect., Dept,of Control Sci. & Eng.,Huazhong Univ. of Sci. & Tech.,Wuhan ,China..A DNA computing model for the minimal covering by plasmids[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2004,32(11):59-61. |
| |
| Authors: | Wang Shudong Liu Wenbin Xu Jin Wang Shudong Lect Dept of Control Sci & Eng Huazhong Univ of Sci & Tech Wuhan China |
| |
| Institution: | Wang Shudong Liu Wenbin Xu Jin Wang Shudong Lect., Dept,of Control Sci. & Eng.,Huazhong Univ. of Sci. & Tech.,Wuhan 430074,China. |
| |
| Abstract: | A DNA computing model and algorithm for the minimal covering problems by plasmids were presented. Time complexity of the algorithm was O(q), the number of kinds of short oligonucletides needed to encode the minimal covering problem was n, where n, and q were the size and edge of the graph respectively. In the algorithm, the number of enzyme was equal to the size of the graph. There was no tangled self-annealed single-stranded DNA or PCR amplification step. |
| |
| Keywords: | DNA computing minimal covering problem NP-complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
