The Applications Of Residue Number And PCR In DNA Computing

Although the electronic computer has achieved a great success in the scientific re-search and the engineering practice,the carrying capacity and the processing power ofthe chip restrict the electronic computer to maintain long-term growth of the computationspeed. As a new computing paradigm, DNA computing has attracted a considerable at-tention. The main difficulties in DNA computing are as follows. The problem of DNAcoding is difficult to be solved and it is hard to coordinate the relationship between the cod-ing quantity and the coding quality. The tedious operations along with the imperfectnessof biochemical reactions involved in computing process may have a negative effect on thecomputing result. In addition, for the NP-complete problem, the exponential relationshipbetween the size of the problem and the volume of DNA molecules required for computingrestricts the capability of DNA computing. Focusing on these problems, we try to do somesort of research in the following several ways in this dissertation.For the problem of DNA coding, a method is presented based on micro-genetic al-gorithm. The definition and the constraints in DNA coding are introduced including thecomputational procedure on the related parameters. A multi-objective optimizing model isconstructed by mapping the H-class constraints into single DNA codeword and introducinga share function between different codewords, which make it possible to solve the problemof DNA coding by micro-genetic algorithm. In concrete solving process, several operators,such as anti-codon operator, segmenting crossover operator, maximum-minimum operatorand inversion operator, are introduced. Compared with the existed results, the non-uniformdistribution of the quality of codewords can be avoided and the population size is approxi-mately 2 times of the volume of DNA codewords which make the computation cost low.In order to decrease the complexity of the DNA coding, the residue number system isintroduced into DNA arithmetic operation. Based on the Adleman-Lipton model, the DNAcoding scheme of DNA residue arithmetic operation is proposed with the DNA algorithmfor binary arithmetic operation. And then based on the 4-moduli set P={2ⁿ⁺¹+2ⁿ-1,2ⁿ,2ⁿ-1,2ⁿ+2^n-1-1} and n-moduli set P={2^m+1+2^m-1...2^m-1-1} the DNA algorithms for the residue arithmetic operation are presented respectively. Theparallelism of computing is n and the volume of DNA molecules required for computingin residue number system is n1 of the volume in binary system. Because of the carry-freeproperty of the residue arithmetic operation, the parallelism of DNA computing can beexploited and the steps of DNA molecular manipulations can be reduce which contribute toerror control.For fear of the negative effect of the imperfectness of biochemical reactions involvedin computing process on the computing result, the PCR is used as the main manipulation torealize DNA computing process and the computing operation model in which the restrictionenzyme is unnecessary is constructed based on PCR. Based on the model, the DNA codingscheme and DNA algorithms in logic and arithmetic operation are presented. After thatfor a typical NP-complete problem, the minimum vertex cover problem, a DNA algorithmwith corresponding DNA coding scheme is presented. The application of PCR can keepthe computing process simple and reliable, and the separation operation is only related tothe length of DNA which make the separation operation more accurate.For the problem of exponential explosion in DNA computing, the construction ofsimple genetic algorithm through PCR is presented. In the genetic algorithm, the geneticoperators, such as crossover operator, mutation operator and selection operator, are con-structed through PCR operation and the fitness function in the genetic algorithm is mappedinto the length of double DNA strands. Moreover the genetic algorithm constructed byPCR is used to solve the minimum vertex cover problem. The DNA algorithm and theresult comparison are presented with the DNA coding scheme for the corresponding bitstring. Compared with other operation methods, it is more practical to construct geneticalgorithm by PCR. Because it is unnecessary to generate the solution space, the applicationof PCR can avoid the problem of exponential explosion.