A Chinese Postman Problem based on DNA computing

Zhixiang Yin; Fengyue Zhang; Jin Xu

doi:10.1021/ci010046r

A Chinese Postman Problem based on DNA computing

Zhixiang Yin^*, Fengyue Zhang, Jin Xu

^*Corresponding author for this work

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

24 Citations (Scopus)

Abstract

DNA computing is a novel method for solving a class of intractable computational problems, in which the computing can grow exponentially with the problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. A Chinese Postman Problem has been solved by means of molecular biology techniques in the paper. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.

Original language	English
Pages (from-to)	222-224
Number of pages	3
Journal	Journal of Chemical Information and Computer Sciences
Volume	42
Issue number	2
DOIs	https://doi.org/10.1021/ci010046r
Publication status	Published - Mar 2002
Externally published	Yes

Access to Document

10.1021/ci010046r

Cite this

@article{f6d14f4522dd43f39a02c21f4e0f4f00,

title = "A Chinese Postman Problem based on DNA computing",

abstract = "DNA computing is a novel method for solving a class of intractable computational problems, in which the computing can grow exponentially with the problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. A Chinese Postman Problem has been solved by means of molecular biology techniques in the paper. A small graph was encoded in molecules of DNA, and the {"}operations{"} of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.",

author = "Zhixiang Yin and Fengyue Zhang and Jin Xu",

year = "2002",

month = mar,

doi = "10.1021/ci010046r",

language = "English",

volume = "42",

pages = "222--224",

journal = "Journal of Chemical Information and Computer Sciences",

issn = "0095-2338",

publisher = "American Chemical Society",

number = "2",

}

TY - JOUR

T1 - A Chinese Postman Problem based on DNA computing

AU - Yin, Zhixiang

AU - Zhang, Fengyue

AU - Xu, Jin

PY - 2002/3

Y1 - 2002/3

N2 - DNA computing is a novel method for solving a class of intractable computational problems, in which the computing can grow exponentially with the problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. A Chinese Postman Problem has been solved by means of molecular biology techniques in the paper. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.

AB - DNA computing is a novel method for solving a class of intractable computational problems, in which the computing can grow exponentially with the problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. A Chinese Postman Problem has been solved by means of molecular biology techniques in the paper. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.

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

U2 - 10.1021/ci010046r

DO - 10.1021/ci010046r

M3 - Article

C2 - 11911690

AN - SCOPUS:0036489452

SN - 0095-2338

VL - 42

SP - 222

EP - 224

JO - Journal of Chemical Information and Computer Sciences

JF - Journal of Chemical Information and Computer Sciences

IS - 2

ER -

A Chinese Postman Problem based on DNA computing

Abstract

Access to Document

Other files and links

Fingerprint

Cite this