论文部分内容阅读
给定无向图，图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者，这个问题是著名的NP－完全问题。1994年Adleman博士首次提出用DNA计算解决NP－完全问题，以编码的DNA序列为运算对象，通过分子生物学的运算操作解决复杂的数学难题，使得NP－完全问题的求解可能得到解决。提出了基于质粒DNA的无向图的最大匹配问题的DNA分子 生物算法，通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离，依据分子生物的实验手段，算法是有效并且可行的。