基于改进的粒子群遗传算法的DNA编码序列优化

第33卷　第2期2010年2月

计　　算　　机　　学　　报

CHINESEJOURNALOFCOMPUTERS

Vol.33No.2

Feb.2010

基于改进的粒子群遗传算法的DNA编码序列优化

崔光照

1),2)

　李小广　张勋才

1)2)

1)1),2)

　王延峰

1),2)

　李翠玲

(郑州轻工业学院电气信息工程学院　郑州　450002)(河南省信息化电气重点实验室　郑州　450002)

摘　要　在DNA计算中,DNA编码序列的设计是影响DNA计算可靠性的重要手段.在不同的DNA序列设计中,应该选择适当的约束条件,并且根据相应的约束条件提出每个DNA应该相应满足的评估公式.文中从DNA编码设计应满足的多约束条件中选取适当的约束条件,提出评估公式,优化问题.,.关键词　DNA计算;DNA编码;多目标优化;中图法分类号TP301　　　DOI号:10.TheBasedonModifiedPSO/GAAlgorithm

CUIGuang2Zhao1)

),2)

))))))

　LIXiao2Guang1　ZHANGXun2Cai1,2　WANGYan2Feng1,2　LICui2Ling1

(SchoolofElectricalandElectronicEngineering,ZhengzhouUniversityofLightIndustry,Zhengzhou　450002)

(HenanKeyLaboratoryofInformation2basedElectricalAppliances,Zhengzhou　450002)

Abstract　ThedesignofDNAsequenceisimportantinimprovingthereliabilityofDNAcompu2ting.SomeappropriateconstrainedtermsthatDNAsequenceshouldsatisfyareselected,andthentheevaluationformulasofeachDNAindividualcorrespondingtotheselectedconstrained

termsareproposed.ModifiedParticleSwarmOptimization/GeneticAlgorithm(MPSO/GA)ispresentedtosolvethemulti2objectiveoptimizationproblem.AtlastthecomparisonoftheresultswiththeknownDNAsequencesinfitnessfunctionvalueismadetoprovethefeasibilityandeffi2ciencyofthemethod.

Keywords　DNAcomputing;DNAcoding;multi2objectiveoptimization;modifiedparticleswarmoptimization/geneticalgorithm

1　引　言

美国加州大学的Adleman博士[122]利用现代分子生物技术提出7个顶点的哈密尔顿有向路问题的DNA分子生物算法,并且成功地在DNA溶液的试管中进行了实验,成为DNA计算发展的里程碑.总

的来说,DNA计算可以分为3个步骤:首先是编码,也就是把具体的问题映射到DNA分子链上;其次是通过各种生物酶的作用,在适当的条件下,使所代表问题的各个DNA分子链进行充分的混合杂交反应;最后是萃取阶段,即把杂交反应的结果还原为原问题的解.

通过DNA计算的过程可以知道,编码问题是

收稿日期:2009207206;最终修改稿收到日期:2009211217.本课题得到国家自然科学基金(60573190,60773122,60970084)、河南省基础与前沿技术研究项目([1**********]3,[1**********]6)和河南省科技创新人才计划(科技创新杰出青年)([1**********]2)资助.崔光照,男,

1957年生,博士,教授,主要研究领域为DNA计算、基因网络以及信息控制等.E2mail:[email protected].李小广,男,1983年生,硕士

研究生,主要研究方向为DNA计算.张勋才,男,1981年生,博士,副教授,主要研究方向为智能信息处理、算法分析与设计等.王延峰,男,1973年生,博士,副教授,主要研究方向为DNA计算、基因网络.李翠玲,女,1984年生,硕士研究生,主要研究方向为信息安全.

312计　　算　　机　　学　　报2010年

首要问题.一个好的DNA编码序列就是能够确保

随后进行的各种生化反应不出现任何错误,而且反应产物中包含有足够多的稳定可靠的能够被成功提取的原始问题的解.在实际的操作过程中,DNA编码设计就要通过序列优化尽量减少DNA计算过程中的错误杂交.错误杂交的类型可以分为两种:第一是假阳性,也就是不完全互补的DNA分子在适当的条件下能够杂交形成双链分子;第二是假阴性,也就是完全互补的DNA分子在反应过程中由于种种原因而没有杂交.假阳性主要是由于杂交的两个DNA分子间的序列有足够的“相似度”而造成的;而假阴性则主要是由反应条件及生化操作本身的失误引起的.为了确保DNA计算结果的可靠性,就必须最大限度地降低错误杂交的可能性.们利用各种约束条件来筛选序列DNA计算的需要.[324]

度为n的DNA分子的编码集合S,显然|S|=4n.求

τ(si,sj)Εk.S的一个子集CΑS使得Πsi,sj∈C满足其中K为正整数,τ是评价编码性质的准则,如汉明距离、GC含量等.

接下来的问题就是要在寡核苷酸空间中找到合

适的评价编码性质的准则τ以及确定各个DNA编码约束条件的复杂性.如前所述,DNA编码问题实质是多目标组合优化问题,也就是说编码要同时满足多个目标约束.这个问题将在第4节给出.

3　.,是一种通过模拟自然进化过程搜索最优解的方法,它最初由美国Michigan大学Holland教授于1975年首先提出来的.遗传算法以决策变量的编码作为运算对象,而不需要待解决问题的具体领域信息,同时它也不受搜索空间是否连续或者可微的限制.遗传算法主要可以分为4个部分:初始状态的确立、适应度函数的制定、遗传操作的进行以及控制参数的选取.

编码机制是遗传算法的基础.首先要创建一个随机的初始状态,即初始解,将这些解比喻为染色体或基因,该种群被称为第一代.接着对每一个解(染色体)指定一个合理的适应度值,根据问题求解的实际接近程度来指定.然后就是各种进化操作(选择、交叉和变异).在以上的各种操作过程中,控制参数的选取是不可忽略的因素,适当地选取可以使算法得到令人满意的结果.图1为基本遗传算法的流程图

、连续性约束、

解链温度、GC基于这些约束条件,Frutos等提出了模板编码方法[4],Feldkamp提出了一个设计DNA序列的DNA序列编译算法[5],Deaton提出了遗传算法来设计DNA序列.

DNA编码问题实质上是满足多约束条件的多目标组合优化问题.文献[8]用基本遗传算法针对多个约束条件产生了较好的序列,其中约束条件是针对每代群体的所有个体所提出的.本文将改进的粒子群算法(MPSO)[9210]与基本遗传算法(SGA)[8]相结合,提出了改进的粒子群遗传算法(MPSO/GA)来对DNA序列进行优化,同时提出了针对单个个体的约束条件评估公式.在遗传算法的基础上,结合改进的粒子群算法,产生出了与之前文献相比更好的DNA序列.

[627]

2　基本编码问题

DNA编码问题是DNA计算中的核心问题,它

创造性地将现实问题映射为特殊的编码DNA分子序列.这些DNA分子序列应能够确保随后进行的生化反应不出现任何错误,而且反应产物中须包含有足够多的、稳定可靠的、能被成功提取的原始问题的解.一个好的编码序列就是要最大限度地促进期望的杂交,同时限制不期望杂交的发生,综合平衡各个反应条件,从而为最后解的提取提供有力支持.

概括来讲,DNA编码问题可以表述为:在DNA分子的4个碱基ΣDNA={A,G,C,T}上,存在一个长

图1　遗传算法流程图

2期崔光照等:基于改进的粒子群遗传算法的DNA编码序列优化313

3.2　改进的粒子群优化算法

粒子群算法自诞生以来就以其规则简单,易于编程实现成为处理多目标优化问题的重要工具.传统的粒子群算法是求解连续优化问题的有力工具,但是对于离散问题却无能为力.这里我们引入了四进制粒子群算法用于求解DNA编码这样的离散空间问题.

(1)传统粒子群算法:传统粒子群算法是受鸟群觅食行为的启发而提出的,其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解.该算法将每个个体看作是搜索空间中的一个没有体积的微粒,并且在搜索空间中从一个随机初始位置(xi)和随机初始速度(vi)飞行.每个粒子代表解空间的一个候选解,.找到的最优解,.每个粒子都通过上述两个极值(个体最优解和整体最优解)不断地更新自己,从而产生新一代群体.对于第t次迭代,粒子i将根据下面的公式来更新自己的位置和速度:

vid

t+1

其中f(v)被定义如下:

0,rand()1,rand()

f(v)=

2,rand()3,rand()

>r&rand()

Φr&rand()ΕS(v)Εr&rand()ΕS(v)

(3)扰动策略的引入:经典的粒子群算法的粒

子们在搜索过程中,总是追逐当前全局最优点和自己迄今搜索到的最优点,因此速度会很快降低到接近于0,容易陷入局部最优值.我们课题组的秦利敏等人在文献[10]

引入了扰动策略:即如果迄今搜索到的全局最优适应值连续u,那么r,重置它们的速度.,,r为[0,1]上.Ift-tu>u,Thenresetv,其中tu表示最近一次更新搜索到的全局最优点适应值的迭代步.图2为改进的粒子群算法流程图.

=w×vtid+c1×rand()×(pid-xtid)+

　　c2×rand()×(pgd-xtid)

xid

t+1

=xtid+vti

d+1

其中rand()是均匀分布于(0,1)区间的随机数,c1,c2为学习因子,ω为惯性权值,pid为个体极值,pgd为群体极值.粒子在解空间中不断跟踪个体极值与全局极值进行搜索,直到达到规定的迭代次数或者满足规定的误差标准为止.

(2)四进制粒子群算法:基于传统粒子群算法的不足,Kenndy和Eberhart在文献[11]提出了一种二进制离散型PSO算法[12]用于解决组合优化问题,在一定程度上完善发展了传统粒子群算法.这里我们对文献[11]进行了改进,在离散四进制空间中,粒子xid要趋向于判决选择为0,1,2和3,由参数vid决定一个概率选择阈值,如果偏高,粒子就会更可能选择为0,1;如果偏低,就更倾向于选择2,3.并且这个阈值位于[0,1]范围之内,这里引入sigmoid函数:S(vid)=1/(1+exp(-vid)),改进后的速度和位置更新公式如下:

vid

t+1

图2　改进粒子群算法流程图

3.3　改进的粒子群遗传算法(MPSO/GA)

该算法是以基本遗传算法为基础,同时将改进的粒子群算法作为遗传算法的一个重要算子,具体算法步骤如下:

1.设定参数,并随机产生初始种群;

2.计算每个个体的适应度函数值,并且按照适应度函

=w×vtid+c1×rand()×(pid-xtid)+

数值进行排序;

3.判断是否满足目标条件(包括程序收敛以及达到指

　　c2×rand()×(pgd-xtid)

t+1

定的进化代数),如果满足,结束进程,输出结果;否则进行下一步;

=Mod((xtid+f(v

t+1id

)),4

)

314计　　算　　机　　学　　报2010年

4.更新个体种群.根据适应度函数值的大小确定一部示所指定的GC含量,其计算公式如下:

GC(x)=

分个体直接进入下一代种群,剩余个体通过MPSO算法优化过后进入下一代种群;

5.对新一代种群执行遗传算法的复制、交叉和变异等

|x|

其中#G和#C分别表示序列x里面的碱基G和C的个数,|x|表示序列x里碱基总个数.

(2)连续性约束.如果DNA序列里某一字母连

操作,转步2.

该算法的流程图如图3所示

续出现(比如出现“AAAA”或者“GGGG”,那么DNA结构就会变得不稳定.

fCon(xi)=-

j=1

∑

(j-1)N(ji)

(2)

其中N(ji)表示同一字母在指定j次的次数.

(3).DNA分

n-2・pinlenn-pinlen-[r/2]

Hairpin(xi)=

r=5

∑

c=pinlen+[r/2]

∑

Hairpin(xi,c)(3)

其中,r为形成发卡最小的环长度;pinlen为形成发卡茎所应有的最小长度.并且Hairpin(xi,c)定义如下:

Hairpin(xi,c)=

1,0,

d(xi,c)>pinlen/2d(xi,c)Φpinlen/2

其中d(xi,c)表示序列xi沿其c点折叠两段序列的逆补距离.

(4)Hamming距离约束.在DNA序列编码设

计中,Hamming距离描述了两个不同DNA序列之

图3　MPSO/GA算法流程图

间的非相似程度.为了减少不同DNA序列之间的相似性从而避免错误杂交的产生,一般要求两个DNA序列xi和xj之间的Hamming距离不小于某

4　算法约束条件

通过很多的算法与文献,我们已经知道,越来越

多的约束条件被用于评估DNA编码的好坏.例如GC含量约束、Tm值约束、连续性约束、二级结构约束、汉明距离约束、自由能约束等等.但是通过文献[13]我们可以知道并不需要把每个约束条件考虑在内.综合目前DNA计算中的主要组合约束,我们选取了以下几个方面作为评估项.

(1)GC含量约束.GC含量就是碱基G和C在一个DNA分子序列里所占总碱基的比重.

由于碱基G和C之间有3个氢键连接,而碱基A和T之间有两个氢键连接,所以GC含量对保持序列的化学性质的稳定性非常重要.一般要求GC(x)∈[40,60].

(1)fGC(xi)=-|GC(xi)-GC(xi)defined|

其中GC(xi)表示序列xi的GC含量,GC(xi)difined表

个阈值d,即H(xi,xj)Εd.

fHamming(xi)=

1ΦjΦn,j≠i

min{H(xi,xj)}(4)

(5)逆距离约束.与Hamming距离相似,要求

序列xi和序列xj的逆序列xRj之间的Hamming距离不小于某个阈值d.

fInverse(xi)=min{H(xi,xj)}

1ΦjΦn

(5)

(6)适应度函数设计.本文所定义的多目标优

化问题属于最大化问题,我们采用加权平均法来处理每个DNA个体各约束项的评估函数:

Fitness(xi)=

j=1

∑w

(6)

其中m是评估项个数,wj为各个评估项fj的权重,并且有

fj∈{fGC(xi),f

(xi),fCon(xi),

fHaipin(xi),fHamming(xi)}.

2期崔光照等:基于改进的粒子群遗传算法的DNA编码序列优化315

(2)MPSO算法.最大进化代数为200,学习因子分

5　算法仿真结果及分析

针对以上约束条件以及目标函数设计编码序列模型,在Matlab710环境下,使用MPSO/GA算法进行仿真,运行环境是PentiumDualE2104,116GHz,512MB,MicrosoftXP.参数设置如下:(1)基本遗传

别为c1=2,c2=118,惯性权重因子w从2降低到018,扰动因子u=10,最大速度为4.

为了评价本算法所产生的DNA序列的性能,我们将所得到结果与文献[8]的结果进行了比较.表1和表2分别列出了本算法以及文献[8]所产生的DNA序列编码的数据分析.其中“Hd”表示Hamming距离“,Id”表示逆距离.

算法.最大进化代数为300,种群规模为20,DNA序列编码长度为20,交叉率为0185,变异率为01005.

表1　MPSO/GA算法产生的DNA序列

)DNA序列(5′23′

GC成分/%

505050

-10--1-1-3-3

-10-1-10-2

Fitnessvalue

[1**********]734

CGTGTGCAGTACTGAGTATGAGTAGTTCTCAGACGCTGCTGCATGATCGATCTCGTCAGAATCGGTAGTCGTAGACGTCTTTGCAGTCAGTCGACTAGTGTACGCTCACGAAGT[1**********]2

1413131312

表2　文献[8]所产生的DNA序列

)DNA序列(5′23′

GAGTTAGATGTCACGTCACGAGGCGAGTAGGGGTATATCTTTATGATTCCACTGGCGCTCCCTGTCAACATTGACGCTCACGCTCCATCCTTGATCGTTTATCGTACTCATGGTCCCTACCTTCGCTGCTGATAACCTCA

GC成分/%

[1**********]050

Continuity

-1-4-4-3-5-3-3

Hairpin-4-10-2-2-2-1

Fitnessvalue

[1**********]828

[1**********]111

[1**********]0

从表1与表2可以明显看到,MPSO/GA算法明显比文献[8]算法的适应度函数有所改进,同时在图4指出了该算法的进化收敛图.其中横轴表示进化代数,竖轴表示适应度函数值(每代群体经过排序后最差个体的适应度值).由图4可以看出,算法具有较好的收敛性.

6　结论与展望

本文从DNA编码的多个约束条件选取合适的约束,通过将多约束转化为多目标优化问题,提出了MPSO/GA算法对DNA计算中的编码序列实现了优化,通过与前人对比,产生了较好的DNA序列,验证了该算法的可行性和有效性.当然,进一步的工作可以结合其他的智能优化算法,进而增强算法的寻优能力并且尽量减小陷入局部最优的概率.

参考

[1][2]

文献

AdlemanLM.Molecularcomputationofsolutiontocombi2natorialproblems.Science,1994,66(11):102121024AdlemanLM.Onconstructingamolecularcomputer.Com2puterScienceDepartment,UniversityofSouthernCalifornia,USA:TechnicalReportTR792387,1995

图4　MPSO/GA算法的进化收敛图

316

[3]

计　　算　　机　　学　　报

DeatonR,GarzonM.ThermodynamicconstraintsonDNA2basedcomputing//GheorghePauneds.ComputingwithBio2Molecules,Springer2Verlag,1998:1382152

[9]

2010年

IEEETransactionsonEvolutionaryComputation,2005,9(2):1432158

CuiGZ,NiuYY,WangYFetal.AnewapproachbasedonPSOalgorithmtofindgoodcomputationalencodingse2quences.ProgressinNaturalScience,2007,17(6):7122716

[10]

CuiGZ,QinLMetal.ModifiedPSOalgorithmforsolvingplanargraphcoloringproblem.ProgressinNaturalScience,2008,18(3):3532357

[11]

KennedyJ,EberhardR.Adiscretebinaryversionofthepar2ticleswarmoptimization//ProceedingsoftheIEEEInterna2tionalConferenceonSystem,Man,andCybernetics.Orlan2do,Florida,1997:410424108

[12]

FatihMandLiangY.AbinaryswarmoptimizationalgorithmforlotofEconomicandSo2cial,,5(2)]

,YamamotoMetal.DevelopingforsequencedesigninDNAcomputing//Pro2ceedingsofthe7thInternationalWorkshopDNA2BasedCom2puters.Tampa,FL,USA,2001:3402

349

[4]FrutosAG,LiuQ,ThielAJetal.DemonstrationofaworddesignstrategyforDNAcomputingonsurfaces.NucleicAcidsRes,1997,25(23):474824757

[5]FeldkampU,BanzhafW,RauheHetal.ADNAsequencecompiler//Proceedingsofthe6thDIMACSWorkshoponDNABasedComputers,Leiden,NE,2000

[6]DeatonR.ADNAbasedimplementationofanevolutionarysearchforgoodencodingsforDNAcomputation//Proceed2ingsofthe1997IEEEInternationalConferenceonEvolution2aryComputation.Indianapolis,IN,USA,1997:2672271

[7]DeatonRJ,MurphyRC,GarzonMHetal.Goodencod2ingsforDNA2basedsolutionstocombinatorialproblems//ProceedingsoftheDNA2BasedComputersII.AMSDIMACSSeries44,Princeton,1998:2472258

[8]ShinSY,LeeIH,KimDetal.optimizationofDNACUIGuang2Zhao,bornin1957,Ph.D.,professor.HiscurrentresearchinterestsincludeDNAcomputing,genenetworksandinformationcontrol.

ZHANGXun2Cai,bornin1981,Ph.D.,associatepro2fessor.Hisresearchinterestsincludeintelligentcomputationandalgorithmanalysisanddesign.

WANGYan2Feng,bornin1973,Ph.D.,associatepro2fessor.Hisresearchinterestsincludeintelligentcomputationandgenenetworks.

LICui2Ling,bornin1984,M.S.candidate.Herre2

LIXiao2Guang,bornin1983,M.S.candidate.Hisre2searchinterestsfocusonDNAcomputing.

searchinterestsfocusoninformationsecurity.

Background

ThispaperissupportedbytheNationalNaturalScienceFoundationofgramof

China

(grant

No160573190,60773122,

No.

[1**********]3,

60970084),BasicandFrontierTechnologyResearchPro2

Henna

Province

(grant

[1**********]6),andInnovationScientistandTechniciansTroopConstructionProjectsofNo[1**********]22).

TherearethreepartsinDNAcomputing:encodingthatmapstheproblemsontoDNAstrands,hybridizationthat

HennaProvince(grant

performsthebasiccoreprocessingandextractionthatmakestheresultsvisibletothenakedeye.DNAencodingproblem,whichhasbeenprovedtobeanNPhardproblem,isakeyproblemforDNAcomputing,andusuallysolvedbyoptimi2zationalgorithms.Inthispaperanewefficientgeneticalgo2rithmforthedesignofDNAcodewordispresented.Somepropercodedesigncriteriasareselectedtoimprovethecod2ingoftheDNAsequences.Simulationresultsshowthismethodisfeasibleandefficient.

第33卷　第2期2010年2月

计　　算　　机　　学　　报

CHINESEJOURNALOFCOMPUTERS

Vol.33No.2

Feb.2010

基于改进的粒子群遗传算法的DNA编码序列优化

崔光照

1),2)

　李小广　张勋才

1)2)

1)1),2)

　王延峰

1),2)

　李翠玲

(郑州轻工业学院电气信息工程学院　郑州　450002)(河南省信息化电气重点实验室　郑州　450002)

CUIGuang2Zhao1)

),2)

))))))

　LIXiao2Guang1　ZHANGXun2Cai1,2　WANGYan2Feng1,2　LICui2Ling1

(SchoolofElectricalandElectronicEngineering,ZhengzhouUniversityofLightIndustry,Zhengzhou　450002)

(HenanKeyLaboratoryofInformation2basedElectricalAppliances,Zhengzhou　450002)

Keywords　DNAcomputing;DNAcoding;multi2objectiveoptimization;modifiedparticleswarmoptimization/geneticalgorithm

1　引　言

通过DNA计算的过程可以知道,编码问题是

1957年生,博士,教授,主要研究领域为DNA计算、基因网络以及信息控制等.E2mail:[email protected].李小广,男,1983年生,硕士

312计　　算　　机　　学　　报2010年

首要问题.一个好的DNA编码序列就是能够确保

度为n的DNA分子的编码集合S,显然|S|=4n.求

τ(si,sj)Εk.S的一个子集CΑS使得Πsi,sj∈C满足其中K为正整数,τ是评价编码性质的准则,如汉明距离、GC含量等.

接下来的问题就是要在寡核苷酸空间中找到合

、连续性约束、

解链温度、GC基于这些约束条件,Frutos等提出了模板编码方法[4],Feldkamp提出了一个设计DNA序列的DNA序列编译算法[5],Deaton提出了遗传算法来设计DNA序列.

[627]

2　基本编码问题

DNA编码问题是DNA计算中的核心问题,它

概括来讲,DNA编码问题可以表述为:在DNA分子的4个碱基ΣDNA={A,G,C,T}上,存在一个长

图1　遗传算法流程图

2期崔光照等:基于改进的粒子群遗传算法的DNA编码序列优化313

3.2　改进的粒子群优化算法

vid

t+1

其中f(v)被定义如下:

0,rand()1,rand()

f(v)=

2,rand()3,rand()

>r&rand()

Φr&rand()ΕS(v)Εr&rand()ΕS(v)

(3)扰动策略的引入:经典的粒子群算法的粒

=w×vtid+c1×rand()×(pid-xtid)+

　　c2×rand()×(pgd-xtid)

xid

t+1

=xtid+vti

d+1

vid

t+1

图2　改进粒子群算法流程图

3.3　改进的粒子群遗传算法(MPSO/GA)

该算法是以基本遗传算法为基础,同时将改进的粒子群算法作为遗传算法的一个重要算子,具体算法步骤如下:

1.设定参数,并随机产生初始种群;

2.计算每个个体的适应度函数值,并且按照适应度函

=w×vtid+c1×rand()×(pid-xtid)+

数值进行排序;

3.判断是否满足目标条件(包括程序收敛以及达到指

　　c2×rand()×(pgd-xtid)

t+1

定的进化代数),如果满足,结束进程,输出结果;否则进行下一步;

