The Study Of Some DNA Computing Sticker Models

In the dissertation, several problems in graph and combinatorial optimization arestudied and discussed mainly from the point of sticker models and sticker systems. Thedetailed contents are as follows: The sticker system is a language generative mechanism based on stickingoperations and a DNA computation abstract model that follows Watson-Crickcomplementarity relation to anneal. In this dissertation, DNA computing models oftraveling-salesman problems are given out using the massive parallelism of stickersystem. After all, the built models are verified by an actual example. The minimal vertex-covering problem is a NP-complete problem, and may applywidely to molecular biology, schedule problem, error diagnosis, the balance of resumeand collection, the journey plan of oil tanker and switch theory. In the dissertation,DNA computing models of the minimal vertex-covering problems are studied andexplored using the theories of sticker systems. The restriction conditions of systems aremodified, and the double segments are defined as single strands when the incompletemolecules LRρ(V ) being designed. The joint shapes of left and right sticky ends areuniform and they are either the upper joint or the lower joint at the same time. Webelieve that if the double segments in LRρ (V ) are defined as arbitrary nonemptyforms, then the DNA sequence states may be added to 10 types. The detection problem is an important problem in DNA computing. In thedissertation, the detection problems are studied and discussed by building the DNAcomputing sticker model on surface of the minimal vertex-covering problems. Duringbuilding the model, the vertices and edges of graphs are denoted by a certain long IIIoligoncleotides; The strategy of double-color fluorescence marker is adopted whendesigning DNA sequences, and the final results are detected by adding thefluorescence reagents and fluorescence quenching molecules on the template strandssuch that fluorescence quenching occurs after the hybridization reactions of stickerstrings and template strands. DNA computing is fulfilled with several steps of biochemical experiments, andthe number of experiment steps will influence the precision and time of computationdirectly. The sticker model computes by controlling the denaturalization andre-denaturalization of DNA sequences according to the complementarity principle ofDNA molecules. In such computation, the whole sequence DNA molecules areinvolved in every operation of denaturalization and re-denaturalization, hence thenumber of experiment steps is important to the computing results of model. In thisdissertation, we introduce a new biologic molecule-PNA to sticker model, and attemptto reduce the number of experiment steps. PNA is a man-made biologic molecule andthe joint with DNA possesses the characters of fastness, high melt temperature,without electric charge and not being infection influenced by particle concentration.According to this property of PNA molecules, we design the memory strands andseparate probes using DNA molecules, and sticker string using PNA molecules.What's more, this paper show a DNA computing model of perfect matching problembased on sticker model. The difficulty of the model is controlling the denaturalizationtemperature.