| DNA编码问题及其复杂性研究* |
| |
| 引用本文： | 张凯,耿修堂,肖建华,张勋才.DNA编码问题及其复杂性研究*[J].计算机应用研究,2008,25(11):3264-3267. |
| |
| 作者姓名： | 张凯 耿修堂 肖建华 张勋才 |
| |
| 作者单位： | 华中科技大学,控制科学与工程系,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金重点资助项目(60533010, 30670540);国家“863”计划资助项目(2006AA01Z104) |
| |
| 摘 要： | 高质量的DNA编码可以避免DNA分子间的非特异性杂交，提高DNA计算的有效性和可靠性。首先对DNA编码的约束条件进行归类，分析了各编码约束对编码质量的影响；然后研究了编码质量、编码数量、序列长度与DNA计算可靠性、有效性、可扩充性之间的关系；最后通过类比DNA编码问题和图的独立集问题，说明了求解最大DNA序列集合问题是NP完全的。
|
| 关 键 词： | DNA计算 DNA编码设计 组合优化 |
DNA sequence design problem and complexity analysis |
| |
| ZHANG Kai,GENG Xiu tang,XIAO Jian hu,ZHANG Xun cai.DNA sequence design problem and complexity analysis[J].Application Research of Computers,2008,25(11):3264-3267. |
| |
| Authors: | ZHANG Kai GENG Xiu tang XIAO Jian hu ZHANG Xun cai |
| |
| Affiliation: | (Dept. of Control Science & Engineering, Huazhong University of Science & Technology, Wuhan 430074, China) |
| |
| Abstract: | High quality DNA sequences can prevent the interference between different DNA molecules, and improve the reliability and effectiveness of DNA computation. At first, classified DNA constraints, and analyzed the influence of constraints on the quality of DNA sequences. Then the paper studied the relationship between DNA sequence and the efficiency of DNA computing. Finally, the paper carried on the analogy to DNA sequence design problem and graph independent set problem, and proved the maximum DNA sequences set problem was a NP complete problem. |
| |
| Keywords: | DNA computing DNA sequences design combinatorial optimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
