| In 1994, Doctor Adleman successfully gave the solution of a Hamilton path of a directed graph with seven vertices using DNA molecules and biological enzymes, which inaugurated a new era of DNA computing. In recent years,much work has been done on DNA computing and great success has been achieved by many scholars at home and abroad. And a great progress has been made on the study of DNA computing and DNA computers in both theoretical research and experimental method.In DNA computing, the encoding problem of nucleic acid plays an important role, which directly influences the validity and reliability of the computing process and determine the success or failure of the final computing results. In this thesis, beginning with the analysis and research of DNA coding problem, algorithms for designing DNA sequence are presented and then the applications of DNA computing, such as the multi-valued logic operation, and the DNA algorithm for maximum flow problem, are investigated. This thesis is organized as followsThe coding problem is studied in this thesis, and the branch and cut algorithm(BCA) is applied to design the DNA sequences, which satisfy corresponding combinatorial and thermodynamic constraints, and the search speed of DNA sequences design can be improved effectively. Compared with the existing results, the DNA sequences generated by BCA possess the higher coding quality and thermodynamic stability. So, the BCA is effective in designing the small-scale DNA coding sequences.A filter function is introduced into the process of DNA coding, by which DNA coding sequences are mapped into the vectors in real space. Based on this idea, a novel algorithm is constructed to design the DNA sequences, and the comparisons of coding sequences is made. According to the comparing results, the algorithm for DNA words designing based on the filter function is effective. A set of better DNA sequences with better quality and higher thermodynamic stability can be obtained using the algorithm.Based on error-correcting thery, a novel algorithm for DNA sequence design is also constructed in this thesis. A set of good DNA strings coulde be achieved using this algorithm. Furthermore, the simulation results show that the algorithm is effective in nucleic acid sequences design for DNA computing.Based on DNA hairpin structure, an operation of multiple value logic is constructed. The chemically induced DNA hairpin structure is used to construct the logic gate with multiple inputs, and the modular addition with regard to the modulus 3 is realized by the DNA hairpin structure. In DNA hairpin model for the multiple value logic operation, the logic gates can be reused after logic operation. The input signal and the output signal are in the same form represented by linear DNA strands. By this means, the signals can be transported between different logic gates. In addition, the method can be generalized to the realization of other multi-valued logic gates. The DNA model of the multi-valued logic gates has the characters of reusability and better reliability.Finally, the DNA computing is applied to solve the maximum flow problem. In order to find all augmenting paths, DNA algorithm is designed in the first stage, which can exploit the massive parallelism of DNA computing. Compared with the existing algorithms for solving augmenting path problem, the complexity of DNA algorithm for maximum flow problem is the lowest. The result indicates that combination of the DNA computing and electronic computers can obviously improve the computational efficiency in solving the maximum flow problem.
|
PDF Full Text Request