基于三链DNA结构的0-1整数规划改进研究  

Improvement of 0-1 integer programming based on triple-stranded DNA structure

作　　者：任晓玲[1] 白雪[1] 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院,济南250014

出　　处：《计算机应用研究》2013年第1期56-59,77,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61170038);山东省自然科学基金资助项目(ZR2011FM001);国家教育部人文社会科学研究项目(12YJA630152);山东省社会科学基金资助项目(11CGLJ22);山东省高等学校科技计划资助项目(J12LN22;J12LN65)

摘　　要：为实现DNA计算中对解的有效筛选,防止探针与探针之间的错配、发夹结构等,以及便于检测最终解,提出了改进的三链DNA模型求解0-1规划的设计。该方法编码n个变量的每种组合的所有排列情况。此编码方式不仅使计算所需有效分子量从O((2n)!)下降到O(2nn!),并使对可行解的筛选更加有效。利用寡聚脱氧核苷酸(ODN)在RecA蛋白介导下与同源的双链DNA匹配成三螺旋DNA的特点,可推广到更多以双链DNA分子为计算模型的解的检测中。To realize the effective screening of solutions in DNA computing and to prevent the mismatch between probes,the formation of the hairpin structure etc,this paper presented an improved triple-stranded DNA model to solve 0-1 integer programming problem.This method made a full array of all combinations of n 0-1 variables.Compared with the original one,the amount of DNA strands needed dropped from O（（2n）!） to O（2nn!） and the improved one made a better selection of feasible solutions.Triple-helix structure could be constructed by the homologous double-helix DNA with the oligodeoxyribonucleotides（ODN） in the mediated of RecA protein.It could make use of its special structure to promote it to the selection of solutions with the double-helix computing model.

关 键 词：三链DNA 0-1整数规划 DNA计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]