title: Solving traveling salesman problems with DNA molecules encoding numerical values.
abstract: We introduce a DNA encoding method to represent numerical values and a biased molecular algorithm based on the thermodynamic properties of DNA. DNA strands are designed to encode real values by variation of their melting temperatures. The thermodynamic properties of DNA are used for effective local search of optimal solutions using biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel electrophoresis. The proposed method was successfully applied to the traveling salesman problem, an instance of optimization problems on weighted graphs. This work extends the capability of DNA computing to solving numerical optimization problems, which is contrasted with other DNA computing methods focusing on logical problem solving.
authors.affiliation: School of Chemical Engineering, Seoul National University, San 56-1 Shillim-Dong, Kwanak-Gu, Seoul 151-744, Republic of Korea.
authors.forename: Ji Youn
authors.initials: JY
authors.lastname: Lee
authors.forename: Soo-Yong
authors.initials: SY
authors.lastname: Shin
authors.forename: Tai Hyun
authors.initials: TH
authors.lastname: Park
authors.forename: Byoung-Tak
authors.initials: BT
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000737:chemistry*; D004591:Electrophoresis, Polyacrylamide Gel; D016133:Polymerase Chain Reaction; D013816:Thermodynamics
chemical_list: D004247:DNA