Biosystems. 2004 Dec;78(1-3):39-47.

Solving traveling salesman problems with DNA molecules encoding numerical values.

Source

School of Chemical Engineering, Seoul National University, San 56-1 Shillim-Dong, Kwanak-Gu, Seoul 151-744, Republic of Korea.

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.

PMID:: 15555757; [PubMed - indexed for MEDLINE]

Publication Types, MeSH Terms, Substances

Publication Types

Research Support, Non-U.S. Gov't

MeSH Terms

Substances

LinkOut - more resources

Full Text Sources

Other Literature Sources

COS Scholar Universe

Supplemental Content

Save items

Related citations in PubMed

Hybridization-ligation versus parallel overlap assembly: an experimental comparison of initial pool generation for direct-proportional length-based DNA computing. [IEEE Trans Nanobioscience. 2006]
Hybridization-ligation versus parallel overlap assembly: an experimental comparison of initial pool generation for direct-proportional length-based DNA computing.
Ibrahim Z, Tsuboi Y, Ono O. IEEE Trans Nanobioscience. 2006 Jun; 5(2):103-9.
A fractional programming approach to efficient DNA melting temperature calculation. [Bioinformatics. 2005]
A fractional programming approach to efficient DNA melting temperature calculation.
Leber M, Kaderali L, Schönhuth A, Schrader R. Bioinformatics. 2005 May 15; 21(10):2375-82. Epub 2005 Mar 15.
Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction. [Biosystems. 2008]
Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction.
Wang X, Bao Z, Hu J, Wang S, Zhan A. Biosystems. 2008 Jan; 91(1):117-25. Epub 2007 Aug 26.
Review DNA computing. [Curr Opin Biotechnol. 1997]
Review DNA computing.
Gibbons A, Amos M, Hodgson D. Curr Opin Biotechnol. 1997 Feb; 8(1):103-6.
Review [Common problems in the analyses of microbial community by denaturing gradient gel electrophoresis (DGGE)]. [Wei Sheng Wu Xue Bao. 2006]
Review [Common problems in the analyses of microbial community by denaturing gradient gel electrophoresis (DGGE)].
Xing DF, Ren NQ. Wei Sheng Wu Xue Bao. 2006 Apr; 46(2):331-5.

See reviews... See all...

Related information

Related Citations
Calculated set of PubMed citations closely related to the selected article(s) retrieved using a word weight algorithm. Related articles are displayed in ranked order from most to least relevant, with the “linked from” citation displayed first.
Compound (MeSH Keyword)
PubChem chemical compound records that are classified under the same Medical Subject Headings (MeSH) controlled vocabulary as the current articles.
Substance (MeSH Keyword)
PubChem chemical substance (submitted) records that are classified under the same Medical Subject Headings (MeSH) controlled vocabulary as the current articles.

Recent activity

Clear Turn Off Turn On

Solving traveling salesman problems with DNA molecules encoding numerical values...
Solving traveling salesman problems with DNA molecules encoding numerical values.
Biosystems. 2004 Dec ;78(1-3):39-47.

PubMed
Fish consumption and depression: the Northern Finland 1966 birth cohort study.
Fish consumption and depression: the Northern Finland 1966 birth cohort study.
J Affect Disord. 2004 Nov 1 ;82(3):447-52.

PubMed
GPS: a novel group-based phosphorylation predicting and scoring method.
GPS: a novel group-based phosphorylation predicting and scoring method.
Biochem Biophys Res Commun. 2004 Dec 24 ;325(4):1443-8.

PubMed
Molecular classification of scrapie strains in mice using gene expression profil...
Molecular classification of scrapie strains in mice using gene expression profiling.
Biochem Biophys Res Commun. 2004 Dec 24 ;325(4):1339-45.

PubMed
The role of omega-3 long-chain polyunsaturated fatty acids in health and disease...
The role of omega-3 long-chain polyunsaturated fatty acids in health and disease of the retina.
Prog Retin Eye Res. 2005 Jan ;24(1):87-138.

PubMed

Your browsing activity is empty.

Activity recording is turned off.

Turn recording back on

PubMed

Result Filters

Display Settings:

Send to: