传递闭包问题的DNA计算  

DNA Computing of Transfer Closure Problems

作　　者：刘文君[1] 殷志祥[1] LIU Wen-jun,YIN Zhi-xiang（College of Science,Anhui University of Science and Technology,Huainan 232001,China）

机构地区：[1]安徽理工大学理学院,安徽淮南232001

出　　处：《电脑知识与技术》2012年第10期6771-6772,6794,共3页Computer Knowledge and Technology

基　　金：国家自然科学基金（61170172,60873144,61073102,60973050）资助

摘　　要：DNA计算是计算机科学和分子生物学相互结合,相互渗透而产生的新计算模式,在解决一些复杂的问题上,尤其是NP—完全问题上具有一定的优势,提供了新的解决途径。首先介绍DNA计算的基本原理,其次详细介绍传递闭包问题的DNA算法,对图中顶点用DNA片段进行编码,将这些DNA片段放入溶液中进行生化反应,通过基本的生物操作及生物酶完成解的产生,并最终筛选出传递闭包问题的所有解。最后介绍DNA计算的研究和一些尚待解决的问题。The DNA calculation is a new computing mode,which combine and infiltrate computer science with molecular biol ogy.It has certain advantages in solving complex issues,particularly NP complete problems,which can provide a new solution.In the first place,the paper presents the basic principle of DNA computing.In the second place,the paper introduces the transfer clo sure DNA algorithm in detail.The graph vertices were encoded by DNA fragments.Then,these DNA fragments were put into the solution which can conduct biochemical reaction.The solutions are generated through the basic biological operation and bio logical enzyme.And finally,all transfer closure solutions were selected.Eventually,the paper gives an introduction about the DNA computing research and some problems to be solved in its.

关 键 词：DNA计算 传递闭包 NP完全问题 

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