dna词设计改进禁忌搜索算法

《dna词设计改进禁忌搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cnImprovedTabooSearchAlgorithmforDesigningDNAWordsKaiZhang,JinXu,XiutangGeng,JianhuaXiao,andLinqiangPan?KeyLaboratoryofImageProcessingandIntelligentControlDepartmentofControlScienceandEngineeringHuazhongUniversityofScienceandTechnologyWuhan430074,Chinazhangkaicn@sin

2、a.com,jxu@mail.hust.edu.cngxt1028@163.com,jhxiao2008@163.com,lqpan@mail.hust.edu.cnAbstract.ThedesignofDNAsequencesisoneofthemostpracticalandimportantresearchtopicsinDNAcomputing.Weadopttaboosearchalgorithmandimprovedthemethodforthesystematicdesignofequal-lengthDNAsequences,whichcouldsa

3、tisfycertaincombinatorialandthermodynamicconstraints.Usingtaboosearchalgorithm,ourmethodcanavoidtrappingintolocaloptimizationandcan¯ndgreatestDNAsequencessetswhichsatisfyrequiredconstraints.Keywords:DNAComputing;TabooSearchAlgorithm;DNASequencesDesign1IntroductionSinceAdleman[1]¯rstlypr

4、esentedtheexperimentbyusingmolecularbiologytosolvea7-vertexinstanceofHamiltonianPathProblemin1994,DNAcomputingshowsgreatpotentialtosolvepainstakingproblemssuchastheNP-completeproblems.DNAsequencesdesignisoneofthemostpracticalandimportantresearchtopicsinDNAcomputing.Inordertoobtainsucces

5、sfulresultsofbiologicalexperiments,wemustdesigne®ectiveDNAsequencesfortargetcomputationalproblem.TherehasbeenagreatdealofpreviousworkindesigningDNAsequences[2][3][4][5].Inparticular,Frutos[6][7]etal.proposedthetemplatemethodforDNAworddesign.Feldkamp[8]demonstratedaDNAsequencecompileralg

6、orithmfordesigningDNAsequences.Reaton[9][10][11]presentedageneticalgorithmforgeneratingDNAstrands.However,theobviousdisadvantageofthecurrentDNAgeneratoralgorithmisthepossibilityofbeingtrappedinlocaloptimizationwhichmaybefarfromtheglobaloptimalsolution.Taboosearchisageneraltechniquepropo

7、sedbyGlover[12][13]forobtainingapproximatesolutionstocombi-natorialoptimizationproblems.Taboosearchavoidsbeingtrappedintolocalminimumbyallowingthetemporalacceptanceofworsesolution.Andithasbeensuccessfullyappliedtoawiderangeofcombinatorialoptimizationproblemssuchasjobshopschedul