基于粘贴模型的图顶点着色问题的dna算法

《基于粘贴模型的图顶点着色问题的dna算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第26卷第l2期计算机应用Vo1．26No．122006年l2月ComputerApplicationsDee．2006文章编号：1001—9081(2006)12—299803基于粘贴模型的图顶点着色问题的DNA算法马季兰，杨玉星(太原理工大学计算机与软件学院，山西太原030024)(jade—star@163．CO1TI)摘要：为了用生化实验的方法解决图的顶点着色问题，基于粘贴模型的巨大并行性，将着色问题转化为可满足性问题，提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤

2、，并对生化反应过程进行了模拟，得出具体的着色方案，证明了该算法的可行性。关键词：DNA计算；粘贴模型；NP完全问题；图顶点着色中图分类号：TP301．6文献标识码：ADNAalgorithmofgraphvertexcoloringproblembasedonstickermodelMaJi．1anYangYuxing(CollegeofComputerandSoftware，TaiylmnUniversityofTechnology，Taly~,anShar~i030024，China)Abstract：Inordertosolve

3、thegraphve~ex—coloringproblem，aDNAalgorithmbasedonstickermodelwasproposed，whichconve~edthecoloringproblemtosatisfiabilityproblemonthebasisofthevastparallelism．TheoperationstepswereVenthroughaninstance+AndasimulationexperimentWaScarriedouttoillustratethebiochemicalproced

4、ures．Thefinalcoloringschemesweregot．Consequently，thefeasibilityofthealgorithmisproved．Keywords：DNAcomputing；stickermodel；NP··completeproblem；vertex--coloringofgraph存储合成物中的某一个位元为单链时表示O，为双链时表示0引言1。如图1所示是子链数为4，子链长度为5个碱基的位串。由于解决NP(Non-deterministicPolynomial，非确定多项式复杂程度)完全问题

5、的精确算法的时间复杂度随着问题的规模成指数级增长，因此，传统计算机对这一类问题显得力不从心。随着DNA计算与DNA计算机研究的展开，一些NP完全图1一个位串实例问题、NP难问题的计算模型被相继提出J。图1中的位串对应的二进制串是：0110。计算模型的研究一直是DNA计算领域的研究热点之一，粘贴模型在位串上定义了四种基本操作：至今已有不少的计算模型被提出，其中，近几年的研究热门是合并：定义存储合成物的集合。与的合并为，其中，剪接模型和粘贴模型]。其中，粘贴模型是文献[5]首次提T=T。u。出的DNA计算模型，粘贴模型有着与剪接模型同样的

6、计算能分离：根据存储合成物中第i个位元的状态(即单、双链)力，而且具有不需要延伸DNA链、不需要酶的参与以及材料将存储合成物的集合分解为两个集合：+(T，i)和一(T，i)，可以重复利用等优点。目前，研究者们基于粘贴模型已经解其中+(T，i)为该位元为“1”的位串的集合，一(，f)为该位决了不少NP类问题。例如：3-SAT问题(3-satisfiability，3可元为⋯0’的位串的集合。满足性问题)J、旅行商问题(TravelingSalesmanProblem，设置：对存储合成物的集合中的所有位串的某～特定TsP)⋯、k一团与k一

7、独立集问题等。文献[9]根据颜色将位置i的位元，Set(T，i)的含义是：若其状态为“0”，将其状态顶点编码成k个长度不同的单链DNA，给出了求图的顶点设置为“1”。k一着色问题的一种DNA算法；文献[10]中提出了一种图的清除：对存储合成物的集合中的所有位串的某～特定顶点着色问题的粘贴算法，其主要思想是将着色问题分解成位置i的位元，Clear(T，i)的含义是：若其状态为⋯1’，将其状顶点独立集问题和顶点划分问题进行解决；本文是将图的顶态设置为“0”。点着色问题转化为SAT问题进行解决。基于粘贴模型的计算模式就是将问题的所有可能解用

8、位1粘贴模型串来编码，得到一个“数据池”，对该数据池中的位串通过上在粘贴模型中用单、双链DNA分子进行编码，分别对应述操作的某一种或者几种操作的排列组合，筛选出结果串，如于传统计算机的0和1。在粘贴模型的存储区中，放置着