Application And Implementation Of Generalized Molecular Computation Model

DNA computing is a new emerging field of high performance computing. Many Scholars have developed a lot of DNA computing models in30years. However, the existing models are mostly based on biological technology, which have many restrictions on the implementation. So a new generalized molecular computation model (GTM) based on Turing machine is introduced, which combines DNA computing with traditional computer model[11. The realization of this model is not dependent on biological technology. GTM includes a general Turing machine, a writing tape, a working tape and network, which contains a special topology mapping between writing and working tape. For its big storage and high parallelism inherited from DNA computing, it can solve NP complete problems by space complexity for time complexity.This paper can be divided into the three following parts:1. The part of preface. This paper describes the development of DNA computing and DNA computers, research status and research difficulties of DNA computing model.2. The introduction of background knowledge. Discuss the main theory and knowledge involved in the paper, including DNA computing, sticker model, Turing machine and NP complete problem. Then a molecular computation model is expressed, which is independent on biological technology, including the structure, formal definition and working process. This model is the core theory of the whole study.3. The application and implementation of GTM. The model is used to solve four NP complete problems, that is:set covering problem, satisfiability problem, half divided problem and0-1knapsack problem. The solving algorithm is designed and using instance and computer simulation to prove the validation of the algorithm.GTM shows its versatility to solve NP complete problems in polynomial time. The instance and simulation verifies the ability and advantage of the model to solve NP complete problems.