Solving traveling salesman problems with DNA molecules encoding numerical values.
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.
Lee
Ji Youn
JY
School of Chemical Engineering, Seoul National University, San 56-1 Shillim-Dong, Kwanak-Gu, Seoul 151-744, Republic of Korea.
Shin
Soo-Yong
SY
Park
Tai Hyun
TH
Zhang
Byoung-Tak
BT
D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000737:chemistry*; D004591:Electrophoresis, Polyacrylamide Gel; D016133:Polymerase Chain Reaction; D013816:Thermodynamics
D004247:DNA