Research On Enzyme-digested DNA Computing Model For Timetable Problems

As a developing method of intelligent computing,DNA computing recently has become the subject of extensive attention and study from researchers at home and abroad.In 1994,Adleman originally adopted DNA computing to solve Hamiltonian path problem,which symbolized the DNA computing became an effective method of solving NP-complete problems.The basic method of employing DNA computing to solve problems is that: encoding the practical problems in DNA and forming a specific DNA molecular based on the peculiar molecular structure and the capability of replicate itself.Under the catalyze of biological enzyme,initial solution space is produced.Non-solutions are eliminated after a series of biological reactions.Finally,PCR,gel electrophoresis and other biological methods are employed to test the result and map to the result of the practical problem.Because of its cosmically parallelism and large capability,DNA computing will hopefully have breakthroughs in solving NP-complete problems.Timetable problem,which is a typical NP-complete problem is a constrained,multi-objective optimization problem with great practical value.This paper aims to study the DNA computing model for timetable problems.1.DNA computing model based on AcryditeTM separating technique.After DNA gel columns have been built,they were rearranged by enzyme digestion and electrophoresis.In this process,the minimum number of cycles is the minimum classhour in timetable problem.Restriction enzyme applied in this model improves shortcomings such as long reaction time,complicated reaction conditions and easy generation of hairpin structures and enables better efficiency of the model.2.The DNA computing model based on AcryditeTM separating technique mentioned above can hardly be applied to large-scale timetable problems due to the limitation of biotechnology.For this reason,the paper brings up a surface-based DNA computing model for large-scale timetable problems,which combines fluorescent technique with enzyme digestion.Since the DNA molecules are stored in dot arrays in this model,having advantages on parallelism and storage capability,the model is suitable for large-scale timetable problems.Compared with previous models,this model has the advantages of higher reaction sensitivity,simpler experimental operation and shorter reaction time.The paper studying the DNA computing models not only provides a new research approach and solution for NP-complete problems like timetable problems,but also opens up new possibilities for DNA computing and biological computing.