DNA Algorithm For Traveling Salesman Problem Based On Molecular Computation

Presently, two new computing paradigms are popular in large-scale parallel computation: quantum computing and DNA computing. And this paper researches into DNA computing paradigms. DNA computing, as a new paradigms in computation technology, employs DNA molecular computation, having uncomparable advantages compared with conventional computers. Thus attracts great attention.With the fast develovment of computer technology and molecular biotechnology, DNA computing as a new interdispline has been under-develovment, which has great potential in sloving large-scale parallel computation, especially in NP-complete problems.This paper firstly introduces the present develovment of DNA computing, the mathematic theories of DNA computing, the biological base of DNA computing and the mechanism of DNA computing. Secondly, the paper analyzes the living example model of DNA computing in sloving NP-complete problem. On the foundation of the former encoding methods, the paper poses two new encoding methods: one based on weight is represented by DNA string, the other based on melting temperature control encoding method, and the practical use of two encoding methods in sloving TSP problem. Finally, the paper presents DNA molecular algorithms and living examples of TSP problem based on sticker model.