Dissertation > Excellent graduate degree dissertation topics show

Self-assembled DNA computing model and its application

Author: ZhangXunCai
Tutor: XuJin
School: Huazhong University of Science and Technology
Course: System Analysis and Integration
Keywords: DNA computing Tile self-assembly Arithmetic 0-1 integer programming Graph Coloring Coding Design NTRU decipher Integer factorization
CLC: TP301.6
Type: PhD thesis
Year: 2009
Downloads: 531
Quote: 3
Read: Download Dissertation

Abstract

DNA computing is a novel based on the biochemical reaction mechanism information processing model, based on the computer Turing machine ideological principle different. DNA computing to solve problems from the ability to scale point of view, it developed rapidly; 1994, Adleman given only handle seven vertices of a directed graph calculation experiment, to 2007, China developed a search capability can reach 10 < sup> 28 of times vertex coloring DNA computer, in just 15 years. Especially in recent years, DNA molecular self-assembly theory, experiment and control technology, the rapid development, the realization of DNA computer technology provides a new theoretical and means. It is by virtue of its massive storage capacity and ultra-large-scale parallel computing, in theory, can overcome the computer storage capacity and computing speed on the lack of NP-complete problems is expected to become a potential solutions. DNA molecular self-assembly is defined as the temperature, concentration, pH and the specific enzymes, some of the DNA molecule with the input information (for example, DNA Tile) pair according to Watson-Crick complementarity principle, generate a new self-assembly with output information with DNA molecules. The last decade, DNA molecular self-assembly technique in molecular computing, biophysics, nanotechnology and other aspects have been widely used. In particular, the development of DNA computing has important guiding significance. Self-assembled DNA computing model is formed by the interaction between DNA molecules specific to complete the configuration of the calculation. It is a combination of DNA computing, Ting theory and DNA nanotechnology has become one of the models current concern. In the calculation process, it avoids the other DNA computing model number of experiments required number of operations, reducing the operation time-consuming and error brought tendencies. In this paper, in-depth study of self-assembled DNA computer management on the basis of its NP-complete problems in information security, and discuss applications in the field, and gives a coding design. This innovation follows: First, the calculation of the traditional subtraction and division operation mechanism, the process according to the division operation, the division into sub comparison, the replication subsystem and subtraction subsystem. With existing Tile type of information will be operational by encoding and Tile sticky ends associated with DNA Tile self-assembly technology to achieve given three subsystems eleven. Finally merge these three subsystems is established based on self-assembled DNA computing model for subtraction and division. Second, the self-assembled DNA computing model was applied to solve combinatorial optimization problems, including 0-1 programming problem and graph coloring problem. 0-1 programming problem as an important issue in operations research, so far no good algorithm. Based on the 0-1 programming problem constraint handling mechanism analysis, constraint handling is divided into two basic operations: \And gives the \By combining these two operations, based on DNA self-assembly techniques, for any feasible solution that can automatically determine whether it satisfies all the given constraints. With the parallelism of DNA computing is proposed based on self-assembled DNA computing model 0-1 programming problem constraint handling scheme. Theoretical analysis shows that, using self-assembled DNA computing model that can in polynomial time to solve this problem. Vertex coloring problem with real life timetable, scheduling and task allocation issues are closely related. This self-assembly based on the characteristics of the DNA molecule, introduction of non-deterministic algorithm can be non-deterministic graph coloring scheme given. The use of self-assembled DNA computing parallelism advantages in parallel to verify that all possible coloring schemes, with high probability to give solution to the problem, solved in polynomial time graph vertex coloring problem. Then, the DNA Tile coded information, by means of adhesion between the ends Tile for self-assembly, gives some two integer multiplication and multiplication of two polynomials of implementation. On this basis, through the introduction of non-deterministic assignment Tile, proposed a self-assembled DNA computing with deciphering and RSA public-key cryptosystem NTRU non-deterministic algorithms. By creating hundreds of millions involved in the calculation of DNA Tile, parallel algorithm with high probability to decipher these two cryptosystem. The biggest advantage of the method is to fully utilize the DNA Tile has a massive storage capacity, the enormous parallelism biochemical reactions and spontaneous assembly of orderliness. Finally, for the self-assembly of DNA computing gives a sequence encoding design. Encoding quality, the encoding quantity of the sequence length and DNA computing the reliability, efficiency, scalability are closely related. Optimized design of the most essential DNA coding rules embedded in the DNA hybridization process to bind to each other among the thermal dynamics. Thermodynamic encoding constraints, the establishment of the coding sequence design objective optimization mathematical model. With IWO algorithm, we propose a coding sequence for the design optimization algorithm, elaborated algorithm implementation process. Generated by the algorithm to provide a sequence and Deaton comparison and analysis of DNA sequences, confirmed the proposed algorithm can produce more stable thermodynamic properties of DNA sequences to verify the effectiveness of the algorithm, expanding the IWO algorithm in a discrete space Application.

Related Dissertations

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net Mobile