摘要
提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。
A closed circle DNA computing model and its bio-cbemistry experiments are introduced. The flexibility of a closed circle DNA molecule structure is brought forward, which includes the controllabitity of DNA chains in length and mutual conversion among the DNA molecules. For the 0-1 planning problem of nonnegative integer coefficients, a closed circle DNA algorithm is put forward. In the closed circle DNA algorithm, first the five groups of DNA encoding are encoded according to variable＇s 0 or 1 values, its coefficients and its detecting mark. All possible solutions are synthesized. Then all feasible solutions are filtered out using the insert experiment, electrophoresis experiment and delete experiment. All optimization solutions are filtered out using the same method. Finally all optimization solutions are found using a detect experiment. The correctness of the algorithm is proved, and the complexity of the algorithm is discussed. And the feasibility of the DNA algorithm is explained by an example. The closed circle DNA algorithm is improved so as to solve the 0-1 planning problem of the real coefficient including negative numbers.
出处
《系统工程与电子技术》
EI
CSCD
北大核心
2009年第4期947-951,共5页
Systems Engineering and Electronics
基金
国家自然科学基金(60574041,60403002)
湖北省自然科学基金(2007ABA407)资助课题
关键词
闭环DNA计算模型
0-1规划问题
接入实验
删除实验
closed circle DNA computing model
0-1 planning problem
insert experiment
delete experiment
