论文部分内容阅读
近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透和相互促进。随着计算机技术和分子生物技术的迅速发展，DNA计算作为一种新兴的交叉学科已经成为当今研究的热点。
图论中的许多问题都是组合优化问题，也是NP完全问题。目前有关图论中许多问题，如Hamilton路、最大团、最小覆盖、图的顶点或边的着色等问题，都通过建立DNA计算模型得以有效求解和发展，同时也倍受学者们的关注和研究。本文主要针对图的一类控制(支配)集问题展开了DNA计算模型的研究。具体有以下几方面的工作：
①介绍了DNA计算产生的生物背景、发展现状、DNA计算的数学理论、生物学基础以及DNA计算的机理，并对近年来有关DNA计算的研究成果进行了综述。
②建立了基于图论中最小独立控制集问题的DNA表面模型，并进行了实例仿真，验证了算法的可行性和有效性。
③构建了图论中的最小控制集、全控制集、独立控制集、连通控制集、完美控制集、约束控制集、双控制集、k控制集等NP完全问题的DNA粘贴模型，并证明了在DNA计算模型下，它们的算法时间复杂度是多项式阶的，并通过实例仿真对算法进行了可行性的验证。
最后，本文对全文进行了全面的总结，并展望今后继续研究的方向。