论文研究 DNA编码问题及其复杂性研究.pdf

高质量的DNA编码可以避免DNA分子间的非特异性杂交，提高DNA计算的有效性和可靠性。首先对DNA编码的约束条件进行归类，分析了各编码约束对编码质量的影响；然后研究了编码质量、编码数量、序列长度与DNA计算可靠性、有效性、可扩充性之间的关系；最后通过类比DNA编码问题和图的独立集问题，说明了求解最大DNA序列集合问题是NP完全的。