基于自组装模型的最大团问题DNA计算算法  

An Algorithm in Tile Assembly Model for Maximum Clique Problem

作　　者：李肯立[1] 罗兴[1] 吴帆[1] 周旭[1] 黄鑫[1] 

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

出　　处：《计算机研究与发展》2013年第3期666-675,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61133005;61070057;61202109;61173013);国家科技支撑计划基金项目(2012BAH09B02);湖南省杰出青年基金项目(12JJ011)

摘　　要：DNA计算在解决NP完全问题时,有着传统图灵机无法比拟的优势.但是随着DNA计算研究的不断深入,传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点.如何提高DNA计算结果的准确性在DNA计算研究中日显重要.针对NP完全的最大团问题,引入DNA自组装模型,提出了一种求解最大团问题的DNA计算算法.算法通过减少实验的操作步骤数,以降低生化解的错误率,给出了DNA分子的编码方案及结果检测的实验方法.算法设计的tiles种类为Θ(n+|E|),生化操作复杂性为Θ(1),其中n为图的顶点数,|E|为边数.与求解最大团问题的其他DNA算法的对比分析表明,本算法不仅明显提高了生化解的准确性,且算法的生化实验复杂度低,具有良好的实验操作性.DNA computing is an efficient method to solve computational problems, especially for NP complete problems that cannot be efficiently solved using the traditional Turing machine. However, with the development of DNA computation, it presently suffers from several challenging problems such as relatively high error rates, DNA space explosion, etc. How to decrease error rates has become an important issue for DNA computation. To solve the maximum clique problem which is an NP complete problem, with low DNA hybridization error rates, this paper introduces a DNA self- assembly model and presents a novel DNA computing algorithm. This algorithm decreases error rates by decreasing experiment operations. Moreover, the DNA structures of initial molecular, regular molecular and detection molecular are designed, and encoding scheme of DNA molecular is described, too. The proposed algorithm needs （n＋ ｜E｜） types of tiles and （1） times of experiment operations, where n and｜ E｜are the numbers of vertex and edge of a graph respectively. According to the analysis, our algorithm can not only improve the accuracy of the solutions, but also greatly reduce the complexity of the experiment, which leads to easier experiment operability, as compared with the other DNA models including sticker model, insert-delete system, etc.

关 键 词：DNA计算 自组装 并行计算 NP完全问题 最大团问题 

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