Objective To solve the 0-1 knapsack problem,which is a classical NP problem since the chemical re-action networks based on DNA strand displacement can be used as an effective programming language to solve va-rious mathematical problems.Methods The DNA strand displacement reaction network was proposed and Visual DSD was used to design the simulation experiment.Results Three reaction modules,weighting,summation and threshold,were used to solve the problem,and the result was expressed by the output single strand DNA.Due to the error of concentration detection,the results of the operation were expressed by using a single strand DNA with fluorescent molecules.Finally,DSD simulation software was used to obtain the chain displacement response net-work diagram,variable simulation diagram and threshold comparison diagram corresponding to the variable con-version module.The model showed that the algorithm reduced effectively the complexity of 0-1 knapsack prob-lem and had high accuracy and stability.Conclusion The model proposed in this paper is able to enrich DNA computation and broaden the computational width of DNA strand displacement.
DNA strand displacement0-1 knapsack problemNP problemDNA computing
NETL
NSTL
维普
万方数据
