子集和问题的O（1．414^n）链数DNA计算机算法.doc

子集和问题的O（1．414^n）链数DNA计算机算法 第3O卷第11期 2007年11月 计算机 CHINESEJOURNAL OFCOMPUTERS Vol_3ONO.11 NOV.2007 子集和问题的0(1.414)链数DNA计算机算法 李肯立姚凤娟许进李仁发 (湖南大学计算机与通信学院长沙410082) (华中科技大学分子生物计算机研究所武汉430074) 摘要随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重 要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman—Lipton模型的操作与粘贴模型的解 空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行有哪些信誉好的足球投注网站器,提出一种求解子集和问题的DNA计算机模 型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的 DNA分子链数从O(2)减少至O(1.414),其中,2为子集和问题的维数.因此,文中算法理论上在试管级生化反应 条件下能将可破解子集和公钥的维数从6O提高到120. 关键词DNA计算;子集和问题;分治法;并行处理;NP完全问题 中图法分类号TP301 AnO(1.414)VolumeMolecularSolutionsfortheSubset-SumProblemon DNA-BasedSupercomputing LIKen-Li,YAOFeng-JuanXUJinLIRen—Fa (SchoolofComputerandCommunication,HunanUniversity,Changsha410082) (InstituteofBiomolecularComputer,HuazhongUniversityofScienceandTechnology,Wuhan430074) AbstractHOWtodecreasethevolumesinDNAcomputershasbecomeanimportantresearchar— eainDNAcomputing.ItisshowedthatthepoorscalabilityintheDNA—basedalgorithmsrootsin thepoorscalabilityoftheDNAmodels.Inthispaper,aDNAmodelforgoodscalahilityispro— posed.ItisbasedonbiologicaloperationsintheAdleman—Liptonmodelandthesolutionspaceof stickersinthesticker-basedmode1.Themethodoffluorescencelabelingandthetechniqueofgel e1ectrophoresisareincorporatedintothemode1.Basedonit,anewDNAalgorithmforsolutionof thesubset—sumproblemisproposedwherethestrategyofdivideandconquerandanewdesigned algorithmofParalle1Searcherareintroduced.Theproposedalgorithmcansolvethe一dimension subset-suminstancesbyusingtheO(1.414)shorterDNAstrandsontheconditionofnotvar- yingthetimecomplexity,ascomparedbyfarthebestmolecularalgorithmforitinwhichO(2) DNAstrandsisused.Therefore,thescaleofthepublickeycryptosystemthatcanbetheoretically brokenusingthepresentbiologicaltechnologymaybeenlargedfrom60to120variables. KeywordsDNA—basedcomputing;subset—sumproblem;divideandconquer;parallelprocess— ing;NP—completeproblem 收稿日期:2006—10—24;最终修改稿收到日期:2007—09—15.本课题得到国家自然科学基金60503002和中国博士后科 学基金(20060400845)资助.李肯立,男,1971年生,博士,教授,中国计算机学会高级会员,研究领域