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

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

作　　者：聂晓艳[1] 耿俊[2] 汤建钢[1] 

机构地区：[1]伊犁师范学院数学与统计学院,新疆伊宁835000 [2]喀什师范学院数学系,新疆喀什844006

出　　处：《江汉大学学报（自然科学版）》2012年第5期5-8,共4页Journal of Jianghan University：Natural Science Edition

基　　金：国家自然科学基金资助项目(11161050);新疆维吾尔自治区自然科学基金资助项目(2011211A051);伊犁师范学院研究生资助课题(2012YJS011);喀什师范学院青年专项课题(122448)

摘　　要：提出了用粘贴系统求解赋权无向图中固定端点最短路径的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.

关 键 词：DNA计算 粘贴系统 最短路径问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O157.5[自动化与计算机技术—计算机科学与技术]