The Research On Coding Theory And Methods For DNA Computing

DNA computing is a new computational paradigm that uses DNA molecules as information storage materials and hybridization reactions as information processing operators due to massive parallelism and huge memory capacity. Computational codeword design is one of the crucial problems in DNA computing. From the perspective of molecular biology, the existence of codeword is attributed by the physicochemical properties of DNA sequence; Thermodynamic properties of DNA sequences govern the kinetics of hybridization and ligation. Therefore, this thesis focus on designing computational codeword based on physicochemical properties, as well as the thermodynamic properties of DNA sequences to make the molecular computation more reliable. The main research works are as follows:Besides the encoding problem of DNA computing, both the physicochemical properties of DNA molecule and the thermodynamics of hybridization are discussed in detail. Additionally, some usual calculation methods for the correlative thermodynamic parameters are also introduced.An optimized approach for generating a set of computational codeword is presented. In this method, after studying more systematically the thermodynamic and physicochemical constrains of DNA encoding sequences and exploring the inherent connection among these constrains, the criterions are classified into two classes, and the order of criterions is organized by computational time complexity and constraint intensity. Then the desired number of computational codeword is generated by using random generate and real-time filter algorithm. The comparison results show the performance of this approach outperforms the existing DNA sequence design systems, especially in preventing sequence self-complementary from forming secondary structure and keeping the uniform melting temperature among sequences.After investigating relationship among the universal constraints for the design of computational codeword, we present a new combined weight method to determine the objective index weight in the synthetic evaluation system for computational codeword based on statistics without experiment. The simulation results show that this system evaluation model can not only provide objective and stability evaluation to a set of computational codeword, but guide us to design fitness function when evolutionary algorithms are used to the design of codeword for DNA computing.Because the problem of finding the maximum number of computational codeword in a generated randomly set of DNA sequences can be mapped onto solution to a graph maximum clique problem and is NP-hard. Thus, utilizing meta-heuristic algorithm to find an optimal or near optimal solution and predestinating whether the computational codeword in an arbitrary generated randomly set are enough for the following controllable computation or not is required. So we present an improved Hopfield neural network algorithm to solve this problem. The simulation results show that the proposed method is useful for user to select an appropriate set of candidate DNA sequences to filter and obtain the good computational codeword finally.Aim at satisfying the maximum unique of the codeword and the minimum rate of crossover, we present a new computational codeword design method based on Hybridized Simulated Annealing Algorithm and Genetic Algorithms. This method possesses both the global searching ability of GAs and the local rapid convergence of SA algorithm, and the efficiency improved. The simulation results show that the proposed method is effective to generate high quality computational codeword.The design of computational codeword based on particle swarm optimization is discussed. We propose strategy for converting the discrete problem into the continuous optimization problems so as to the standard particle swarm optimization algorithm could be used to address in the design of computational codeword, which belongs to discrete problem. Besides, a new methodology based on Quarter-Discrete Particle Swarm Optimization is also developed to optimize DNA encoding. Simulation results show that our two PSO-based approaches are effective for the small scale encoding problem, and could rapidly converge at at the minimum level for an output of the simulation model.