一种基于DNA自组装模型求解最大团问题的算法  

An Algorithm for Solving Maximum Clique Problem Based on Self-Assembly Model of DNA

作　　者：周炎涛[1] 李肯立[2] 罗兴[2] 黎福海[1] 朱青[1] 

机构地区：[1]湖南大学电气与信息工程学院,湖南长沙410082 [2]湖南大学信息科学与工程学院,湖南长沙410082

出　　处：《湖南大学学报（自然科学版）》2012年第9期39-44,共6页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金资助项目(61173013)

摘　　要：基于tiles理论模型和已有DNA自组装模型,结合最大团问题给出基于DNA自组装模型的算法设计,得到具体设计初始分子、规则分子和检测分子所需的DAE块种类.在此基础上采用荧光标记和凝胶电泳生物操作提出了一种求解最大团问题算法.该算法设计tiles的种类为Θ(n2+|E|),其生物操作复杂性为Θ(1).此算法降低了实验的复杂度,而且保证了实验的易操作性和结果的准确性。On the basis of tiles theory model and the existing self-assembly model, an algorithm based on DNA self-assembly model was presented for maximum clique problem, and the corresponding DAE blocks designed in particular for initial molecular, rules of molecular and the detection of molecular were given. Then, an algorithm for solving maximum clique problem was presented with the biologic operation of fluorescence labeling and gel electrophoresis. The proposed algorithm needs O（n2＋｜E｜ ） types of tiles, and the complexity of experiment operation was 19（1）. This algorithm can reduce the complexity of the ex- periment, and ensure the ease of experiment and the accuracy of results.

关 键 词：DNA序列 最大团问题 DNA自组装模型 

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