A DNA algorithm for maximal matching problem

This paper proposes a DNA algorithm based on biological technology for the maximal matching problem. Maximum matching problem is a typical combinatorial optimization problem. The main idea of the algorithm is draw the line graph to observe adjacent edges firstly, then use the direct proportional length-based DNA strands to encode the given weighted graph edges. All data pool generated in a test tube. Then the result comes out by a series of biological reaction and computation such as denaturation, anneal, Polymerase Chain Reaction, enzyme-cutting reaction, gel electrophoresis. The maximal matching of the graph will find. Finally this article discusses the feasibility of this algorithm and confirmed its effectiveness by an example.