胡 娟 李 冬 张丽丽

（1.淮南职业技术学院 基础部，安徽 淮南232001；2.淮南工业学校 电子组，安徽 淮南232001；3.安徽理工大学 理学院，安徽 淮南232001）

0 引言

DNA 首次用于计算是1994 年Adleman 用此解决了有向Hamilton 路问题,从此DNA 计算模型以其高度并行性和海量存储功能解决了大量NP 完全问题， 也使人们对DNA 计算机产生了浓厚的兴趣。 DNA 编码序列设计问题也是该领域研究的核心问题之一，寻找到高质量DNA 序列已成为DNA 编码序列优化设计一个热点。

虽然DNA 计算在许多领域都取得了巨大进展，但编码，生物技术等问题还需进一步解决。 而且，目前还没有一种通用的好方法来解决编码问题。目前制约DNA 编码的约束条件有两种：距离约束和热力学约束。 距离约束有海明距离（HD），海明反距离（RH），海明反补距离（RC）等；热力学约束有GC 含量，自由能ΔG，解链温度Tm等。

在本文中， 我们主要选择海明距离和反海明距离这两个约束条件，首先用遗传算法获得大量的集合，满足组合约束。 然后，使用改进的遗传算法来获得大量的集合，以满足组合约束。 最后将这个结果与遗传算法比较，结果证明改进的遗传算法是优于基本遗传算法的。

1 约束条件

Garzon 首先提出了DNA 计算的编码问题的定义。即以DNA 分子的四个碱基为字母表∑={A，T，C，G},设一长度为n 的DNA 分子的编码集合为S，有|S|=4n，则对S 的子集C⊆S 有：

式中k∈Z+，τ 为评价准则，显然，编码质量和编码数量两者是相互矛盾的。 在满足一定质量的条件下，约条件束越多，就会减少DNA序列的编码数目来满足约束。

在本文中，我们使用海明距离，海明反距离和海明反补距离。 设DNA 序列的长度为n，海明距离，海明反距离和海明反补距离为d。

1.1 海明距离约束

海明距离约束：两个序列xi和xj之间的汉明距离大于或等于某参数d，即

式中f′Hamming（i）为第i 个进化过程中对海明约束的评价。在这里，海明距离码的最大值我们用AHD4 （n，d）来表示。

1.2 海明反距离约束

海明反距离约束： 两个序列xi和之间的汉明距离大于或等于某参数d，即其中是xi的反序列。

1.3 优化功能

我们使用平均权重处理功能来评价每个约束。

式中每个约束的权重为ωj，评价项的个数为m。

2 遗传算法

2.1 基本遗传算法

基本遗传算法首先要随机生成新的DNA 序列， 计算各个序列的适应度函数值来满足海明距离和海明反距离组合约束;然后利用遗传算子生成满足海明距离和海明反距离组合约束条件下的新的DNA 序列，从而获得满足条件的DNA 序列的集合。

具体步骤如下：

1）设置参数，并随机生成初始群体。

2）计算各个适应度函数值，从而满足海明距离和海明反距离组合约束。

3）通过选择、交叉和变异算子生成下一代个体。 如果下一代小于3000，转到2，如果不是进入4。

4）结束和输出结果。

2.2 改进的遗传算法

为了获得更多的满足约束条件的DNA 序列的， 通过控制个体的适应度函数值来进行改进。 如下：

（1）在计算个体的适应度函数值上，使用动态的方式进化个体。

（2）在选择阶段，使用最省策略。

（3）在变异阶段，调整变异与动态方法操作的可能性。

主要过程如下：用DNA 序列生成动态遗传算法，通过控制进化适应度函数值来选择序列，以生成满足海明距离和海明反补距离约束条件下的序列，然后通过选择、交叉和变异算子生成新的DNA 序列，获得DNA 序列集。

3 仿真实验

改进的遗传算法使用的参数： 初始群体规模为40， 交叉概率为0.7，变异概率被为0.03，下一代是500。列表1 是在满足海明距离和海明反距离约束条件下由遗传算法获得的DNA 的界限序集。 表2 是在满足海明距离和海明反距离条件下由改进的遗传算法获得的DNA 的界限序集。 对每个值我们都做了做5 次的试验。

