DNA编码问题和其复杂性研究.pdf

第25卷第11期 计算机应用研究 V01．25No．11 Researchof NOV．2008 2008年11月 Application Computers DNA编码问题及其复杂性研究 张凯，耿修堂，肖建华，张勋才 (华中科技大学控制科学与工程系，武汉430074) 摘要：’高质量的DNA编码可以避免DNA分子间的非特异性杂交，提高DNA计算的有效性和可靠性。首先 对DNA编码的约束条件进行归类，分析了各编码约束对编码质量的影响；然后研究了编码质量、编码数量、序列 长度与DNA计算可靠性、有效性、可扩充性之间的关系；最后通过类比DNA编码问题和图的独立集问题，说明 了求解最大DNA序列集合问题是NP完全的。 关键词：DNA计算；DNA编码设计；组合优化 中图分类号：TP301．5 文献标志码：A 文章编号：1001-3695(2008)11—3264-04 DNA and designproblemcomplexityanalysis sequence ZHANG Xun-cai Kai，GENGXiu—tang，XIAOJian·hua，ZHANG 430074，China) (Dept．ofControlScienceEngineering，HuazhongUniversityofScience＆Technology，Wuhan can theinterferencebetweendifferentDNA therelia- DNA molecules，and Abstract：Highqualitysequencesprevent improve DNA theiniluenceofconstraintson andeffectivenessofDNA first，classifiedconstraints，and bility computation．At analyzed DNA the studiedthe betweenDNA andthe ofDNAeom- the of efficiency quMity sequences．Thenpaper relationship sequence carriedonthe toDNA and set analogy design graphindependentproblem，and puting．Finally，thepaper sequenceproblem themaximumDNA set wasaNP problem． proved sequencesproblem complete Keywords：DNA design；combinatorialoptimization