A Chinese Postman Problem based on DNA computing.
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.
Yin
Zhixiang
Z
Department of Control Science and Engineering, Hua Zhong University of Science and Technology, HuBei 430074, China. zxyin66@263.net, zhixiangyin@sohu.com
Zhang
Fengyue
F
Xu
Jin
J
D001483:Base Sequence; D003205:Computing Methodologies; D004247:DNA / Q000737:chemistry*; D008969:Molecular Sequence Data
D004247:DNA