最小顶点覆盖问题的闭环DNA算法

《最小顶点覆盖问题的闭环DNA算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com最小顶点覆盖问题的闭环DNA算法周康许进：(武汉工业学院数理科学系，武汉430023)(华中科技大学控制科学与工程系，武汉430074)E-mail：zhoukang65@tom．tom摘要提出了闭环DNA计算模型的基本概念及其基本生化实验，并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中，提出并实现了用删除实验直接构造顶点覆盖补集的构想：再通过电泳实验得到最小顶点覆盖的补集，由补集得到最小顶点覆盖。这使得算法的设计独特而新颖；由于算法仅用到基本的生化实

2、验，这使得算法的实现简捷、可靠。关键词闭环DNA计算模型最小顶点覆盖问题补集删除实验文章编号1002—8331一(2006)20--0007-03文献标识码A中图分类号TP301．6ClosedCircleDNAAlgorithmoftheMinimalCoveringProblemZhouKangXujin2(DepartmentofMathematicsandPhysics，WuhanPolytechnicUniversity，Wuhan430023)(DepartmentofControlScienceandE

3、ngineering，HuazhongUniversityofScienceandTechnology。Wuhan430074)Abstract：Inthispaper，basicconceptsandbasicbio-chemistryexperimentsofamodelofclosedcircleDNAcomputingarebroughtforward．ClosedcircleDNAalgorithmoftheminimalcoveringproblemisputforward．Intheclosedcirc

4、leDNAalgorithm．anideathatcomplementarysetsofvertexcoveringareformedstraightwaybydeleteexperimentisputforwardandrealized，whichhasdesignofthealgorithminimitableandnove1．Andthencomplementarysetsofminimalcoveringareobtainedbyelectrophoresisexperiment．Minimalcoverin

5、gsCangainedfromthecomplementarysets．Onlyusingbasicbio-chemistryexperimentsinthealgorithm，SOrealizingthealgorithmissimpleandcredible．Keywords：amodelofclosedcircleDNAcomputing，minimalcoveringproblem，complementaryset，deleteexperimentl引言常规的DNA计算算法的构造具有一定的规律性【l-41。其

6、设DNA计算是目前科研领域的热点之一，而DNA计算模型计思想是首先产生全体解空间：再通过各种生化实验分离出问的研究是DNA计算研究的主要内容，其中闭环DNA计算模型题的解；最后检测出解。而本文提出的DNA计算算法有两点是最近发展起来的一种全新的DNA计算模型。与质粒DNA计创新：算模型相比，两者之间有很多相同之处。从用途上看，用质粒(1)通过求解问题的最优解集的补集达到求解最优解集的DNA计算模型能够解决的问题必然可以用闭环DNA计算模目的。型解决；但从结构和功能上看，两者之间存在着两大差距：(2)采用闭环DNA计算

7、模型最基本的生化实验，直接构造(1)两者所用载体不同而造成DNA复制方法的差异。质粒出问题的最优解集的补集，即采用构造法得到需要的解集。DNA的复制要在细菌细胞体内繁殖，操作难度大、操作费用昂在本文中。仅使用闭环DNA计算模型最基本的生化实验贵且成功率不高，而闭环DNA的复制用很成熟的PCR技术。来得到问题的最优解集，这使得算法的实现更加可靠、操作更这样操作成本大大降低、可操作性大大增强且准确性得到提加简便。高，放大倍数增大。(2)因DNA复制过程不同而使得两者计算规模产生差异。2闭环DNA及其基本生化实验闭环DNA

8、的复制条件较少，因此，其规模比质粒DNA计算模闭环双链DNA是由若干个限制性内切酶四的识别序列在型规模要大很多。识别位点处将线性DNA首尾相连而成。在闭环DNA分子上最基于以上原因．闭环DNA计算模型应该具有更强的生命基本的生化实验是接入和删除实验。闭环DNA分子的结构不力和活力，我们研究小组一直致力于对闭环DNA计算模型应同，这两个基本生化实