RLM: A New Method of Encoding Weights in DNA Strands

摘要

How to encode weights in DNA computing is an important but challenging problem because many practical applications in the real world involve weights. In order to efficiently encode weights in DNA strands, we firstly proposed two definitions, the order number of weight and the relative length graph. And then, by means of the two definitions, we have devised a new method of encoding weights in DNA strands for a weighted graph G=(V,E,W), referred to relative length method (RLM). The RLM method can directly deal with weights of either real numbers or integers, even very small and very big positive weights, and the solution obtained in the RLM method isn't proportional to the length of DNA strand. The RLM method was applied to solve the traveling salesman problem, and it can be expanded to solve other numerical optimization problems.