Some Applications And Formal Semantics Of DNA Computing

Since computer appeared, it has become a very important tool to help people solve allkinds of computable problems. For NP-hard problems, with the scale of problemincreasing, the space and time which computing costs will increase surprising rapidly.The power of electronic computer can not meet the requirement because of therestriction of hardware device and serial instruction executing principle. DNAcomputing is a new computing paradigm by which DNA strands are encoded toexpress data and be processed by biochemical reactions. The character of DNAcomputing make it has the advantages of massive storage and parallelism. It is anatural computing method to solve NP-hard problems. In this dissertation, hairpinstructure DNA molecular are used to express the constraints of stack bottom, a methodfor stack designing based on hairpin structure molecular is proposed. k-armedmolecular are used to construct weighted graph and to solve shortest path problem.DNA-GA combined neural network is used for nondestructive quantitative analysis ofthe concentration of paracetamol and caffeine as active principles ofcompoundparacetamol and diphenhydramine hydrochloride powder. And the formalsemantics of some basic biological operations used in DNA computing are described.The content as follows:1. Design stack data structure based on hairpin structureData structure is an important problem in computer science. It is the basis of algorithmdesigning and information processing. DNA computing must have the capability toorganize and store data just as electronic computer for the purpose of practicalapplication. Stack is an important data structure that data only can be inserted ordeleted at the top of the stack. A method for stack designing based on DNA computingis proposed. Hairpin structure molecule is used to design stack. The circle part is usedto be the bottom of stack. The double strand part is encoded as data. Because differentrestriction endonucleases has different recognition site and cut site, two kinds ofrestriction endonucleases are used for push and pop operation. The encoding method isdescribed in detail. Then the initial operation, push and pop operation are alsodescribed. Some biological operations are introduced. The research can help to find a effective method for DNA computing to be used for data and information organization,extend the application field and help DNA computing more close to be computing toolin practice just like electronic computer.2. Shortest path problem for weighted graph is a very important problem, and haswidely application in practice. At the same time, it is a kind of NP-hard problem.Conventional algorithms need massive calculation. Especially when the problem scaleis large, it needs a long time to find the probable solution. The advantages of massstorage of the DNA molecule as well as the mass parallelism make DNA computing tobe a good method for NP-hard problems. Because k-armed molecule has sticker end, itcan be used as a bridge to connect each vertex of a graph. A method for weightedgraph building based on k-armed molecule is proposed. Weight of an edge is encodedas a double strand with a corresponding length. By encoding for vertex and edges of agraph, sticker operations are used to find the shortest path. The encoding method isdescribed in detail. Then DNA algorithm for shortest path problem and the formaldescription are described. A method to shorten the length of the code of weight isproposed. The molecular structure used in this method is stable. It can help to reducethe error during biological reactions. The biological operatation is common and easyto operate. So the method we propose is feasible in practice.3.Quality monitoring of drugs is an important problem during the process ofproduction and circulation. Nondestructive quantitative analysis is a good method forquality monitoring of drugs. In this dissertation, DNA-GA combined neural network isused for nondestructive quantitative analysis of the components of drugs. Data of NIRregion are selected based on DNA-GA and RBF neural network is used to buildanalysis model. This method is used to analyze the two components of compoundparacetamol and diphenhydramine hydrochloride powder. The testing result showsthat the method is feasible, the analysis model can predict the content of thecomponent well. The precision and running speed are all improved after regionselection based on DNA-GA .4. It is necessary for the computing model to have an accurate method to explain it.Formal method gives a way to define a computing model and its component withaccurate mathematic form. The formal semantics of DNA strand and some basic biological operations are described. This can help to give a precise definition andunderstanding about DNA computing model, and give a reference for formaldescriptions and semantics research in DNA computing.DNA computing is a new computing paradigm. There are still many problems in thisfield need to be researched both in theory and application. The content of thisdissertation give feasible method for data organization and application. And it make anattemp for semantic description of DNA computing.