赋权图上优化问题的DNA计算方法研究

论文摘要

在赋权图上优化问题的DNA计算方法研究中,权值的DNA编码方法是求解问题的关键。本文讨论了中国邮递员、旅行商、最大权团、最小生成树等赋权图上经典优化问题的DNA计算方法,改进了它们原有DNA计算模型中的权值编码方法,给出了利用改进DNA编码方法求解的新DNA算法。我们通过设计赋权无向图的广义边图给出了中国邮递员问题的一种DNA编码方法及计算模型,通过设计赋权图的相对长度图给出了旅行商问题的一种DNA编码方法及计算模型,通过选取DNA序列的最佳逆补比对给出了最小生成树问题的基于逆补比对的一种DNA编码方法及计算模型,并通过改进已有的DNA编码方法给出了最大权团问题、顶点覆盖问题及0/1背包问题的DNA计算模型。我们给出的DNA计算模型提高了DNA计算中数值表示和处理能力。具体研究工作如下:对于中国邮递员问题,我们首先提出了广义边图的概念,然后设计了一种新的基于广义边图的DNA编码方法及DNA算法。所提出的广义边图DNA编码方法利用边到点映射把赋权图中的边映射为顶点,构造给定赋权图的广义边图,使得赋权图中的边权值转换为广义边图中顶点的权值,从而利用顶点的编码长度表示权值,使得权值的处理变得更容易。具体地说,对于任一赋权连通无向图G=（V,E）,首先通过边到点映射把图G转换为广义边图G′=（V′,E′）,其中每个顶点v′i∈V′对应于图G的一条边ei。若图G中边ei与ej邻接,则在G′中顶点v′i和v′j之间加一条无向边;若图G中vi的度数为奇数,则在与vi关联的边对应的G′的顶点上添加自环。用于编码图G′中顶点v′i的DNA串si的长度等于图G中边ei的权值。用于编码图G′中边e′ij=（v′i,v′j）的DNA串Sij为si的后半部分与Sj的前半部分并置后的逆补。这种编码方法提高了用DNA计算求解赋权图上具有边权值的优化问题的数值表示和处理能力。对于旅行商问题,我们首先提出了权值序号和相对长度图的概念,然后设计了一种基于相对长度图的DNA编码方法和一种改进的DNA编码方法,并给出了相应的DNA算法。对于任一赋权连通无向图G=（V,E）,所提出的相对长度DNA编码方法利用权值的序号和相对长度图代替权值本身来对权值进行编码。由于该编码方法中用于编码权值的DNA串的长度只与权值的序号有关,与权值本身无关,因此它能直接处理整数或实数权值,甚至很小或很大的权值,并且所获得的最优解不与DNA串的长度成正比,这就使得这种编码方法能处理一个较宽范围的权值。所提出的改进DNA编码方法用两条不同长度的DNA串去编码每条边,其中较长DNA串由首段、权值段及尾段三部分组成,较短DNA串是较长串权值段的逆补。该编码方法是对先前的权编码方法的一种改进,改进后的编码方法生成的是稳定的DNA双链而不是单双交替的DNA串,因而更容易生成问题的最优解。对于最小生成树问题,我们设计了一种基于顶点识别码的DNA编码方法以及一种基于DNA序列的逆补比对的DNA编码方法,并给出了相应的DNA计算模型。由于非线性的最小生成树不能直接用线性的DNA串表示,因此不能直接给出最小生成树问题的基于DNA计算基本操作的DNA编码方法及DNA算法。对于任一赋权连通无向图G=（V,E）,所提出的基于顶点识别码的DNA编码方法用一个长度为l=max{[log4n],6}的识别码ri去编码图G的每个顶点vi,用一个长度为2p=2×max{wij,l)的DNA串Sij去编码图G的每条边eij,其中Sij的长度为Wij的前部分标记为Swij1,长度为Wij的后部分标记为Swij2,并对图G的任意两条相邻边eij和ejk,增加一个长度为wij+Wjk的DNA串Saijk=-h(Swij2Swjk1)作为附加码。基于所提出的DNA编码方法,我们给出了最小生成树问题的一种基于顶点识别码的DNA算法,该算法首先获得对应于最小生成树的Euler回路,然后把Euler回路转化为最小生成树。在此基础上,针对DNA双链中碱基之间的互补/非互补、同向/非同向关系,提出了DNA序列的补比对和逆补比对的概念,给出了DNA序列的补比对和逆补比对的计分方法,并利用DNA序列的逆补比对的计分方法给出了最小生成树问题的一种新DNA编码方法及DNA算法。对于任一赋权连通无向图G=（V,E）,vi∈V,eij∈E,l≤i,j≤n,其中边eij上的权值为Wij,用一个长度为l=max([log4n],6}的识别码ri去编码每个顶点vi,用一个长度为2p=2×max{Wij,l)的DNA串Sij去编码每条边eij,然后计算Swij1,Swij2,rj的逆补比对αswij1,αswjk2,αrj,并选取DNA串Saijk=Lower(αswij2|αrj)+Lower(αswjk1|αrj)作为附加码。基于所提出的DNA编码方法,我们给出了最小生成树问题的一种基于逆补比对的DNA算法,该算法借助于Euler图获得给定赋权图的最小生成树。这种DNA编码方法可推广到其它赋权图上优化问题的DNA计算模型中。对于顶点赋值的最大权团问题,我们在Ouyang的最大团问题的DNA计算模型的基础上,增加了权值的DNA编码表示,进而给出了最大权团问题的一种改进的DNA编码方法及DNA算法。对于任一顶点赋权的连通无向图,我们用两个不同长度的DNA串去编码每个顶点,用一个长度为20的DNA串去编码每条边。相应于顶点vi的较长DNA串由三部分组成,其中间部分的长度为wi,相应于顶点vi的较短DNA串是较长DNA串的中间部分的逆补。在此基础上,我们给出了最大权团问题的DNA算法及其生物实现方法。所设计的DNA算法的空间复杂度为O(dmaxn),n表示给定赋权图的顶点数,dmax表示顶点的最大度数,这比Ouyang的最大团问题的DNA算法的空间复杂度O（nn）略低。此外,我们还给出了0/1背包问题和顶点覆盖问题的DNA编码方法和DNA算法。对于0/1背包问题,我们对先前的DNA编码方法进行了一点改进,使得连接反应生成稳定的DNA双链而不是单双交替的DNA串。对于顶点覆盖问题,我们首先对先前的从顶点覆盖问题到Hamilton回路问题的多项式变换进行了一点改进,把具有12个顶点和14条边的覆盖子图改为具有4个顶点和4条边的改进覆盖子图,使所构造的图G′的顶点数从k+12|E|减少到k+4|E|,边数从16|E|+（2k-1）|V|减少到6|E|+（2k-1）|V|,然后利用Adleman实验中的基本操作给出了顶点覆盖问题的一种基于杂交的DNA计算模型。正如电子计算机中其它算术操作都转换为加法操作来实现一样,DNA计算机中其它操作也应转换为几个基本的DNA操作来实现,本文工作在这方面为DNA计算提供了一定基础。

