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

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

The Molecular Algorithm of The Matching Problem Based on Plasmid DNA

Given an undirected graph, the maximum matching problem is to find a subset of mutually non-adjacent edges having the largest number. This problem is a NP-complete and has no effective method. Adleman introduced firstly the DNA computing in 1994, with which the NP-complete problems are likely to be solved. DNA-based algorithm simulates molecular biology structure of DNA by means of molecular biology technological computation. The plasmid DNA contains a specially inserted series of DNA sequence segments, each of which is bordered by a characteristic pair of restriction enzyme sites, the DNA sequence segments of this series were used to represent the vertices of the graph. The solution is reached by applying enzymatic and gel electrophoresis. The DNA solution to the maximum matching problem of an undirected graph based on the plasmid is introduced. On the basis of the experimental method of bio-molecular, the algorithm is an effective and feasible method.