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

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

一类禁位排列问题的粘贴DNA算法

杨玉星1,栗青生1,马季兰2   

  1. 1.安阳师范学院 计算机与信息工程学院,河南 安阳 455000
    2.太原理工大学 计算机与软件学院,太原 030024
  • 收稿日期:2008-06-19 修回日期:2008-07-04 出版日期:2008-10-21 发布日期:2008-10-21
  • 通讯作者: 杨玉星

DNA algorithm of a kind of forbidden ranking problem based on sticker model

YANG Yu-xing1,LI Qing-sheng1,MA Ji-lan2   

  1. 1.School of Computer and Information Engineering,Anyang Normal University,Anyang,Henan 455000,China
    2.College of Computer and Software,Taiyuan University of Technology,Taiyuan 030024,China
  • Received:2008-06-19 Revised:2008-07-04 Online:2008-10-21 Published:2008-10-21
  • Contact: YANG Yu-xing

摘要: 提出了广义的分离操作和广义的多级分离操作的概念,简要说明了二者的区别,并给出了其实现方法。基于粘贴模型的巨大并行性,给出了一类禁位排列问题的粘贴DNA算法,分别使用扩展的分离操作和扩展的多级分离操作实现了该算法。通过一个实例说明了给出的实验操作步骤,并对生化实验进行了模拟,得出了模拟结果,从而证明了该算法的可行性。最后,对算法的操作复杂度进行了分析。

关键词: 禁位排列, DNA计算, 粘贴模型, 分离

Abstract: Both extended separate and extended multi-separate are proposed originally.The difference from them is illustrated,and the physical implementing methods are shown.A sticker DNA algorithm is proposed based on the vast parallelism of sticker model,and be carried out it by extended separate and extended multi-separate respectively.The operation steps are given through an instance,and a simulation experiment is carried out to illustrate the biochemical processes.The final result is gotten.Consequently,the feasibility of the algorithm is proved.At last,the complexity is analyzed.

Key words: forbidden ranking, DNA computing, sticker model, separation