论文目录

• 摘要
• ABSTRACT
• 符号说明
• 前言
• 第1章 DNA计算的基础知识
• 1.1 DNA单链的方向性
• 1.2 Watson-Crick碱基互补原则及DNA双链的方向性
• 1.3 DNA计算的基本操作
• 第2章 中国邮递员问题的广义边图DNA编码方法及计算模型
• 2.1 中国邮递员问题
• 2.2 广义边图的定义及其构建
• 2.3 基于广义边图的DNA编码方法
• 2.4 基于广义边图的DNA算法
• 2.5 DNA算法的理论基础
• 2.6 DNA算法的生物实现及复杂性分析
• 2.7 与已有权编码方法的比较
• 2.8 小结
• 第3章 旅行商问题的相对长度DNA编码方法及计算模型
• 3.1 旅行商问题
• 3.2 权值序号与相对长度图的概念
• 3.3 基于相对长度图的DNA编码方法
• 3.4 基于相对长度图的DNA算法
• 3.5 与Narayanan方法的比较
• 3.6 基于顶点的改进DNA编码方法
• 3.7 小结
• 第4章 最小生成树问题的DNA编码方法及计算模型
• 4.1 最小生成树问题
• 4.2 基本概念及计分方法
• 4.2.1 顶点的识别码
• 4.2.2 DNA序列的补比对和逆补比对
• 4.2.3 补比对和逆补比对的计分方法
• 4.3 最小生成树问题的基于识别码的DNA编码方法及DNA算法
• 4.3.1 基于识别码的DNA编码方法
• 4.3.2 基于识别码的DNA算法及生物实现
• 4.3.3 DNA算法的理论基础
• 4.4 最小生成树问题的基于逆补比对的DNA编码方法及DNA算法
• 4.4.1 基于逆补比对的DNA编码方法
• 4.4.2 基于逆补比对的DNA算法及生物实现
• 4.5 小结
• 第5章 最大权团问题的DNA编码方法及计算模型
• 5.1 最大权团问题
• 5.2 最大权团问题的DNA编码方法
• 5.3 最大权团问题的DNA算法
• 5.4 DNA算法的生物实现
• 5.5 与Ouyang算法的比较
• 第6章 顶点覆盖与0/1背包问题的DNA编码方法及计算模型
• 6.1 顶点覆盖问题的DNA编码方法及计算模型
• 6.1.1 顶点覆盖问题
• 6.1.2 改进覆盖子图与选择顶点的概念
• 6.1.3 顶点覆盖问题到Hamilton回路问题的多项式变换
• 6.1.4 基于多项式变换的DNA编码方法
• 6.1.5 基于多项式变换的DNA算法及生物实现
• 6.1.6 与其它DNA编码方法的比较
• 6.2 0/1背包问题的DNA编码方法及计算模型
• 6.2.1 0/1背包问题
• 6.2.2 0/1背包问题的DNA编码方法
• 6.2.3 0/1背包问题的DNA算法
• 6.2.4 DNA算法的生物实现
• 6.2.5 与其它DNA编码方法的比较
• 6.3 小结
• 结束语
• 参考文献
• 致谢
• 攻读博士学位期间的学术论文目录
• 在读期间参与科研项目情况
• 学位论文评阅及答辩情况表
• 正式发表的英文论文
• 1 DNA Solution Based on Sequence Alignment to the MST Problem
• 2 RLM:A New Method of Encoding Weights in DNA Strands