基于二维DNA分子tiler自组装求解最大团问题  

The solution to the maximum clique problem based on two-dimensional DNA tiles self-assemble

作　　者：冯婷[1] 张倩[1] 董亚非[1,2] 

机构地区：[1]陕西师范大学生命科学学院,陕西西安710062 [2]陕西师范大学计算机科学学院,陕西西安710062

出　　处：《郑州轻工业学院学报（自然科学版）》2011年第4期94-97,共4页Journal of Zhengzhou University of Light Industry:Natural Science

基　　金：国家自然科学基金项目(60970005);陕西师范大学2008年重点项目

摘　　要：针对常用算法在求解完全NP问题中最大团问题时,存在实验操作步骤过多、活体内不易操作以及环化效率不高等问题,设计了一种用二维DNA(k-臂DNA分子)结构来解决最大团问题的方法.该方法将二维DNA分子设计为分子tiler,通过二维DNA分子构建三维DNA图结构并建立计算模型,以减少解决问题所需的时间和步骤.该算法是求解最大团问题的一种可以降低复杂度的新算法,对DNA计算和DNA计算机的研究是一次有意义的实践.Because there are some disadvantages of traditional algorithms in solving maximum clique problem—one of the NP complete problems,such as too many experimental steps,uneasiness to operate in vivo,and low cyclization efficiency,a 2D DNA（k-arm DNA molecule） structure was designed to solve the maximum clique problem.In order to reduce the time and steps required in resolving this problem,the method is that the 2D DNA molecular was designed as molecular tiles and the computation model was obtained by using the 3D DNA tiles to build the 3D DNA structure chart.This algorithm reduces the complexity of calculation for solving the maximum clique problem,and it is also a meaningful practice for DNA computing and DNA computer research.

关 键 词：DNA计算 最大团问题 k-臂DNA分子 纳米金DNA探针 

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