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

第26卷第l2期 2006年 l2月 计算机应用 Computer Applications 文章编号：1001—9081(2006)12—2998 03 基于粘贴模型的图顶点着色问题的 DNA算法 Vo1．26 No．12 Dee．2006 马季兰，杨玉星 (太原理工大学计算机与软件学院，山西 太原030024) (jade—star@163．CO1TI) 摘 要：为了用生化实验的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 解决图的顶点着色问题，基于粘贴模型的巨大并行性，将着色问 题转化为可满足性问题，提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤，并对 生化反应过程进行了模拟，得出具体的着色 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，证明了该算法的可行性。 关键词：DNA计算；粘贴模型；NP 完全问题；图顶点着色 中图分类号：TP301．6 文献标识码：A DNA algorithm of graph vertex coloring problem based on sticker model Ma Ji．．1an Yang Yu xing (College of Computer and Software，Taiylmn University of Technology，Taly~,an Shar~i 030024，China) Abstract：In order to solve the graph ve~ex—coloring problem，a DNA algorithm based on sticker model was proposed， which conve~ed the coloring problem to satisfiability problem on the basis of the vast parallelism．The operation steps were Ven through an instance+And a simulation experiment WaS carried out to illustrate the biochemical procedures．The final coloring schemes were got．Consequently，the feasibility of the algorithm is proved． Key words：DNA computing；sticker model；NP··complete problem；vertex--coloring of graph 0 引言 由于解决NP(Non-deterministic Polynomial，非确定多项式 复杂程度)完全问题的精确算法的时间复杂度随着问题的规 模成指数级增长，因此，传统计算机对这一类问题显得力不从 心。随着DNA计算与DNA计算机研究的展开，一些NP完全 问题、NP难问题的计算模型被相继提出 J。 计算模型的研究一直是DNA计算领域的研究热点之一， 至今已有不少的计算模型被提出，其中，近几年的研究热门是 剪接模型和粘贴模型 ]。其中，粘贴模型是文献[5]首次提 出的DNA计算模型，粘贴模型有着与剪接模型同样的计算能 力，而且具有不需要延伸DNA链、不需要酶的参与以及 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 可以重复利用等优点。目前，研究者们基于粘贴模型已经解 决了不少NP类问题。例如：3-SAT问题(3-satisfiability，3可 满足性问题) J、旅行商问题(Traveling Salesman Problem， TsP)⋯、k一团与k一独立集问题 等。文献[9]根据颜色将 顶点编码成k个长度不同的单链 DNA，给出了求 图的顶点 k一着色问题的一种 DNA算法；文献[10]中提出了一种图的 顶点着色问题的粘贴算法，其主要思想是将着色问题分解成 顶点独立集问题和顶点划分问题进行解决；本文是将图的顶 点着色问题转化为SAT问题进行解决。 1 粘贴模型 在粘贴模型中用单、双链 DNA分子进行编码，分别对应 于传统计算机的0和 1。在粘贴模型的存储区中，放置着由 存储链和粘贴链组成的存储合成物。存储链是一个由n个不 重叠的子链组成的单链 DNA分子，而每个子链包含 ／rt个碱 基。每个粘贴链也是由m个碱基构成，而且每个粘贴链均与 存储链中的某一个子链满足Watson—Crick互补关系。当一个 存储合成物中的某一个位元为单链时 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示O，为双链时表示 1。如图1所示是子链数为4，子链长度为5个碱基的位串。 图1 一个位串实例 图1中的位串对应的二进制串是：0110。 粘贴模型在位串上定义了四种基本操作： 合并：定义存储合成物的集合 。与 的合并为 ，其中， T = T。u 。 分离：根据存储合成物中第i个位元的状态(即单、双链) 将存储合成物的集合 分解为两个集合：+(T，i)和一(T，i)， 其中+(T，i)为该位元为“1”的位串的集合，一( ，f)为该位 元为⋯0’的位串的集合。 设置：对存储合成物的集合 中的所有位串的某～特定 位置i的位元，Set(T，i)的含义是：若其状态为“0”，将其状态 设置为“1”。 清除：对存储合成物的集合 中的所有位串的某～特定 位置i的位元，Clear(T，i)的含义是：若其状态为⋯1’，将其状 态设置为“0”。 基于粘贴模型的计算模式就是将问题的所有可能解用位 串来编码，得到一个“数据池”，对该数据池中的位串通过上 述操作的某一种或者几种操作的排列组合，筛选出结果串，如 果结果串为空，则表明问题无解。 2 图的顶点着色问题的粘贴算法 2．1 问题描述 给定无向简单图G=( ，E)及颜色集合C，图的顶点k一 收稿日期：2006一O6—26：修订日期：2006—08—21 作者简介：马季兰(1948一)，女。llI西五寨人。教授，主要研究方向：智能计算、软计算 ； 杨玉星(1981一)，男，河南柘城人，硕士研究生，主 要研究方向：DNA计算． 维普资讯 http://www.cqvip.com 第l2期 马季兰等：基于粘贴模型的图顶点着色问题的DNA算法 2999 着色问题可描述如 F：能否用 c中的颜色对图 G的顶点着色， 使得每 一顶点着⋯种颜色，且相邻的顶点不同色。这里， 是 顶点集合，V； { 。， ：，⋯， }；E足边的集合 E= {e。， 2，⋯， e }；C是颜色的集合C={c。，c ，⋯，c }。图的顶点k一着色问 题是 NP一完全问题 2．2 问题转化 这里，我们将图的顶点着色问题转化为 SAT问题来解 决。为此，引出以下定理： 定理l 图的顶点着色问题可以转化为SAT问题。 证明 令P ：{ ，舌 ·看 ，其中， ：1，2，⋯， ； 【O ，若 不着 c =1，2，⋯，ko则图G的每一种着色方案对应于向量(P Pl2’ ⋯ ，P。 ，P2。，P2 ，⋯，P ，⋯，P 。，P ，⋯，P )的一 种赋值方 案。则： ^ (1)每一个顶点 着一种颜色 等价于： P =1，当P P ，⋯，P 中有两个或两个以上取值为“1”时，表示 ．可以着 与取值相对应的两个或两个以上的颜色中的其中一种。 (2)相邻顶点着不同颜色。等价于：对于 V e． E，若 e 连接的两个顶点是 ，和 ，则对于 V c c，满足p。V p =1。 因此，图G一种着色方案是否为正常着色的问题等价于 合取范式，是否为真的问题。 n ^ ^ 一 一 F= ( P ) v ( ， (P V P )) 这里，边e 连接的两个顶点是 和 。 综上所述，图的着色问题可以转化为SAT问题。 2．3 算法描述 对于n个顶点、p条边的图G的顶点k一着色问题可以转 化为f个变量s个子句的SAT问题。因为每个顶点可以选择k 种颜色之一，所以，变量数f=n k；每一条边连接两个顶点， 这两个顶点不能着同种颜色，每条边对应于k个子句，P条边 有k P个子句数与之对应；而每个顶点有一个约束条件，每 个顶点fl!I就对应于一个子句，n个顶点有 n个子句与之对应。 所以，子句数s=ri+k P。 向 量 (P Pl2，⋯，Pl^，P2l，P22，⋯，P2^，⋯，P P ，⋯， P )的所有可能的赋值方案就是问题的可能解的集合。我们 对该向量用长度为n 个位段的DNA单链来表示，每个位段 的长度m值可以根据问题的规模选择，为了减少生物反应的 错配现象，问题规模较大时，m值也应相应增大。 接下来，采用 Lipton的编码技术⋯对P (i=1，2，⋯，ri； J=1，2，⋯k)编码，每个P 设计两个不同的等长DNA单链P 、 p 分别表示取值为真、为假。共需要 2n十k个寡核苷酸链。然 后，生成初始数据池(试管 )。 包含2” 个 DNA位串，每 个位串的编码长度为 n k m。P 是一个位串中的第(i一 1) k+J．个位段。初始数据池 的生成方法见文献[6]。 下面对初始试管 选用粘贴模型的操作，并引入Discard 表示“舍弃”操作(将试管中的溶液倒掉)，以Lipton解决SAT 问题的思想⋯为依据，给出求解图G的顶点 k一着色问题的 算法。 删除包含未着色顶点的方案： GraphColoring( ．，l，P， )： F0ri 1 to n d0 Separate十( ，(i一1)}k+I)and一(Io，(i一1)$ +1) 7 一十(? ，(i 1) k十1) 7’．一一( ，(i一1)}k十1) Forj+一2 tt) do Separate十(Tl，(i一1)十 +』)8lld (Tl，(i 1)}k+ ) 7 — Merge( ，十(Tl，(i一1)} + )) 71l一一(Tl，(i一1) + ) End Discard Tl End 删除相邻顶点着同种颜色的方案： Fori¨ 1 toP do Forj+_-1 to do Separate十(To，(r一1) k+ )attd一(Vo，(r一1)} 十』) 一一( ，(r一1)} + ) 71l一+( ，(r一1)$k十 ) Separate十(Tl，(t一1)}k十』)and (Tl，(t一1)十 十 ) +一Merge(To，一(Tl，(t一1)} +』)) Discard十(Tl，(t一1)十 + ) End End 上述程序段中r和t是边e 连接的两个顶点 和 的下 标的值，随着e．的变化而相应变化。 经过以上操作，试管 中的DNA链即为表示正常着色 方案所对应的DNA链。 3 实例 下面用上述算法来求解 5个顶点、7条边的无向简单图 G=( ， )(如图2)的顶点3一着色问题。 幽 2 一个尢 向图文例 在图2中，V={ l， 2， ， 4， 5}；E {Pl，e2，e3，e4，e5，e6， 7} ={( l， 2)，( 2， 3)，( 3， 4)，( 4， 5)，( l， 5)，( l， 3)， ( l， 4)}：颜色集合 C={c。，c2，c3}；顶点数 ri=5；边数P= 7；颜色数k=3。该图的3一着色问题可以转化为 15个变量、 26个子句数的可满足性问题： F =(PIJ V pI2 V Pl3)^ (P2I V p22 V P23) ^ (P31 V p32 V p33)A (P4l V p42 V p43) ^ (P51 V p52 V p53)A (pll V p21)A (Pl2 V p22) ^ (Pl3 V P23)A (p2l V p31)A (p22 V P32) ^ (p23 V p33)A (P3l V p41)A (p32 V p42) ^ (p V p )A (P 。V p 。)A (P V P ：) ^ (p43 V p53)A (Pl1 V p51)A (Pl2 V pj2) ^ (p13 V p53)A (pll V P41)A (p12 V p42) ^ (pl3 V P43)A (pll V p31)A (p12 V p32) ^ (Pl3 V P33) 采用文献[1]中介绍的Adleman编码技术对P (i=1，2， ⋯ ，n；J=1，2，⋯，k)随机编码，本文中采用的编码如下： P = CTGACAGGGA PlFl= CCCTCTTGTA P = TAGCAGCAGT p = TGTGCATTTG P = TTGCCACTCA P = TAGCCTTCCG 维普资讯 http://www.cqvip.com 3000 计算机应用 2006丘 p2TI= ATGGAGAGAA p2Fl= GCGCGGGCCA p2T2= CTAGAAGATA p2F2=ATGTCGGGCC p2T3= CTTGAGCGCG p2F3= CCAAGCCCCA p3Tl= GGCATTTGTA p3Fl= GGCAGGTTTC p3T2 = CTCTCCCGCA p3F2= GGGGCAATGT P”T = GTACATTCGG P”F = TAGAACATAA p4TI= CGCTGGAATT p4Fl= ACATTCGCCG p42T = CATTACTAGT p4F2= AAACCGTCCT p4T3 = TTGTAAGGAA p4F3= GCCGCCAGGA TI= GTGCGTTAAT p5F1= GGATAGGGTC p = CGAACGGTCT p5F2= CAACTAAGTC p女T = CACCTTGCGC p F =AGCCAACGCC 初始数据池 中，有2 个表示着色方案的长度为 15 X 10：150个碱基序列。调用算法GraphColoring(vo，5，7，3)， 对 执行如下的操作： 步骤 1：删除包含顶点未着色的方案。 1)删除包含顶点 。未着色的方案。 利用探针技术分离 +( ，1)和 一(T0，1)，记 +(To，1) 为 ，一( ，1)为T ；设计探针，分离 +( 。，2)和一( ，2)， 将 +( ，2)倒人试管 中，记 一( l，2)为T。；分离 +( ， 3)和一(T。，3)，将+(T ，3)倒人试管 中，将一( 。，3)作 为废弃溶液倒出。 2)：仿照步骤步骤 1)，依次删除顶点 、 ，、 、 未着色 的方案。 步骤2：删除相邻的边着同种颜色的方案。 1)删除边e 连接的两个顶点 、 着同种颜色的方案。 (a)删除顶点 、 都着颜色c。的方案。 设计探针、分离 +( ，1)和 一(T0，1)，记 一( ，1)为 ， +(T0，1)为7’ ；设计探针，放人试管 来分离 +( ，4) 和 一( 。，4)，把一( ，4)倒人 ，将 +( 。，4)作为废弃溶液 倒出。 (b)仿照步骤(a)，删除顶点 、 都着颜色c 、c 的方 案。 2)仿照步骤2中步骤1)，依次删除其余各边连接的顶点 着同种颜色的方案。 步骤3：T0中的结果串即为正常的着色方案，对其进行 PRC扩增，测出结果值。 在VC++6．0环境下，编程模拟上述筛选过程。对长度 为150个碱基的2 个 DNA串组成的“数据池”进行筛选，依 次删除不满足合取范式F中pll VP 2 V P P VP VP 3，⋯ 等24个子句的DNA串，得到6种正常着色方案，最终结果及 其对应的着色方案如表 1所示。 表 1 结果串及相应的着色方案 从表 1可以看出，该实例共有6种3一着色方案，不存在 2一着色方案。 4 结语 将图的顶点k-着色问题转化为 SAT问题，基于Lipton解 决SAT问题的算法，给出了一种解决图顶点着色问题的通用 算法。并给出了一个实例的实验方案，对其进行了模拟计算。 文中提出的算法具有与顶点数n、边数P、颜色数 k成线性关 系的时间复杂度；该算法中编码方式虽然简单，但也存在着编 码量较大的问题，这一问题的解决有待于新的编码方案的提 出和对算法的改进，这也是我们日后的研究的重点之一。 参考文献： [1 J UPTON RJ．DNA solution of hard computational problem[J】．Sci- ence，1995，268：542—545． 『2】 WU HY．An improved surface-based method for DNA computation lJ】．Bio-systems，2001。59(1)：1—5． 【3j 许进，萤!E4I~。魏小鹏．粘贴 DNA计算机模型(I)：理论【J】． 科学通报，2004，49(3)：205—212． 【4】 许进，李三立，董亚非，等．粘贴 DNA计算机模型(Ⅱ)：应用 【J】．科学通报。2004。49(4)：299—307． 【5】 ROWEIS S，WINFREE E，BURGOYNE R。et a1．A sticker based 811'- chitecture for DNA computation[A】．DNA Based Computers，Proc 2nd Annual Meeting【C】．Princeton：Baum E B，1999．1—27． [6】 BRAICH RAVINDEILlIT s，CHELYAPOV N，JOHNSON C。et a1． Solution of a 20一variable 3-SAT problem on a DNA computer¨ 】． Scienee ，2002。296：499—502． [7】 ZIMMERMANN KH．Efficient DNA algorithms for NP-complete graph problems[J1．Computer Physics Communications，2002，144(3)；297 — 3o9． 【8J 董亚非，谭刚军，张社民．给予粘贴模型求解TSP问题【J】．系统 与仿真学报，2005，17(6)：1299—1302。1306． 【9J 高琳，许进．图的顶点着色问题的 DNA算法【J】．电子学报， 21303，31(4)：494—497． [1O】 王淑栋。刘文斌，许进．图顶点着色问题的DNA粘贴算法【J】． 系统 程与电子技术，2005，27(3)：568—573．。 I 11I 原晋江．图的路色数问题的 NP一完全性I JI． 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 研究，1995， 28(1)：49—53． 维普资讯 http://www.cqvip.com