DNA計算在整數(shù)規(guī)劃問題中的應(yīng)用
DNA Computation for a Category of Special Integer Planning Problem
-
摘要: 基于生化反應(yīng)原理的DNA計算由于在解決一類困難問題,特別是NP-完全問題上具有硅計算機(jī)無法比擬的優(yōu)勢,因此對DNA計算的研究具有重要意義。利用在基于表面的DNA計算中采用熒光標(biāo)記的策略,提出了一種基于DNA計算的一類特殊整數(shù)規(guī)劃問題最優(yōu)解的求解算法,新算法利用熒光猝滅技術(shù),通過觀察DNA分子表面的熒光來排除非解。算法分析表明,新提出的基于DNA計算的求解算法具有編碼簡單和錯誤率低等特點。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.
-
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]許進(jìn),張雷.DNA計算機(jī)原理、進(jìn)展及難點(Ⅰ):生物計算系統(tǒng)及其在圖論中的應(yīng)用.計算機(jī)學(xué)報,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]殷志祥,張鳳月,許進(jìn).0-1規(guī)劃問題的DNA計算模型[J].電子與信息學(xué)報.2003,25(1):62-66瀏覽 -
計量
- 文章訪問數(shù): 2433
- HTML全文瀏覽量: 96
- PDF下載量: 711
- 被引次數(shù): 0
下載:
