CAJ | 학술논문

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。
제출료용점첩계통구해부권무향도중고정단점최단로경적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.