最短路问题的闭环DNA算法

Closed circle DNA algorithm of shortest path problem

提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过检测实验输出所有最短路径。得出了算法的复杂性,为说明算法的有效性给出了一个算例。最后讨论了最短路问题闭环DNA算法在变权网络、自由终点或固定中间点的最短路问题中的应用,并给出了相应的解决方法。由此说明该算法具有广泛的适应性。

A concept of closed circle DNA＇s different chain-length is brought forward, which generalizes a model of closed circle DNA computing. For the shortest path problem of fixed jumping-off point and end point, a closed circle DNA algorithm is put forward. In the closed circle DNA algorithm, three groups of DNA encoding for every arcs are encoded. And all paths of fixed jumping-off point and end point are synthesized using purposive ending technology. Then all shortest paths are filtered out using insert experiment and electrophoresis experiment and found using detect experiment. The complexity of the algorithm is educed. And an example is applied to explain the feasibility of the DNA algorithm. Finally it is discussed, which is the application of closed circle DNA algorithm of shortest path problems to variational-weight network, free end point or fixed middle point shortest path problem. And methods solving interrelated problems are put forward, which explains this DNA algorithm has extensive adaptability.