Design And Implementation Of Stack And Binary Tree Data Structure In DNA Computer

Since Adleman launched the field of DNA computing with a demonstration in 1994 that strands of DNA could be used to solve the Hamiltonian problem for a simple directed graph, many scientists in different fields are interested in DNA computing Because DNA computing has been formed a new science field. The studying and making DNA computer needs many science subjects such as biological engineering, computer science, etc. Research shows that DNA computer has been a complete Turing machine function, which provides theoretical support for DNA computer whether it can become a real computer. DNA computer likes electronic computer must resolve the information organization of DNA computer which requires reasonable data structure to effectively organize information needs to be deal with in DNA computer. Therefore, design of data structure has important value to research the concrete realization of DNA computer.Firstly, on the basis of referential method of designing a queue in DNA computer, the text presents the method of designing stack data structure in DNA computer, which utilizes the features of stack and two different kinds of restriction endonucleases to complete push and pop of stack. And the storage structure of the stack in DNA computer is formally described. The bio-operations of initialization, push, pop and empty stack are described in detail. The nucleotide encodings of the stack and an instance of simulation are given out. The instance simulates the operating mechanism of DNA computer. The process of an algorithm implemented on this stack is demonstrated.Secondly, this paper proposes the method of designing a binary tree based on sequential storage model in DNA computer. The method utilizes the biological characteristics of DNA molecules and restriction endonucleases to complete sequential storage structure and basic operations of the binary tree. An actual binary tree with detailed nucleotide encodings and an instance of algorithm are given out. The result proves the feasibility of this method in DNA computer.Furthermore, the linked storage structure of the binary tree in DNA computer is formally described. Being affected by ligase, among the various nodes generates hybridizations and linking reaction to form double-stranded DNA. And an instance of a binary tree's linked storage structure is given out, the example indicates the double-stranded DNA correspond with the binary tree's inorder traversing.All the biological technology mentioned in this paper can be practically implemented in the laboratory. Based on these methods, more other data structures in DNA computer can be developed, which can help to organize the information processed by DNA computer correctly and efficiently, and make DNA computer for practical applications.