Applications Of DNA Computing To NP Problems And Its Program Simulation

DNA computing is a new method of simulate biology moleculeDNA-structure and rely molecular biology technology to computing. It setup the precedent of chemistry as a computing tool, and it has a splendidfuture.Adleman first published his method of DNA computing on science in1994, using DNA computing solved the problem of Hamilton path in graphtheory, and got success in experiment. The DNA computing is a completenew concept. It has break through the bondage of traditional structure ofcomputer. The basic theory of DNA computing is: Encode informationusing the special structure of DNA double helix and nucleotides match rule,and mapping the object to operating to DNA molecules strands, and underthe control of enzyme build a data pool, then use the rules appointedmapping the DNA molecules strands to a high speed parallel data computingbio-chemistry procedure. At last, using molecule biology technology such aspolymerization chain reaction (PCR), ultrasonic degradation, hybridization,clone, trap, molecules purify, electrophoresis, magnet-bead separate and soon, detect the result of the reaction. So the core matter is let the encodedDNA strands as input, and in test tube or other carrier take place specificbio-chemistry reactions controlled, then achieve the computing procedure togive the whole result space after the reaction. The most advantage of DNAcomputing is that it makes the best use of the info-code in abundant DNAmolecules, and the jillion of the parallel. So the next generation computer useDNA computing model as background which called DNA computer willcertainly have huge storage and a fastest running speed. In DNA computersystem, the codes in DNA molecules can be look as data in memory, afterthrough the enzyme work towards DNA molecules to achieve some kinds ofreaction instantly, the code could be transformed from one to another. If takethe code before the reaction then the code after reaction look as the result.Then DNA computing is a progress that by the abundant exact undercontrolled chemistry reaction towards DNA helix including tag, amplify ordestroy original strands to achieve different computing progress.The efforts in this paper mainly include the following two contents:1. Give no-direction weight Hamilton path problem and knight problemcorrespond DNA computing model algorithm.(1). No-direction weight Hamilton path problem. Hamilton path is aboutconnected chart, has a path routed every vertex once and only once we call itHamilton path. If has a Hamilton path that can go back to the vertex beginwe call it Hamilton loop, while the contrast we call Hamilton path. If everyedge give correspond weight the problem become the Hamilton path withweight. Adleman's experiment research the direction Hamilton path problemwith no weight. While we discuss in this paper is about Hamilton path withweight, so we have to treat two things about the weight and the direction.And the main problem is to solve the problem of weight, as to the directionwe could give a transform of a no-direction edge to two direction edge. Toweight we take use of different GC content to represent different weight, letheavy weight edge with higher GC content or have the lower;As to match ofGC it form a three covalent bond has a higher divide-temperature ( Tm )compared with the two covalent bond of AT, so we could detect the path withlower weight easily according to their different divide-temperature.We adopt the method of stick short piece to random produce all path, detectthe result we adopt the way of pyrogenation and PCR take place together,first metamorphic unit have lower weight and be amplified first, and thispoint solve the problem of weight express and separate. This kind ofexpression of weight has a good elicitation meaning towards such problems.(2). Knight Problem is another old problem, it describe in a n×nchessboard, place count n knights, let them can not assault each other;Therule they assault each other is that they lie in the same row column orcater-corner. It is also call chess's 'eight-queen' problem.In this paper we use stick-model, stick-model use DNA strands as theinformation carrier, the computing relay on the Watson-Crick matching rule,it is reusable in theory. We give a improvement on stick-model, introducepart-complement entire-complement and asterisk operator, give a specialdesign of encode, successfully avoid conflict on specific grid, also ensuremassive parallel operating and automatic requirement.Part-complement is about contrast to original stick short piece'sentire-complement anneal to '1' add further meaning, it is only anneal to partof storage strands' sub-strand;In another word we make the stick short pieceto more shorter information unit.This kind of combination problem and other problems which could beexpressed by matrix, we all could model and analysis in suchpart-complement and entire-complement.2. According the two problems we give the simulation of DNA computingalgorithm recur to database management system, and research to large scale.Simulation by database we take ORACLE PL/SQL as programming tool.As to this kind of large database management system it providesdevelopment tools and some useful functions and other data structure, it isconvenience to manage data. To this two problems we could use least code toachieve the function require. Here only take one select sentence. It couldeasily extend to large scale problem make use of hard disk could be expandinfinite.We discuss dodecahedron ichnographic Hamilton path problem withweight. Find all Hamilton path and loop, also the path with lowest weight.The algorithm is expand every vertex in every level, do not expand thevertex have been routed, and the method is like DNA computing is a processof exhaust. After the process we could easily remove unexpected results,only preserve the results with lowest weight and end at the vertex required.As to knight problem we use the method of data set Descartes product, bythe form of n sets' Descartes product we could exhaust all combination,while exhaust all results we remove the one not qualify the three constrain.And the method has high efficiency in database system. Here we successsolve the order with 8 9 10 11 12 14 16.The efforts of this paper not only including field of DNA computing butalso about traditional computer technology intersect with DNA computer.Not only give some good method in DNA computing, also add DNAcomputing theory to traditional method. They are all meaningful things.