Solving traveling salesman problems with DNA molecules encoding numerical values

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

doi:10.1016/j.biosystems.2004.06.005

Solving traveling salesman problems with DNA molecules encoding numerical values

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

Department of Nutritional Science & Food Management

Research output: Contribution to journal › Article › peer-review

125 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 language	English
Pages (from-to)	39-47
Number of pages	9
Journal	BioSystems
Volume	78
Issue number	1-3
DOIs	https://doi.org/10.1016/j.biosystems.2004.06.005
State	Published - 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

Access to Document

10.1016/j.biosystems.2004.06.005

Cite this

@article{c49cc030c5034fad87e41d5295b03194,

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.",

keywords = "DNA computing, Melting temperature control encoding method, Traveling salesman problem, Weight representation in DNA",

author = "Lee, {Ji Youn} and Shin, {Soo Yong} and Park, {Tai Hyun} and Zhang, {Byoung Tak}",

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.",

year = "2004",

month = dec,

doi = "10.1016/j.biosystems.2004.06.005",

language = "English",

volume = "78",

pages = "39--47",

journal = "BioSystems",

issn = "0303-2647",

publisher = "Elsevier Ireland Ltd",

number = "1-3",

}

TY - JOUR

T1 - Solving traveling salesman problems with DNA molecules encoding numerical values

AU - Lee, Ji Youn

AU - Shin, Soo Yong

AU - Park, Tai Hyun

AU - Zhang, Byoung Tak

N1 - 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.

PY - 2004/12

Y1 - 2004/12

N2 - 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.

AB - 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.

KW - DNA computing

KW - Melting temperature control encoding method

KW - Traveling salesman problem

KW - Weight representation in DNA

UR - http://www.scopus.com/inward/record.url?scp=8844263882&partnerID=8YFLogxK

U2 - 10.1016/j.biosystems.2004.06.005

DO - 10.1016/j.biosystems.2004.06.005

M3 - Article

C2 - 15555757

AN - SCOPUS:8844263882

SN - 0303-2647

VL - 78

SP - 39

EP - 47

JO - BioSystems

JF - BioSystems

IS - 1-3

ER -

Solving traveling salesman problems with DNA molecules encoding numerical values

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this