The Maximum Matching Problem Based on Self-Assembly Model of Molecular Beacon

摘要

The maximum matching problem is a famous NP-complete problem. Some scholars also have given many algorithms using DNA computing. Its algorithm complexity is over n. Based on the special hairpin structure of the molecular beacon, this paper gives a new tile-the molecular beacon tile, and it has a simple structure, strong specificity, low rate of wrong solutions. Firstly, all combinations of arcs are set in the graph G map for binary sequences. Secondly, the self-assembled model of molecular beacon is applied to verify whether each combination is the matching of the graph G. Finally, gel electrophoresis is used to look for maximum matching in all matchings. This algorithm uses massive parallelism of the self-assembled model to reduce complexity to Theta(n).