基于质粒dna匹配问题的分子算法

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