求解0-1规划问题的DNA计算模型(英文)  

A DNA Computation Model to Solve 0-1 Programming Problem

作　　者：强小利[1] 曾波[1] 王子成[1] 寇铮[2] 

机构地区：[1]华中科技大学控制科学与工程系,武汉430074 [2]中国科学院武汉病毒研究所病毒学国家重点实验室,武汉430071

出　　处：《计算机学报》2008年第12期2155-2159,共5页Chinese Journal of Computers

基　　金：国家自然科学基金(60533010,30670540,60874036,60503002);国家“八六三”高技术研究发展计划项目基金(2006AA01Z104);中国教育部博士点基金(20070001020);中国博士后科学基金(20060400344)资助

摘　　要：DNA计算是以DNA分子作为数据的一种新型计算模式.在DNA计算中首要面对的问题是编码问题.文中提出了一种双编码方法,利用这种编码方法可以使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作.基于该编码方法所建立的DNA计算模型可用于求解0-1规划问题,只需4次PCR反应即可读取问题的可行解.与其他DNA计算模型相比,该模型具有操作简单、易于实现的优点.DNA computing is a novel computation paradigm with DNA molecules as ‘data＇, and encoding is a crucial problem with great difficulties of DNA computing. In this paper, a novel encoding method named double encoding method is proposed, which could make the procedure of solution detection similar to DNA sequencing technology. By using this method a DNA algorithm to solve 0-1 programming problem is proposed and PCR is done only 4 times of to detect the feasible solutions. Compared with other DNA computing algorithms, this method could be easier and faster to read out the solution.

关 键 词：DNA计算 0-1规划问题 编码 

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