基于粘贴系统求解无向图最短路径问题的DNA计算模型

DNA Algorithm for Shortest Path Problem of Undirected Graph Based on Sticker Systems

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。

Proposed a new project of DNA computing model to solve the shortest path prob- lem of fixed start point and end point of undirected graph, In this DNA algorithm,two opposite di- rected edge took place of each side of undirected graph, so changed the undirected graph into di- rected graph, And all paths of fixed start and end point are obtained by taking use of parallelism of sticker systems. Then can take the shortest path by some molecular biology technology, such as probe, eleetrophoresis, and so on. An example is applied to illustrate the feasibility of the DNA algorithm.