=Mod((xtid+f(v

t+1id

)),4

)

314计　　算　　机　　学　　报2010年

4.更新个体种群.根据适应度函数值的大小确定一部示所指定的GC含量,其计算公式如下:

GC(x)=

分个体直接进入下一代种群,剩余个体通过MPSO算法优化过后进入下一代种群;

5.对新一代种群执行遗传算法的复制、交叉和变异等

|x|

其中#G和#C分别表示序列x里面的碱基G和C的个数,|x|表示序列x里碱基总个数.

(2)连续性约束.如果DNA序列里某一字母连

操作,转步2.

该算法的流程图如图3所示

续出现(比如出现“AAAA”或者“GGGG”,那么DNA结构就会变得不稳定.

fCon(xi)=-

j=1

∑

(j-1)N(ji)

(2)

其中N(ji)表示同一字母在指定j次的次数.

(3).DNA分

n-2・pinlenn-pinlen-[r/2]

Hairpin(xi)=

r=5

∑

c=pinlen+[r/2]

∑

Hairpin(xi,c)(3)

其中,r为形成发卡最小的环长度;pinlen为形成发卡茎所应有的最小长度.并且Hairpin(xi,c)定义如下:

Hairpin(xi,c)=

1,0,

d(xi,c)>pinlen/2d(xi,c)Φpinlen/2

其中d(xi,c)表示序列xi沿其c点折叠两段序列的逆补距离.

(4)Hamming距离约束.在DNA序列编码设

计中,Hamming距离描述了两个不同DNA序列之

图3　MPSO/GA算法流程图

间的非相似程度.为了减少不同DNA序列之间的相似性从而避免错误杂交的产生,一般要求两个DNA序列xi和xj之间的Hamming距离不小于某

4　算法约束条件

通过很多的算法与文献,我们已经知道,越来越

(1)GC含量约束.GC含量就是碱基G和C在一个DNA分子序列里所占总碱基的比重.

由于碱基G和C之间有3个氢键连接,而碱基A和T之间有两个氢键连接,所以GC含量对保持序列的化学性质的稳定性非常重要.一般要求GC(x)∈[40,60].

(1)fGC(xi)=-|GC(xi)-GC(xi)defined|

其中GC(xi)表示序列xi的GC含量,GC(xi)difined表

个阈值d,即H(xi,xj)Εd.

fHamming(xi)=

1ΦjΦn,j≠i

min{H(xi,xj)}(4)

(5)逆距离约束.与Hamming距离相似,要求

序列xi和序列xj的逆序列xRj之间的Hamming距离不小于某个阈值d.

fInverse(xi)=min{H(xi,xj)}

1ΦjΦn

(5)

(6)适应度函数设计.本文所定义的多目标优

化问题属于最大化问题,我们采用加权平均法来处理每个DNA个体各约束项的评估函数:

Fitness(xi)=

j=1

∑w

(6)

其中m是评估项个数,wj为各个评估项fj的权重,并且有

fj∈{fGC(xi),f

(xi),fCon(xi),

fHaipin(xi),fHamming(xi)}.

2期崔光照等:基于改进的粒子群遗传算法的DNA编码序列优化315

(2)MPSO算法.最大进化代数为200,学习因子分

5　算法仿真结果及分析

别为c1=2,c2=118,惯性权重因子w从2降低到018,扰动因子u=10,最大速度为4.

算法.最大进化代数为300,种群规模为20,DNA序列编码长度为20,交叉率为0185,变异率为01005.

表1　MPSO/GA算法产生的DNA序列

)DNA序列(5′23′

GC成分/%

505050

-10--1-1-3-3

-10-1-10-2

Fitnessvalue

[1**********]734

CGTGTGCAGTACTGAGTATGAGTAGTTCTCAGACGCTGCTGCATGATCGATCTCGTCAGAATCGGTAGTCGTAGACGTCTTTGCAGTCAGTCGACTAGTGTACGCTCACGAAGT[1**********]2

1413131312

表2　文献[8]所产生的DNA序列

)DNA序列(5′23′

GAGTTAGATGTCACGTCACGAGGCGAGTAGGGGTATATCTTTATGATTCCACTGGCGCTCCCTGTCAACATTGACGCTCACGCTCCATCCTTGATCGTTTATCGTACTCATGGTCCCTACCTTCGCTGCTGATAACCTCA

GC成分/%

[1**********]050

Continuity

-1-4-4-3-5-3-3

Hairpin-4-10-2-2-2-1

Fitnessvalue

[1**********]828

[1**********]111

[1**********]0

6　结论与展望

参考

[1][2]

文献

图4　MPSO/GA算法的进化收敛图

316

[3]

计　　算　　机　　学　　报

DeatonR,GarzonM.ThermodynamicconstraintsonDNA2basedcomputing//GheorghePauneds.ComputingwithBio2Molecules,Springer2Verlag,1998:1382152

[9]

2010年

IEEETransactionsonEvolutionaryComputation,2005,9(2):1432158

CuiGZ,NiuYY,WangYFetal.AnewapproachbasedonPSOalgorithmtofindgoodcomputationalencodingse2quences.ProgressinNaturalScience,2007,17(6):7122716

[10]

CuiGZ,QinLMetal.ModifiedPSOalgorithmforsolvingplanargraphcoloringproblem.ProgressinNaturalScience,2008,18(3):3532357

[11]

KennedyJ,EberhardR.Adiscretebinaryversionofthepar2ticleswarmoptimization//ProceedingsoftheIEEEInterna2tionalConferenceonSystem,Man,andCybernetics.Orlan2do,Florida,1997:410424108

[12]

FatihMandLiangY.AbinaryswarmoptimizationalgorithmforlotofEconomicandSo2cial,,5(2)]

