（计算机软件与理论专业论文）赋权图上优化问题的dna计算方法研究.pdf

山东大学博十学位论文 摘要 在赋权图上优化问题的d n a 计算方法研究中，权值的d n a 编码方法是求 解问题的关键。本文讨论了中国邮递员、旅行商、最大权团、最小生成树等赋权 图上经典优化问题的d n a 计算方法，改进了它们原有d n a 计算模型中的权值 编码方法，给出t n 用改进d n a 编码方法求解的新d n a 算法。我们通过设计 赋权无向图的广义边图给出了中国邮递员问题的一种d n a 编码方法及计算模 型，通过设计赋权图的相对长度图给出了旅行商问题的一种d n a 编码方法及计 算模型，通过选取d n a 序列的最佳逆补比对给出了最小生成树问题的基于逆补 比对的一种d n a 编码方法及计算模型，并通过改进已有的d n a 编码方法给出 了最大权团问题、顶点覆盖问题及o 1 背包问题的d n a 计算模型。我们给出的 d n a 计算模型提高了d n a 计算中数值表示和处理能力。具体研究工作如下： 对于中国邮递员问题，我们首先提出了广义边图的概念，然后设计了一种新 的基于广义边图的d n a 编码方法及d n a 算法。所提出的广义边图d n a 编码方 法利用边到点映射把赋权图中的边映射为顶点，构造给定赋权图的广义边图，使 得赋权图中的边权值转换为广义边图中顶点的权值，从而利用顶点的编码长度表 示权值，使得权值的处理变得更容易。具体地说，对于任一赋权连通无向图g = ( 形d ，首先通过边到点映射把图g 转换为广义边图g = ( 矿，f ) ，其中每个顶点 v f ，矿对应于图g 的一条边e ，。若图g 中边e ，与e j 邻接，则在g 中顶点和v 之间加一条无向边：若图g 中v f 的度数为奇数，则在与m 关联的边对应的g ，的 顶点上添加自环。用于编码图g 中顶点v 。7 的d n a 串s ，的长度等于图g 中边e ， 的权值。用于编码图g ，中边e 扩k ( v ，) 的d n a 串为曲的后半部分与s ，的前 半部分并置后的逆补。这种编码方法提高了用d n a 计算求解赋权图上具有边权 值的优化问题的数值表示和处理能力。 对于旅行商问题，我们首先提出了权值序号和相对长度图的概念，然后设计 了一种基于相对长度图的d n a 编码方法和一种改进的d n a 编码方法，并给出 了相应的d n a 算法。对于任一赋权连通无向图g = ( 一目，所提出的相对长度 d n a 编码方法利用权值的序号和相对长度图代替权值本身来对权值进行编码。 由于该编码方法中用于编码权值的d n a 串的长度只与权值的序号有关，与权值 i i j 东大学博+ 学位论文 本身无关，因此它能直接处理整数或实数权值，甚至很小或很大的权值，并且所 获得的最优解不与d n a 串的长度成正比，这就使得这种编码方法能处理一个较 宽范围的权值。所提出的改进d n a 编码方法用两条不同长度的d n a 串去编码 每条边，其中较长d n a 串由首段、权值段及尾段三部分组成，较短d n a 串是 较长串权值段的逆补。该编码方法是对先前的权编码方法的一种改进，改进后的 编码方法生成的是稳定的d n a 双链而不是单双交替的d n a 串，因而更容易生 成问题的最优解。 对于最小生成树问题，我们设计了一种基于顶点识别码的d n a 编码方法以 及一种基于d n a 序列的逆补比对的d n a 编码方法，并给出了相应的d n a 计 算模型。由于非线性的最小生成树不能直接用线性的d n a 串表示，因此不能直 接给出最小生成树问题的基于d n a 计算基本操作的d n a 编码方法及d n a 算 法。对于任一赋权连通无向图g = ( k 目，所提出的基于顶点识别码的d n a 编码 方法用一个长度为，= m a x ll o g a nl ，6 ) 的识别码一去编码图g 的每个顶点m ，用 一个长度为2 p = 2 m a x w 帕，) 的d n a 串s g 去编码图g 的每条边e 扩，其中呀的 长度为w 盯的前部分标记为s 。盯l ，长度为w ：，的后部分标记为s ，蛇，并对图g 的任 意两条相邻边p ：和饥，增加一个长度为w 扩毗的d n a 串j 。批= 砌( 钆蛇s 叫) 作为 附加码。基于所提出的d n a 编码方法，我们给出了最小生成树问题的一种基于 顶点识别码的d n a 算法，该算法首先获得对应于最小生成树的e u l e r 回路，然 后把e u l e r 回路转化为最小生成树。在此基础上，针对d n a 双链中碱基之间的 互补非互补、同向! i i e 同向关系，提出了d n a 序列的补比对和逆补比对的概念， 给出了d n a 序列的补比对和逆补比对的计分方法，并利用d n a 序列的逆补比 对的计分方法给出了最小生成树问题的一种新d n a 编码方法及d n a 算法。对 于任一赋权连通无向图g = ( k 司，v ，乃e e ，1 i , j 刀，其中边e 扩上的权 值为w 玎，用一个长度为，= m a x il 0 9 4 nl ，6 的识别码n 去编码每个顶点 ，用一 个长度为印= 2 m a x w ，) 的d n a 串s 矿去编码每条边e 扩，然后计算s w i j l ，归，r j 的逆补比对卵，a s w f l c 2 ，嘶，并选取d n a 串s 缈= l o w e r ( a 删2l 仅力+ l o w e r ( a , 。# x 作为附加码。基于所提出的d n a 编码方法，我们给出了最小生成树问题的一 种基于逆补比对的d n a 算法，该算法借助于e u l e r 图获得给定赋权图的最小生 成树。这种d n a 编码方法可推广到其它赋权图上优化问题的d n a 计算模型中。 山东大学博士学位论文 对于顶点赋值的最大权团问题，我们在o u y a n g 的最大团问题的d n a 计算 模型的基础上，增加了权值的d n a 编码表示，进而给出了最大权团问题的一种 改进的d n a 编码方法及d n a 算法。对于任一顶点赋权的连通无向图，我们用 两个不同长度的d n a 串去编码每个顶点，用一个长度为2 0 的d n a 串去编码每 条边。相应于项点 ，的较长d n a 串由三部分组成，其中间部分的长度为w ，相 应于顶点v ，的较短d n a 串是较长d n a 串的中间部分的逆补。在此基础上，我 们给出了最大权团问题的d n a 算法及其生物实现方法。所设计的d n a 算法的 空间复杂度为o ( d m 甜) ，刀表示给定赋权图的顶点数，以甜表示顶点的最大度数， 这比o u y a n g 的最大团问题的d n a 算法的空间复杂度略低。 此外，我们还给出了0 1 背包问题和顶点覆盖问题的d n a 编码方法和d n a 算法。对于0 1 背包问题，我们对先前的d n a 编码方法进行了一点改进，使得 连接反应生成稳定的d n a 双链而不是单双交替的d n a 串。对于顶点覆盖问题， 我们首先对先前的从顶点覆盖问题到h a n f i l t o n 回路问题的多项式变换进行了一 点改进，把具有1 2 个顶点和1 4 条边的覆盖子图改为具有4 个顶点和4 条边的改 进覆盖子图，使所构造的图g ，的顶点数从k + 1 2 1 目减少到梢旧，边数从 1 6 旧h 2 后1 ) i 减少到6 旧+ ( 觋- 1 ) i 吲，然后利用a d e m a n 实验中的基本操作给出了 顶点覆盖问题的一种基于杂交的d n a 计算模型。正如电子计算机中其它算术操 作都转换为加法操作来实现一样，d n a 计算机中其它操作也应转换为几个基本 的d n a 操作来实现，本文工作在这方面为d n a 计算提供了一定基础。 关键词：智能计算；算法；d n a 计算；d m a 编码方法；赋权图；组合优化 i i i l j i 东大学博士学位论文 a b s t r a c t f o rt h er e s e a r c ho nd n ac o m p u t i n gm e t h o d so fo p t i m i z a t i o np r o b l e m so n w e i g h t e dg r a p h ，t h em e t h o do fe n c o d i n gw e i g h t si nd n a s t r a n d si st h ek e yo fs o l v i n g t h ep r o b l e m s i nt h i sp a p e r , w ed i s c u s st h ed n a c o m p u t i n gm e t h o d so fc l a s s i c a l o p t i m i z a t i o np r o b l e m so nw e i g h t e dg r a p h ，s u c ha st h ec h i n e s ep o s t m a np r o b l e m , t h e t r a v e l i n gs a l e s m a np r o b l e m , t h em a x i m u m - w e i g h tc l i q u ep r o b l e m , a n dt h em i n i m u m s p a n n i n gt r e ep r o b l e m w ei m p r o v et h em e t h o d so fe n c o d i n gw e i g h t si nt h ep m v i o m d n ac o m p u t i n gm o d e l s ，a n dg i v es o m en e wd n aa l g o r i t h m so fs o l v i n gt h e s e p r o b l e m sb a s e do nt h ei m p r o v e dd n ae n c o d i n gm e t h o d s b yd e s i g n i n gt h eg e n e r a l e d g eg r a p ho f aw e i g h t e da n du n d i r e c t e dg r a p h ，w ep r o p o s ead n a e n c o d i n gm e t h o d a n dt h ec o r r e s p o n d i n gd n a c o m p u t i n gm o d e lf o rt h ec h i n e s ep o s t m a np r o b l e m ；b y d e s i g n i n gt h er e l a t i v el e n g t hg r a p ho f a w e i g h t e dg r a p h ，w eg i v ean e wd n ae n c o d i n g m e t h o da n dd n a c o m p u t i n gm o d e lf o rt h et r a v e l i n gs a l e s m a np r o b l e m ；b ys e l e c t i n g t h eb e s to n e so ft h er e v e r s ec o m p l e m e n ta l i g n m e n t so fd n as e q u e n c e s ，w eg i v ea d n ae n c o d i n gm e t h o da n dd n ac o m p u t i n gm o d e lb a s e do nr e v e r s ec o m p l e m e n t a l i g n m e n tf o rt h em i n i m u ms p a n n i n gt r e ep r o b l e m ；a n db yi m p r o v i n gt h ep r e v i o u s d n ae n c o d i n g m e t h o d s ，w eg i v e s o m ed n ac o m p u t i n gm o d e l sf o rt h e m a x i m u m w e i g h tc l i q u ep r o b l e m , t h ev e r t e xc o v e rp r o b l e ma n dt h e0 1k n a p s a c k p r o b l e m t h ep r o p o s e dd n ac o m p u t i n g m o d e l s i m p r o v e t h ec a p a b i l i t yo f r e p r e s e n t i n ga n dd e a l i n g 、) v i n ld a t ai nd n a s t r a n d s t h es p e c i f i cr e s e a r c hw o r k sa l ea s f o l l o w s f o rt h ec h i n e s ep o s t m a np r o b l e m ，w ef i r s tp r o p o s et h ed e f i n i t i o no fg e n e r a le d g e g r a p h ，a n dt h e nd e v i s ean e wd n ae n c o d i n gm e t h o da n dd n aa l g o r i t h mb a s e do n g e n e r a le d g eg r a p h t h ed n ae n c o d i n gm e t h o dn l a p se a c he d g eo naw e i g h t e dg r a p h t oo n ev e r t e xb ym e a n so ft h ee d g e - - t o v e r t e xm a ps oa st oc o n s t r u c tt h eg e n e r a le d g e g r a p ho ft h ew e i g h t e dg r a p h t h u s ，t h ew e i g h t so nt h ee d g e so ft h ew e i g h t e dg r a p ha r e c o n v e n e dt ot h ew e i g h t so nt h ev e r t i c e so ft h eg e n e r a le d g eg r a p h ，a n dw ec a n r e p r e s e n tt h ew e i g h t su s i n gt h el e n g t h so fd n a s t r a n d so fe n c o d i n gv e r t i c e ss oa st o l i j 东大学博士学位论文 d e a lw i t ht h ew e i g h t sm o r ee a s i l yt h a nt h ep r e v i o u sm e t h o d s s p e c i f i c a l l y , f o ra w e i g h t e da n du n d i r e c t e dg r a p hg = ( 圪目，w 0f i r s tc o n v e r ti ti n t oi t sg e n e r a le d g e g r a p hg = ( 矿，f ) t h r o u g ht h ee d g e t o v o r t e xm a p ，w h e r ee a c hv e r t e x ，矿 c o r r e s p o n d st oo n ee d g ee io ft h eg r a p hg i ft h ee d g e sp fa n d 勺a r ea d j a c e n ti ng ，w e l i n kt h ev e r t i c e sv a n d i ng ，；i ft h ev e r t e xv fi ng i sa l lo d dd e g r e eo n e ，w ea d do n e s e l f - l o o pt ot h ev e r t i c e sw h i c ha r em a p p e df r o mt h ee d g e sl i n k e dt o t h el e n g t ho f d n as t r a n ds t , w h i c hi su s e dt oe n c o d et h ev e r t e xv f i 1 1g ，i se q u a lt ot h ev a l u eo ft h e w e i g h to nt h ee d g ee ti ng t h ed n a s t r a n ds g ，w h i c hi su s e dt oe n c o d et h ee d g ee i = ( 吖，吁) ，i st h er e v e r s ec o m p l e m e n to ft h ec o n c a t e n a t i o no ft h el a s th a l fo fs ，a n dt h e f i r s th a l fo fs j t h i sd n a e n c o d i n gm e t h o dc a ni m p r o v et h ec a p a b i l i t yo fr e p r e s e n t i n g a n dd e a l i n gw i t hd a t ai nd n ac o m p u t i n gm o d e l sf o r o p t i m i z a t i o np r o b l e m so n w e i g h t e dg r a p h f o rt h et r a v e l i n gs a l e s m a np r o b l e m , w ef i r s tp r o p o s et h ed e f i n i t i o n so fo r d e r n u m b e ro fw e i g h ta n dr e l a t i v el e n g t hg r a p h ，a n dt h e nd e v i s ead n a e n c o d i n gm e t h o d b a s e do nr e l a t i v el e n g t hg r a p ha n d 锄i m p r o v e dd n a e n c o d i n gm e t h o d f o ra w e i g h t e da n du n d i r e c t e dg r a p hg = ( 巧目，t h ep r o p o s e dr e l a t i v el e n g t hd n a e n c o d i n gm e t h o de n c o d e sw e i g h t si nd n a s t r a n d sa c c o r d i n gt ot h eo r d e rn u m b e ro f w e i g h ta n dt h er e l a t i v el e n g t hg r a p hr a t h e rt h a nt h ew e i g h t st h e m s e l v e s t h i sd n a e n c o d i n gm e t h o dc a nd i r e c t l yd e a lw i t hw e i g h t so fi n t e g e ro rr e a ln u m b e r , e v e nv e r y s m a l lo rv e r yb i gw e i g h t ，a n dt h es o l u t i o no b t m n e di nt h i sm e t h o di s n tp r o p o r t i o n a lt o t h el e n g t ho fd n as t r a n ds i n c ei nt h i se n c o d i n gm e t h o d , t h el e n g t ho fd n as t r a n d u s e dt oe n c o d ew e i g h ti sr e l a t i v et ot h eo r d e rn u m b e ro fw e i g h tr a t h e rt h a nt h ew e i g h t i t s e l f t h i sm a k e st h ee n c o d i n gm e t h o dc a nd e a lw i t hw e i g h t so fw i d er a n g e t h e i m p r o v e dd n ae n c o d i n gm e t h o du s e st w od n as t r a n d so fd i f f e r e n tl e n g t h st oe n c o d e e a c he d g e ，w h e r et h el o n g e rd n as t r a n dc o n s i s t so ft h ef i r s ts e g m e n t ，t h ew e i g h t s e g m e n ta n dt h el a s ts e g m e n t ，a n dt h es h o r t e rd n as t r a n di st h er e v e r s ec o m p l e m e n t o ft h ew e i g h ts e g m e n to ft h el o n g e ro n e t h i se n c o d i n gm e t h o di sa l li m p r o v e m e n to n t h ep r e v i o u sd n a e n c o d i n gm e t h o d s ，a n di tc a nm o r ee a s i l yf i n dt h eo p t i m a ls o l u t i o n s t h a nt h ep r e v i o u so n e ss i n c ei tg e n e r a t e ss t a b l ed n ad o u b l es t r a n di n s t e a do fa l t e r n a t e d n as t r a n do rd o u b l es t r a n d v l i f 东大学博+ 学位论文 f o rt h em i n i m u ms p a n n i n gt r e ep r o b l e m , w ed e v i s ead n ae n c o d i n gm e t h o d b a s e do nr e c o g n i t i o nc o d eo fv e r t e xa n dad n ae n c o d i n gm e t h o db a s e do nr e v e r s e c o m p l e m e n ta l i g n m e n to fd n as e q u e n c e ，a n dt h e ng i v et h ec o r r e s p o n d i n gd n a c o m p u t i n gm o d e l s s i n c en o n l i n e a rm i n i m u ms p a n n i n gt r e e c a n n o tb ed i r e c t l y r e p r e s e n t e dw i t hl i n e a rd n as t r a n d , w ec a n n o td i r e c t l yd e s i g nad n ae n c o d i n g m e t h o da n dd n aa l g o r i t h mb a s e do nt h eb a s i cd n a o p e r a t i o n sf o rt h em i n i m u m s p a n n i n gt r e ep r o b l e m f o raw e i g h t e da n du n d i r e c t e dg r a p hg = ( k 目，t h ep r o p o s e d d n ae n c o d i n gm e t h o db a s e do nr e c o g n i t i o nc o d er i s eo n er e c o g n i t i o nc o d e ，o f l e n g t h ，= m a x r l o 鲫 ，6 t oe n c o d ee a c hv e r t e xma n du s eo n ed n as t r a n d sj 扩o f l e n g t h 印= 2xm a x w g , ，) t oe n c o d ee a c he d g ep 扩，w h e r et h ef i r s tp a r to fl e n g t hw g i s m a r k e dw i t hs w g l ，a n dt h el a s tp a r to fl e n g t hw gi sm a r k e dw i t hs w # 2 f o ra n yt w o a d j a c e n te d g e se ua n de i k w ea d d o n ed n as t r a n dsd 啤= - h ( s w 必叫沁o fl e n g t hw # d - w i l e a sa na d d i t i o n a lc o d e b a s e do nt h ep r o p o s e dd n a e n c o d i n gm e t h o d , w eg i v ead n a a l g o r i t h mb a s e do nr e c o g n i t i o nc o d ef o rt h em i n i m u ms p a n n i n gt r e ep r o b l e m , w h i c h f i r s to b t a i n sa ne u l e rc i r c l ea n dt h e nc o n v e r t si ti n t oam i n i m u ms p a n n i n gt r e e f u r t h e r m o r e ，b a s e do n t h er e l a t i o n so fc o m p l e m e n t n o n c o m p l e m e n ta n ds a m e o r i e n t a t i o n r e v e r s eo r i e n t a t i o nb e t w e e nt h eb a s e si nd n ad o u b l es t r a n d ，w ep r o p o s e t h ed e f i n i t i o n so fc o m p l e m e n ta l i g n m e n ta n dr e v e r s ec o m p l e m e n ta l i g n m e n ta n dg i v e am e t h o do fc o m p u t i n gt h es c o r e so fc o m p l e m e n ta l i g n m e n ta n dr e v e r s ec o m p l e m e n t a l i g n m e n t a n dt h e nw ed e v i s ead n ae n c o d i n gm e t h o da n dad n aa l g o r i t h mb a s e d o nr e v e r s ec o m p l e m e n ta l i g n m e n t sf o rt h em i n i m u ms p a n n i n gt r e ep r o b l e m f o ra w e i g h t e da n du n d i r e c t e dg r a p hg = ( k 司，kp 亨e1 i ，j 刀，w h e r et h e w e i g h to ne d g ep i sw 扩，w eu s eo n er e c o g n i t i o nc o d eno fl e n g t h ，= m a x r l 0 9 4 n l ，6 t oe n c o d ee a c hv e r t e xv fa n du s eo n ed n a s t r a n d s 曲o fl e n g t h 劲= 2xm a x w # ， t o e n c o d ee a c he d g ep 盯a n dt h e nw ec o m p u t et h er e v e r s ec o m p l e m e n ta l i g n m e n t 护， 蝴，叼o fs i ，i r i ，s w 0 2 ，吩，a n ds e l e c td n a s t r a n ds a f 沙2l o w e r ( a , w 0 2i 嘲+ l o w e r ( a n 吲# l 嘲a sa na d d i t i o n a lc o d e b a s e do nt h ep r o p o s e dd n ae n c o d i n gm e t h o d , w eg i v ea d n a a l g o r i t h mb a s e do nr e v e r s ec o m p l e m e n ta l i g n m e n tf o rt h em i n i m u ms p a n n i n g t r e ep r o b l e m , w h i c ho b t a i n sam i n i m u ms p a n n i n gt r e eb ym e a n so fe u l e rg r a p h t h i s d n ae n c o d i n gm e t h o dc a nb eg e n e r a l i z e dt oo t h e ro p t i m i z a t i o n p r o b l e m so n v i 【l j 东大学博士学位论文 w e i g h t e dg r a p h f o rt h em a x i m u m - w e i g h tc l i q u ep r o b l e m , w ea d dw e i g h tr e p r e s e n t a t i o ni nd n a s t r a n d so nt h eb a s i so fo u y a n g sd n a c o m p u t i n gm o d e lf o rt h em a x i m u mc l i q u e p r o b l e m , a n dt h e nw eg i v ea l li m p r o v e dd n ae n c o d i n gm e t h o da n dd n aa l g o r i t h m f o rt h em a x i m u m - w e i g h tc l i q u ep r o b l e m f o raw e i g h t e da n du n d i r e c t e dg r a p h 、i t h w e i g h t so nv e r t i c e s ，w eu s et w od n as t r a n d so fd i f f e r e n tl e n g t h st oe n c o d ee a c h v e r t e xa n du s eo n ed n as t r a n d 澌mal e n g t ho f2 0t oe n c o d ee a c he d g e t h el o n g e r d n as t r a n dc o r r e s p o n d i n gt ov e r e xv fc o n s i s t so ft h r e ep a r t sa n di t sc e n t e rp a r ti s w i t hal e n g t ho fw j ；t h es h o r t e rd n as t r a n di st h er e v e r s ec o m p l e m e n to ft h el o n g e r o n e sc e n t e rp a r t b a s e do nt h ed n a e n c o d i n gm e t h o d , w eg a v ead n aa l g o r i t h mo f s o l v i n gt h em a x i m u m w e i g h tc l i q u ep r o b l e ma n di t sb i o l o g i c a li m p l e m e n t a t i o n t h e p r o p o s e dd n aa l g o r i t h mi sw i t hs p a c ec o m p l e x i t yo fo ( 厶，w h e r e 刀d e n o t e st h e n u m b e ro ft h ev e r t i c e so nt h eg i v e ng r a p ha n d 厶口d e n o t e st h em a x i m u md e g r e eo f t h ev e r t i c e so ni t i no u y a n g sa l g o r i t h mo fs o l v i n gt h em a x i m u mc l i q u ep r o b l e m , t h e s p a c ec o m p l e x i t yi sd ，) s i n c et h ed e g r e eo fa n yv e r t e xo nag r a p hi sa l w a y sl e s s t h a nt h en u m b e ro ft h ev e r t i c e so nt h eg r a p h ，t h es p a c ec o m p l e x i t yi nt h ep r o p o s e d d n a a l g o r i t h mi sl e s st h a nt h a ti no u y a n g sa l g o r i t h m b e s i d e s ，w eg i v ed n ae n c o d i n gm e t h o d sa n dd n aa l g o r i t h m sf o rt h e0 1 k n a p s a c kp r o b l e ma n dt h ev e r t e xc o v e rp r o b l e m f o rt h e0 1k n a p s a c kp r o b l e m , w ed o al i t t l ei m p r o v e m e n to nt h ep r e v i o u sd n ae n c o d i n gm e t h o d ss ot h a ti tg e n e r a t e s s t a b l ed n ad o u b l es t r a n d si n s t e a do fa l t e m a n td n as t r a n do rd o u b l es t r a n di nt h e s i n g l el i g a t i o nr e a c t i o n f o rt h ev e r t e xc o v e rp r o b l e m , w ef i r s ti m p r o v et h ep r e v i o u s p o l y n o m i a lt r a n s f o r m a t i o nf r o ma n yi n s t a n c eo ft h ev e r t e xc o v e rp r o b l e mt ot h a to f h a m i l t o nc i r c l ep r o b l e m ，t h a ti s ，t h ec o v e rs u b g r a p hw i t h12v e r t i c e sa n dlge d g e si s c h a n g e dt ot h ei m p r o v e dc o v e rs u b g r a p h 、析t l l4v e r t i c e sa n d4e d g e ss ot h a tt h e n u m b e ro fv e r t i c e si nt h ec o n s t r u c t e dg r a p hg i sr e d u c e dt o 斛4 j 司f r o m 斛12 阎a n d t h en u m b e ro fe d g e si sr e d u c e dt o6 旧h 2 k - 1 ) lr r lf r o m l 6 旧i + ( 2 k - 1 ) 1r 5 a n dt h e nw e g i v eah y b r i d - b a s e dd n aa l g o r i t h mf o rt h ev e r t e xc o v e rp r o b l e mb ym e a n so ft h e b a s i co p e r a t i o n su s e di na d l e m a n se x p e r i m e n t s j u s ta so t h e ra r i t h m e t i c a lo p e r a t i o n s 山东大学博士学位论文 c o m p u t e r , o t h e ro p e r a t i o n si nd n a b a s e dc o m p u t e rs h o u l db ec o n v e r t e dt os e v e r a l b a s i cd n a o p e r a t i o n s o u rw o r kp r o v i d e sa c e r t a i nf o u n d a t i o ni nt h i sa s p e c to fd n a c o m p u t i n g k e y w o r d s ：i n t e l l i g e n tc o m p u t i n g ；a l g o r i t h m ；d n ac o m p u t i n g ；d n ae n c o d i n g m e t h o d ；w e i g h t e dg r a p h ；c o m b i n a t o r i a lo p t i m i z a t i o n i i 山东大学博士学位论文 符号说明 d n a d e o x y r i b o n u c l e i ca c i d , 脱氧核糖核酸 c p p ：t h ec h i n e s ep o s t m a np r o b l e m , 中国邮递员问题 t s p ：t h et r a v e l i n gs a l e s m a np r o b l e m , 旅行商问题 m s t ：t h em i n i m u m s p a n n i n gt r e ep r o b l e m , 最小生成树问题 r c v ：r e c o g n i t i o nc o d eo f v e r t e x , 顶点识别码 c a ：c o m p l e m e n ta l i g n m e n t ，补比对 r c a ：r e v e r s ec o m p l e m e n ta l i g n m e n t , 逆补比对 m c p t h em a x i m u m c l i q u ep