从表1，表2 中可以发现，当n 在不断增加时，AR（n，d）的值也在增加。 可见计算的复杂性迅速增加。

表1 中，粗体的部分都大于或等于以前下界值，‘-’表示不存在的值。其它则是小于以前的下界值。表2 中，粗体的部分大于以前的下界值，‘！ ’表示大于或等于表1 中的值。

表1 基于GA 的（n，d）结果Table1 results of （n，d） by GA

表1 基于GA 的（n，d）结果Table1 results of （n，d） by GA

?

表2 基于改进的GA 的（n，d）的结果Table2 results of （n，d） by Dynamic GA

表2 基于改进的GA 的（n，d）的结果Table2 results of （n，d） by Dynamic GA

?

根据表1，与表2 比较，我们可以看到，改进的遗传算法比遗传算法更好地地满足了组合约束。

4 结论

在本文中，利用遗传算法和改进的遗传算法来设计满足海明距离和反海明距离约束条件的DNA 序列，通过两种方法所得结果的比较，证明了改进的遗传算法是优于遗传算法的。 当n 增加，若个体的数量增加，下代的数量也可能增加。同时计算复杂度和时间也在增加。必须看到，虽然对DNA 计算做了大量的研究，但其理论研究的深度和广度都还有所欠缺，为此，还需要更深入研究DNA 编码，从而设计出满足组合约束的好的DNA 编码序列。

［1］Holland J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975.

［2］Deaton R，Murphy R C，Rose J A，et al.A DNA based implementationof an evolutionary search for good encodings for DNAcomputation [C]//Proceedings of IEEE Conference on EvolutionaryComputation，Indianapolis，IL.Los Alamitos，CA：IEEE Computer SocietyPress，1997：267-271.

［3］Wood DH，Chen J.Physical separation of DNA according to royalroad fitness[C]//Proceedings of IEEE Conference on EvolutionaryComputation.Washington，CA：IEEE Computer Society Press，1999：1016-1025.

［4］Feldkamp U，Raube H，Banzhaf W.Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4（2）：153-171.

［5］Marathe A.On combinatorial DNA word design [J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44：75-88.

［6］张凯，肖建华.基于汉明距离的DNA 编码约束研究[J].计算机工程与应用，2008，44（14）：24-26.

［7］Shin S Y,Lee I H，Kim Detal.Multiobjective evolut ionary optimization of DNA sequences for reliable DNA computing[J].IEEE Transactions on Evolutionary Comput ation，2005,9(2):143-158.

［8］Deaton R.and Garzon M.Thermodynamic Constraints on DNA -based Computing，in Computing with Bio-Molecues:Theory and Expirements.ed.G.Paun[M].Springer-Verlag:Singapore,1998：138-152.

［9］Deaton R.,Francescheti D.R.,GarzonM.,RoseJ.A.,MurphyR.C.,and Stevens S.E Information transfer through hybridyzation reaction in DNA based computing[J].Proceedings of the Second Annual Conference,1997,July 13 -16，Stanford University,.Morgan Kaufmann,San F rancisco：463-471.

［10］Deaton R.et al.A DNA Based Implementation of an Evolutionary Computation Proceedings IE EEC onference on Evolutionary Computation[J].In diana,1997：267-271.

［11］Marathe, A.; Condon, A. E.; Corn, R. M. On Combinatorial DNA word Design[J].DI MACS Ser ies in Discrete M athematics and Theoretical Computer Science,1999;Vol.44 ：75-87.

［12］RoseJ.A.,The Fidelity of DNA computation[D].The University of Memphis,1999,11.

［13］Xiao J H,Jin X,Chen Z H,et al.A hybrid quantum chaotic swarm evolutionary algorithm or DNA encoding[J].Computers& Mathematics with Applications,2009, 57(11/12):1949-1958.

［14］Marathe A,Condon A,Corn R.On combinatorial DNA word design[J].Journal of Computational Biology，2001，8(3)：201-220.