在赋权图上优化问题的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的一条边e_i。若图G中边e_i与e_j邻接,则在G′中顶点v′_i和v′_j之间加一条无向边;若图G中v_i的度数为奇数,则在与v_i关联的边对应的G′的顶点上添加自环。用于编码图G′中顶点v′_i的DNA串s_i的长度等于图G中边e_i的权值。用于编码图G′中边e′_ij=（v′_i,v′_j）的DNA串S_ij为s_i的后半部分与S_j的前半部分并置后的逆补。这种编码方法提高了用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{[log₄n],6}的识别码r_i去编码图G的每个顶点v_i,用一个长度为2p=2×max{w_ij,l)的DNA串S_ij去编码图G的每条边e_ij,其中S_ij的长度为W_ij的前部分标记为S_wij1,长度为W_ij的后部分标记为S_wij2,并对图G的任意两条相邻边e_ij和e_jk,增加一个长度为w_ij+W_jk的DNA串S_aijk=-h(S_wij2S_wjk1)作为附加码。基于所提出的DNA编码方法,我们给出了最小生成树问题的一种基于顶点识别码的DNA算法,该算法首先获得对应于最小生成树的Euler回路,然后把Euler回路转化为最小生成树。在此基础上,针对DNA双链中碱基之间的互补/非互补、同向/非同向关系,提出了DNA序列的补比对和逆补比对的概念,给出了DNA序列的补比对和逆补比对的计分方法,并利用DNA序列的逆补比对的计分方法给出了最小生成树问题的一种新DNA编码方法及DNA算法。对于任一赋权连通无向图G=（V,E）,v_i∈V,e_ij∈E,l≤i,j≤n,其中边e_ij上的权值为W_ij,用一个长度为l=max([log₄n],6}的识别码r_i去编码每个顶点v_i,用一个长度为2p=2×max{W_ij,l)的DNA串S_ij去编码每条边e_ij,然后计算S_wij1,S_wij2,r_j的逆补比对α_swij1,α_swjk2,α_rj,并选取DNA串S_aijk=Lower(α_swij2|α_rj)+Lower(α_swjk1|α_rj)作为附加码。基于所提出的DNA编码方法,我们给出了最小生成树问题的一种基于逆补比对的DNA算法,该算法借助于Euler图获得给定赋权图的最小生成树。这种DNA编码方法可推广到其它赋权图上优化问题的DNA计算模型中。对于顶点赋值的最大权团问题,我们在Ouyang的最大团问题的DNA计算模型的基础上,增加了权值的DNA编码表示,进而给出了最大权团问题的一种改进的DNA编码方法及DNA算法。对于任一顶点赋权的连通无向图,我们用两个不同长度的DNA串去编码每个顶点,用一个长度为20的DNA串去编码每条边。相应于顶点v_i的较长DNA串由三部分组成,其中间部分的长度为w_i,相应于顶点v_i的较短DNA串是较长DNA串的中间部分的逆补。在此基础上,我们给出了最大权团问题的DNA算法及其生物实现方法。所设计的DNA算法的空间复杂度为O(d_maxⁿ),n表示给定赋权图的顶点数,d_max表示顶点的最大度数,这比Ouyang的最大团问题的DNA算法的空间复杂度O（nⁿ）略低。此外,我们还给出了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计算提供了一定基础。