,YamamotoMetal.DevelopingforsequencedesigninDNAcomputing//Pro2ceedingsofthe7thInternationalWorkshopDNA2BasedCom2puters.Tampa,FL,USA,2001:3402

349

[4]FrutosAG,LiuQ,ThielAJetal.DemonstrationofaworddesignstrategyforDNAcomputingonsurfaces.NucleicAcidsRes,1997,25(23):474824757

[5]FeldkampU,BanzhafW,RauheHetal.ADNAsequencecompiler//Proceedingsofthe6thDIMACSWorkshoponDNABasedComputers,Leiden,NE,2000

[6]DeatonR.ADNAbasedimplementationofanevolutionarysearchforgoodencodingsforDNAcomputation//Proceed2ingsofthe1997IEEEInternationalConferenceonEvolution2aryComputation.Indianapolis,IN,USA,1997:2672271

[7]DeatonRJ,MurphyRC,GarzonMHetal.Goodencod2ingsforDNA2basedsolutionstocombinatorialproblems//ProceedingsoftheDNA2BasedComputersII.AMSDIMACSSeries44,Princeton,1998:2472258

[8]ShinSY,LeeIH,KimDetal.optimizationofDNACUIGuang2Zhao,bornin1957,Ph.D.,professor.HiscurrentresearchinterestsincludeDNAcomputing,genenetworksandinformationcontrol.

ZHANGXun2Cai,bornin1981,Ph.D.,associatepro2fessor.Hisresearchinterestsincludeintelligentcomputationandalgorithmanalysisanddesign.

WANGYan2Feng,bornin1973,Ph.D.,associatepro2fessor.Hisresearchinterestsincludeintelligentcomputationandgenenetworks.

LICui2Ling,bornin1984,M.S.candidate.Herre2

LIXiao2Guang,bornin1983,M.S.candidate.Hisre2searchinterestsfocusonDNAcomputing.

searchinterestsfocusoninformationsecurity.

Background

ThispaperissupportedbytheNationalNaturalScienceFoundationofgramof

China

(grant

No160573190,60773122,

No.

[1**********]3,

60970084),BasicandFrontierTechnologyResearchPro2

Henna

Province

(grant

[1**********]6),andInnovationScientistandTechniciansTroopConstructionProjectsofNo[1**********]22).

TherearethreepartsinDNAcomputing:encodingthatmapstheproblemsontoDNAstrands,hybridizationthat

HennaProvince(grant

基于改进的粒子群遗传算法的DNA编码序列优化

相关内容

热门内容

标签