DNA Computation for a Category of Special Integer Planning Problem

Wang Lei; Lin Ya-ping

Volume 27 Issue 5

May 2005

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2005 > 27(5): 814-818

Wang Lei, Lin Ya-ping . DNA Computation for a Category of Special Integer Planning Problem[J]. Journal of Electronics & Information Technology, 2005, 27(5): 814-818.

Citation:

Wang Lei, Lin Ya-ping . DNA Computation for a Category of Special Integer Planning Problem[J]. Journal of Electronics & Information Technology, 2005, 27(5): 814-818.

Wang Lei, Lin Ya-ping . DNA Computation for a Category of Special Integer Planning Problem[J]. Journal of Electronics & Information Technology, 2005, 27(5): 814-818.

Citation:

Wang Lei, Lin Ya-ping . DNA Computation for a Category of Special Integer Planning Problem[J]. Journal of Electronics & Information Technology, 2005, 27(5): 814-818.

PDF( 1457 KB)

DNA Computation for a Category of Special Integer Planning Problem

Received Date: 2003-11-28
Rev Recd Date: 2004-10-15
Publish Date: 2005-05-19

Abstract

Abstract

Biochemical reaction theory based DNA computation is of much better performance in solving a class of intractable computational problems such as NP-complete problems, it is important to study the DNA computation. A novel algorithm based on DNA computation is proposed, which solves the problem of a category of special integer planning problem by using the method of fluorescence labeling in the surface based approach to DNA computation. By utilizing the techniques of fluorescence distinguishing, the new algorithm can eliminate all of those false solutions through observing the fluorescence on the surface of DNA molecules. Algorithm analyses show that the new proposed algorithm based on DNA computation has such good characteristics as simple encoding and low fault rate etc.

FullText(HTML)

References(1)

References

Gao Lin, Xu Jin. DNA solution of vertex cover problem based on sticker model. Chinese Journal of Electronics, 2002, 11(2):280 - 284.[2]Bach E, et al.. DNA models and algorithms for NP-complete problems[J].Journal of Computer and System Sciences.1998, 57(2):172-[3]许进,张雷.DNA计算机原理、进展及难点(Ⅰ):生物计算系统及其在图论中的应用.计算机学报,2003,26(1):1-11.[4]Frank G, Makiko F. Carter B. Making DNA add. Science, 1996,273(7): 220 - 223.[5]Yurke B, Mills Jr. A P. Cheng Siu Lai. DNA implementation of addition in which the input strands are separated from the operator strands. Bio-systems, 1999, 52(1-3): 165 - 174.[6]Oliver J S. Matrix multiplication with DNA[J].Journal of Molecular Evolution.1997, 45(2):161-[7]Alderman L M. Molecular computations to combinatorial problems[J].Science.1994, 266(11):1021-[8]Lipton R. Using DNA to solve NP-complete problems[J].Science.1995, 268(4):542-[9]Sakamoto, et al.. Molecular computation by DNA hairpin formation[J].Science.2000, 288(5):1223-[10]Liu Q, Guo Z, Fei Z, et al.. A surface based approach to DNA computation[J].Journal of Computational Biology.1998, 5(2):255-[11]Wu Hao-Yang. An improved surface based method for DNA computation[J].Bio-systems.2001, 59(1):1-[12]殷志祥,张凤月,许进.0-1规划问题的DNA计算模型[J].电子与信息学报.2003,25(1):62-66浏览

Relative Articles

Supplements(0)

Cited By

Proportional views