Research On Theory,designation And Application Of DNA Computing Model

DNA computing is a new computational pattern using DNA molecules as data and massive parallel biochemical reactions as data processing tool.Since Aldeman successfully employed DNA molecules to solve the Hamilton problem with seven vertexes in 1994,DNA computing,as a new academic studying field,draws many researchers'wide interest and study for its massive storage capacity,highly parallel computing power and other advantages.The development in DNA computing critically depends on the level of biochemical technology.At present,many DNA computing models are set up for a special problem,and it is difficult to solve other problem without any changes or a small amount of modification.So it is not as universal as an electronic computer.Nearly all DNA computing models research feasible solution or optimal solution in all possible solution space.So,its highly parallel computing power seriously decline with the growth solution space and lost its computing merit.At present,the detection of the solution is based on conventional biological monitoring methods,such as electrophoresis and PCR amplification.So the error rate is high,which has become an important obstacle to the development of DNA computing.This paper put forward a new based on FPGA?field programmable gate array and the field programmable gate array?bionic parallel calculation model of DNA computing model?DNA electronic computing model,DEM?referring to biological DNA computing parallel information processing theory.Three aspects mainly including the basic theory,hardware implementation and the application of 0-1 programming problem and graph theory sare studied.The main contents of this thesis are described as follows:?1?Stickers model,a typical DNA-based computing model,encode information through mixture of DNA single and double strand mixture:single strand is used to represent decimal number 0,and double chain is represent decimal number 1.The method of ecoding information is similar with electronic computer,and is universal.The stickers model is viewed as a bit-vertically operating machine,and seems to be a well-suited programming model for its in silico implementation by a field programmable gate array?FPGA?architecture.A novel generalized Turing machine?GTM?combining by a classical Turing machine with the sticker model of molecular computation has been proposed.GTM is a theoretical computing mdel,and does not rely on any biochemical thenology.It includes an ordinary single tape Turing machine,a finite write-only tape,and a special storage tape equipped a parallel read-write network,in which exist a topological mapping between the write-only tape and the storage tape to realize the massive parallel information processing.GTM can solve satisfiability problem in a polynomial time by trading time with space in parallel,and set cover problem can be sovled without modification in structure.Simulation experiment shows that the highly parallel computing capability and the universal merits in solving the NP-complete problems.?2?The main work is focused on its silico implementation by field programmable gate array?FPGA?architecture.The function in DEM is divided into hardware and software according to the complexity and scale of each function module.SOPC platform is used to complete the hardware design,and the software design is completed in the NiosII integrated development environment to achieve the command control.Logic memory units in FPGA of SOPC platform is employed to present information data similar with the DNA molecular in DNA-based computing model.Address decoder based on multi valued logic is propsed to implement parallel access logic mmemory units.Data generator is proposed to generate many different data at on time.Modification of scanning and addressing circuit in plasma display panel makes it can access a lot of display units in the addressing stage at the same time.So we can visually observe the solution space changes and the distribution of feasible solution or the optimal solution.These parts are designed as IP cored easily to transplant.Instruction system is realized by softwere in the Nios II implementation due to it is designed for sepecial different problems.?3?The application of DEM in solving graph theory is studed.It has been widely used in many fields of scientific research,such as the problem of the maximal clique problem,the Ramsey number,and so on.The hardware implementation of DEM is realized by the maximum clique problem in the graph.Soft core design for the instruction system and result analyzer of DEM is realized through software in the Nios II integrated development environment using C language software code.Address decoder,data decoder,etc,is built in SOPC hardware circuit.Finally,the soft core is downloaded to the target circuit board.The maximal clique and independent set problem are difficult problems in the graph theory,and are key algorithms for solving Ramsey?k,l?number problem.Classical Ramsey number is a NP complete problem.If the Ramsey?k,l?number is p,in order to reflect all possible information of p-order graphs,the solution space is2^C2p.Its exponential searching space makes it difficult to be sovle with traditional electronics computer.This paper introduces the algorithm of the maximal clique problem by DEM model.The thesis describes the algorithm of Ramsey?4,4?drawing idea from the bit sequence encoding method raised by professor Xu.From max?k,l?,the algorithm begans to generate solution space,and then delete all informal solutions according to the definition of Ramsey,test whether there is a sub-graph.Ramsey number is the number when there is sub-graphs in solution space.This paper provides a theoretical algorithm obtain the unknown Ramsey number greatly in the next step.?4?The application of DEM in military ammunition distribution path optimization problem is studied.The problem of satisfaction,the maximum clique problem,the set covering problem and the traveling salesman problem can be transformed into 0-1 programming problem.Therefore,the research on the 0-1 programming problem has a wide range of application value in practice.This paper introduces the mathematical model of the 0-1 programming model of the above problems,and designs the DEM solution method for solving the 0-1programming problem.Military ammunition distribution path optimization problem is the expansion of the traveling salesman problem.Timely,accurate and safe Delivery of ammunition to the needs of the armed forces is related to the outcome of the whole battle.The particularity of ammunition distribution path is analyzed,the calculation is carried out by DEM,and the complexity of the algorithm is analyzed.The superiority of the calculation model is verified in the calculation of the optimization problem of military ammunition supply line.