The Research On Several Problems Of Dna Computing

DNA computing is a new computing paradigm which uses biological molecules as calculation medium and biochemical reaction as calculation tool. Generally considering, although the ability of the classical electronic computer is un-assailable when it executes serial tasks. DNA computing shows natural advantages compared with the classical electronic computer in solving NP hard problems. In this thesis, some problems in DNA computing are discussed and studied. The main results are as follows:The shortest directed path problem is to find a directed path with minimum weight in two pointed vertices of a directed network. It has extensive applications in engineering practice. Sticker system and delete system are two abstract models in DNA computing. In this thesis, we propose DNA computing model and realization algorithm of the shortest directed path problem using the high parallelism of sticker system and delete system and give an example to show the whole process.DNA encoding problem is to design the initial solutions of DNA computing, and the quality of DNA codes could determine whether the DNA computing is successful or not. In this thesis, we view DNA code as a language generated by some grammar and prove the existence of the DNA encoding grammar. Then, by simplifying the alphabet of the grammar, we transform the grammar design of DNA code to that of the binary, and obtain two properties of the DNA encoding grammar.