Research On Computational Model Of DNA Self-Assembly And Its Application In Matching Problem

DNA self-assembly computing becomes a potential solution to solve the NP hard problem and the combinatorial optimization problem because of the massive storage capacity,high degree of parallelism and ultra low energy consumption.These three powerful advantages make it come to the fore in a variety of different algorithms.Compared to the traditional method,DNA computing by self-assembly can make up the deficiency of the traditional calculation in computational time by the method of space for time.It is these characteristics using the DNA self-assembly calculation,This paper solves the maximum matching problem of general graph and the optimal working arrangements by these characteristics of the DNA computing by self-assembly.The main work of this paper is as follows:First,an algorithm idea is given to solve the maximum matching problem of general graphs based on mathematical model of DNA self-assembly computing.Then we design different types of DNA Tile for four subsystem which are seed system,matching system,detection system and output system according to the algorithm idea.A graph with 6 vertices and 12 edges is proposed to explain the process of algorithm self-assembly and the processing method of the final solution,and the algorithm complexity of the model is analyzed.The example shows that the type of Tile uising in the system is a constant,and the problem can be solved in linear time.Secondly,this paper shows an algorithm of the DNA self-assembly with the maximum matching of the bigraph to solve the optimal working arrangement problem.The solution of the problem is converted into the solution of the maximum matching of bigraph by mapping the staff information and task information to the binding domain of DNA Tile.The algorithm proposed by a simple example and gives a detailed description of the steps of the algorithm,and gives the analysis of the complexity of the algorithm.Finally,we summarize the full text and prospect.The shortcomings of the proposed method of this paper are analyzed and discussed.And the future research area is determined.