Papers by Keyword: DNA Computing

Abstract: The emergency of a new computing pattern must be supported by powerful mathematical theory, weak theoretical supported ideology does not have a strong vitality, and which will become vulnerable. As being a new theory, the DNA computing treated as a new computational pattern also need a lot of basic theoretical research system. This article describes the nature of DNA computing, given the equivalence of DNA computing pattern with traditional computer under the support of automata theory system, further analysis and understanding the DNA computing pattern.

Abstract: DNA computing has the support of automata theory completely, based on the equivalent for expressing problem by DNA computing model and the double-shift language in automata theory, using a DNA molecule may encode the instantaneous description of Turing machine, and the operation of continuous sequence can be realized by the DNA molecule s operation with enzymes. Insert - Remove System is a computing system in DNA computing, designed an Binary Tree DNA computing model based on the Insert - Remove System in this paper, which can realize the insert, delete and traversal operation, and has the completeness of the theory.

Abstract: Artificial intelligence based on the genetic algorithm and DNA computing based on the biological intelligence is two kinds of important intelligent computing model, Graph theory and combinatorial optimization problem is a hotspot of research on intelligent computing. This paper designs a coding space optimized by using genetic algorithm, and by using DNA computing to solve Minimum Spanning Tree Problem calculation model. Because MSTP (Minimum Spanning Tree Problem) refer to Weight, IMCE (Incompletion-Molecule Commixed Encoding) is used in vertex, edges and weights encoding. The calculation process of the MSTP solution has been detailed described detailed.

Abstract: With the progress of DNA computing and nanotechnology, DNA/AuNP conjugation becomes an emerging interdisciplinary field. In this paper, a novel DNA computing model based on DNA/AuNP conjugation is developed to solve a maximum independent set problem (MIS). Making use of the hybridization between long DNA strands and short strands conjugated with gold nanoparticles, a series of searching process is implemented. After that, based on the number of DNA/AuNP conjugation on one DNA strand, the answer of the MIS is obtained. To verify the proposed algorithm, a simple paradigm is calculated by using the DNA computing model. In this model, there are some significant advantages such as easy detecting, and controllable automation. This work may demonstrate that DNA computing has the great potentiality in huge parallelism computation.

Abstract: DNA computer is a new type of computer which computing by biological molecular techniques. If DNA computer want to realize its practicability, it must be the same as a traditional computer. In order to settle the issues of representation and organizational in DNA computer, we need a reasonable data structures to effectively represent and organize the information of DNA computer. The thesis designs a stack structure model based on DNA computing, which can express limited stack constraints through hairpin structure. At the same time, it can complete the operations of entering stack and leaving stack using two different restrictive enzymes.

Abstract: Plasmid DNA algorithm of the minimal vertex covering problem is proposed upon the basic idea and operation of plasmid DNA computing model. In the plasmid DNA algorithm, though an appropriate encoding and the basic biological operation, we finish the generation and separation of solution. On the basis of the molecular biology methods, the algorithm is feasible.

Abstract: A new DNA computing model to realize binary integer additions based on molecular beacon is described in this paper. The binary 0 and 1 are represented by two different fluorescent states of a molecular beacon since its two different structures. By designing sequences of molecular beacons skillfully, and using the relationship between each two corresponding bits and their result and carry bit of two operational numbers, the computing process to compute each two corresponding bits of the binary numbers is simulated in the test tube. Finally, the results can be read only by detecting whether the fluorescence in tube emits. The result of the experiment shows that the algorithm is simple and convenient, and the algorithm provides a new idea for DNA computing to realize arithmetic operations

Abstract: . SAT problem is one of important NP-complete problems with widespread application. In this paper, a new DNA computing model based on self-assembled nanoparticle probes is presented to solve this problem. Its essence is that all possible combinations of variables for given problem are encoded in the recognition zone of self-assembled nanoparticle probes. Major benefits of this method include vast parallelism, extraordinary information density and easy controllable operation. The result reveals the potential of DNA computation based on nanotechnology in solving complex problem.

Abstract: About thirty years ago, the concept of the complexity of the problem was proposed. The most important complex class is P and NP class. Fruitful results of this concept are the existence of the so-called complex class complete problem. If the other issues of this class once solved in polynomial time, then the problem must exist polynomial time algorithms. Therefore, the complete problem is most difficult to solve, but because of their presence, we can choose any of them improved algorithm for a problem, so this kind of problem to get a good solution. DNA computing is a novel method that solving a class of intractable computational problems, in which the computing speeds up exponentially with the problem size. Up to now, many accomplishments have been made to improve its performance and increase its reliability. Maximum Independent Set problem (MIS) is a well-known NP-complete problem. Maximum Clique and Minimum Vertex Covering problem is equivalent to Maximum Independent Set problem. In this paper, we explore solving Maximum Independent Set problem by transforming it into equivalent 0-1 programming problem, and utilizing the surface computing model of that. The proposed method demonstrates universal nature of NP-complete problem.

Abstract: In this paper, built mathematical model on Flow Shop scheduling, put forward a RNA genetic algorithm based on DNA computing to solve the Flow Shop scheduling problems. Adopt RNA four digit system encoding method based on DNA computing and RNA computing operator in genetic algorithm. It resolved the encoding scheme and convergence problem which exists in the conventional genetic algorithm. Under some constraint conditions, this genetic algorithm got simulated. Simulation results showed that this algorithm has a better optimum searching and seeking abilities, made the scheduling results comparatively reasonable and expanded the application of DNA computing.