Solving traveling salesman problems with DNA molecules encoding numerical values

Ji Youn Lee, Soo Yong Shin, Tai Hyun Park, Byoung Tak Zhang

Research output: Contribution to journalArticlepeer-review

126 Scopus citations

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.

Original languageEnglish
Pages (from-to)39-47
Number of pages9
JournalBioSystems
Volume78
Issue number1-3
DOIs
StatePublished - Dec 2004

Bibliographical note

Funding Information:
This research was supported by the MEC Project from the Ministry of Commerce, Industry and Energy, by the NRL Program from the Ministry of Science and Technology, and by the BK21-IT Program from the Ministry of Education and Human Resources Development. The ICT at Seoul National University provided research facilities for this study.

Keywords

  • DNA computing
  • Melting temperature control encoding method
  • Traveling salesman problem
  • Weight representation in DNA

Fingerprint

Dive into the research topics of 'Solving traveling salesman problems with DNA molecules encoding numerical values'. Together they form a unique fingerprint.

Cite this