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

摘要：

【摘要】为实现DNA计算中对解的有效筛选,防止探针与探针之间的错配、发夹结构等,以及便于检测最终解,提出了改进的三链DNA模型求解0-1规划的设计。该方法编码n个变量的每种组合的所有排列情况。此编码方式不仅使计算所需有效分子量从O((2n)!)下降到O(2nn!),并使对可行解的筛选更加有效。利用寡聚脱氧核苷酸(ODN)在RecA蛋白介导下与同源的双链DNA匹配成三螺旋DNA的特点,可推广到更多以双链DNA分子为计算模型的解的检测中。
【关键词】三链DNA； 0-1整数规划； DNA计算；
【基金】国家自然科学基金资助项目(61170038);山东省自然科学基金资助项目(ZR2011FM001);国家教育部人文社会科学研究项目(12YJA630152);山东省社会科学基金资助项目(11CGLJ22);山东省高等学校科技计划资助项目(J12LN22,J12LN65)

引言：

【引言】1957 年，Feisenfeld 等人提出了三链核酸的概念。由于双链DNA 中两条相互缠绕且方向相反的链是依靠互补碱基对之间的氢键相连，碱基对又偏向螺旋轴一侧，所以在两条链之间形成了大小两沟。三链DNA 正是在双链DNA 的基础上，通过含有多聚嘌呤的那条链，以Hoogsteen 和反式Hoogsteen 型氢键与新加入的第三条链相连接形成的，且第三条链位于双链DNA 的大沟中，主要有嘧啶—嘌呤—嘧啶和嘌呤—嘌呤—嘧啶两种类型。2004 年，Shigemori 等人发现寡聚脱氧核苷酸能在RecA蛋白及ATPγS 的存在下与双链DNA 形成稳定的三链结构。由于三链DNA 在形成过程中不会发生错配和形成发夹结构，而且反应后得到的解为双链形式，比较稳定，不会像单链DNA 因为过长而形成发夹结构或断裂。因此，基于三链结构DNA 计算的错误率和编码复杂度会降低。

作者：

任晓玲；白雪；刘希玉

作者单位：

山东师范大学管理科学与工程学院；