计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (25): 40-42.DOI: 10.3778/j.issn.1002-8331.2008.25.012

• 理论研究 • 上一篇    下一篇

粘贴与删除系统求解最短有向路的DNA计算模型

马芳芳1,王淑栋1,李 涵2,薛圣伟1   

  1. 1.山东科技大学 信息科学与工程学院,山东 青岛 266510
    2.山东科技大学 信息系,山东 泰安 271209
  • 收稿日期:2007-12-06 修回日期:2008-02-27 出版日期:2008-09-01 发布日期:2008-09-01
  • 通讯作者: 马芳芳

DNA computing model for shortest directed path problem based on sticker and delete system

MA Fang-fang1,WANG Shu-dong1,LI Han2,XUE Sheng-wei1   

  1. 1.College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266510,China
    2.College of Information,Shandong University of Science and Technology,Taian,Shandong 271209,China
  • Received:2007-12-06 Revised:2008-02-27 Online:2008-09-01 Published:2008-09-01
  • Contact: MA Fang-fang

摘要: 最短有向路问题是在一个有向网络中的两个指定顶点之间找出一条具有最小权的有向路,它在工程实践中具有广泛的应用。粘贴系统与删除系统是DNA计算形式模型中的两种基本模型。论文利用粘贴与删除系统的巨大并行性给出了求解图最短有向路问题的DNA计算模型及其实现算法。

关键词: DNA计算, 粘贴系统, 删除系统, 最短有向路问题

Abstract: Shortest directed path problem is finding a directed path with minimum weight in two pointed vertex of a directed network.It has extensive application in engineering practice.Sticker system and delete system are two kinds of basic models in DNA computing form model.This paper proposes DNA computing model and biochemical procedures of graph shortest directed path problem using high parallelism of sticker system and delete system.

Key words: DNA computing, sticker system, delete system, shortest directed path problem