| 基于粘贴系统求解无向图最短路径问题的DNA计算模型 |
| |
| 引用本文： | 聂晓艳,耿俊,汤建钢. 基于粘贴系统求解无向图最短路径问题的DNA计算模型[J]. 江汉大学学报(自然科学版), 2012, 40(5): 5-8 |
| |
| 作者姓名： | 聂晓艳 耿俊 汤建钢 |
| |
| 作者单位： | 1. 伊犁师范学院数学与统计学院,新疆伊宁,835000
2. 喀什师范学院数学系,新疆喀什,844006 |
| |
| 基金项目： | 国家自然科学基金资助项目，新疆维吾尔自治区自然科学基金资助项目，伊犁师范学院研究生资助课题，喀什师范学院青年专项课题 |
| |
| 摘 要： | 提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。
|
| 关 键 词： | DNA计算 粘贴系统 最短路径问题 |
DNA Algorithm for Shortest Path Problem of Undirected Graph Based on Sticker Systems |
| |
| NIE Xiao-yan,GENG Jun,TANG Jian-gang. DNA Algorithm for Shortest Path Problem of Undirected Graph Based on Sticker Systems[J]. Journal of Jianghan University(Natural Sciences), 2012, 40(5): 5-8 |
| |
| Authors: | NIE Xiao-yan GENG Jun TANG Jian-gang |
| |
| Affiliation: | 1 (1.School of Mathematics and Statistics,Yili Normal University,Yili 835000,Xinjiang,China; 2.Department of Mathematics,Kashi Normal University,Kashi 844006,Xinjiang,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | DNA computing sticker systems shortest path problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
