The Research And Applications Of DNA Self-assembly Model

DNA self-assembly model is a way of DNA computing,it has not only the characteristics of high parallelism and autonomy but also the features of coding flexiblility and high-density storage.The thesis is the use of features of DNA self-assembly model to address perfect matching problem of bipartite graph and time-table problem.First this thesis introduces DNA computing and define DNA self-assembly mathematical model in detail.Then propose a DNA self-assembly model algorithm for perfect matching problem of bipartite graph and time-table problem.In solving perfect matching problem of bipartite graph,the thesis codes DNA Tile through mapping the adjacency relation between two nodes in bipartite graph to DNA-binding domain.The result shows that the perfect matching in bipartite graph self-assembly system can get the solution space use 14 different tile type,2Θ(n)tile after Θ(n)steps self-assembly calculated.At present,traditional arrangement solution most universities adopted can’t meet the course requirements of all the students.To the issue,the thesis presents a university timetable problem which can meet all the students’ cause-choosing request use the least amount of class.The thesis propses a university timetable self-assembly system which consist of three subsystem—subsystem of initial courses solution space 、 detection subsystem of initial solution space and subsystem of class statistics.First this thesis introduces the three subsystems.Then presents university timetable self-assembly system.Finally,constructs Lap-on-Chip using biochip technique to extract optimal solution space.the result shows that the university timetable self-assembly system can get the optimal solution space use 36 different tile type,2Θ(n)tile after Θ(n)steps self-assembly calculated.Finally,the thesis summarizes the DNA self-assembly algorithm for perfect matching problem of bipartite graph and university timetable problem,and proposes the shortcomings.