最小顶点覆盖问题的改进粘贴模型

董亚非; 张家秀; 殷志祥; 许进

最小顶点覆盖问题的改进粘贴模型

董亚非^{①;张家秀},
张家秀,
殷志祥,
许进

计量
- 文章访问数: 2363
- HTML全文浏览量: 111
- PDF下载量: 542
- 被引次数: 0
出版历程
- 收稿日期: 2003-12-04
- 修回日期: 2004-04-05
- 刊出日期: 2005-04-19

An Improved Sticker Model of the Minimal Covering Problem

摘要

摘要: DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学反应作为计算工具的先例，具有广阔的应用前景。本文简单回顾了DNA计算的发展，并简要介绍了分子计算的一种模型粘贴模型。最后我们利用粘贴模型的基本原理，运用荧光标记技术，提出了最小顶点覆盖问题的表面技术解决方案。
- DNA计算;粘贴模型;荧光标记技术;最小顶点覆盖问题
Abstract: DNA computing is a new computation method with simulating molecular biology structure of DNA and by means of molecular biology technology. This method has been widely used in many respects. Simply reviewed the progress of DNA computing, the paper introduces a new model of molecular computation that is called the sticker model. Finally, the solution of the minimal covering problem on surface using fluorescence marking technology is proposed based on the principle of sticker model.

HTML全文

参考文献(1)

Adleman L, Molecular computation of solutions to combinatorial problems. Science, 1994, 266(11): 1021 - 1024.[2]Lipton R. DNA solution of hard computation problems[J].Science.1995, 268 (4):542-[3]Faulhammer D, Cukras A R, Lipton R J, et al.. Molecular computation: RNA solution to chess problem. Biochemsty, 2000,97: 1385- 1389[4]Adleman L. On constructing a molecular computer. Technical Report TR. 79-387, Computer Science Department, University of Southern California, USA, January, 1995.Lipton R. Using DNA to solve SAT, 1995.http:∥www. cs.princeton.edu/rj 1/bio.ps, December 1994.Boneh D, Dunworth C, Lipton R, et al.. On the computational power of DNA, Technical Report TR-499-95, Princeton University, USA, October 1995.[5]Braich R S, Chelyapov N, Johnson C, et al.. Solution of a 20-variable 3-SAT problem on a DNA computer[J].Science.2002,296(19):499-[6]Head T, Rozenberg G, Bladergroen R B, et al.. Computing with DNA by operating on plasmids[J].BioSystems.2000, 57:87-[7]Dirk F, Cukras A R, Lipton R J, et al.. Molecular computation:RNA solutions to chess problem. Biochemsty, 2000, 97:1385- 1389.[8]Liu Q H, Wang L M, Frutos A G , et al.. DNA computing on surfaces[J].Nature.2000, 403(13):175-[9]Head T. Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors, Bull. Math.Biology, 1987, 49:737 - 759.[10]Kari L. DNA computing: arrival of biological mathematics. Math.Intelligencer, 1997, 19(2): 9 - 22.[11]Praun G, Rozenberg G, Salomaa A. DNA Computing-New Computing Paradigms. Berlin: Springer, 1998:32 - 63.[12]Roweis S, Winfree E, Burgoyne R, et al.. A sticker based archtecture for DNA computation, in: Baum E B et al.(Eds), DNA Based Computers, Proc. 2nd Annual Meeting, Princeton, 1999:1 - 27.[13]Paun G, Rozenberg G. Sticker systems[J].Theoretical Computer Science.1998, 204:183-[14]Gao L, Xu J, DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002, 11(2):280 - 284.[15]Zimmermann K H. Efficient DNA sticker algorithms for NP-complete graph problems[J].Computer Physics Communications.2002, 144:297-[16]Benenson Y, Tamar P E, Rivka A, et al.. Programmable and autonomous computing machine made of biomolecules, Nature,2001, (414): 430 - 434.[17]Ouyang Q, et al.. DNA solution of the maximal clique problem,Science, 1997, 278(17): 446 - 449.[18]Dong Ya-fei, Wang Shu-dong, Yin Zhi-xiang, et al.. DNA solution of the minimal covering problem. Advances in Systems Science and Applications, 2003, 3(2): 152 - 156.

施引文献

资源附件(0)

访问统计