计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 309-313.doi: 10.11896/j.issn.1002-137X.2019.01.048

• 交叉与前沿 • 上一篇    下一篇

有向图k顶点导出子图的DNA粘贴算法

朱维军, 张春艳, 周清雷, 陈永华   

  1. (郑州大学信息工程学院 郑州450001)
  • 收稿日期:2017-12-28 出版日期:2019-01-15 发布日期:2019-02-25
  • 作者简介:朱维军(1976-),男,博士,副教授,主要研究方向为DNA计算、形式化方法、信息安全,E-mail:zhuweijun76@163.com;张春艳(1990-),女,硕士生,主要研究方向为DNA计算;周清雷(1962-),男,教授,主要研究方向为信息安全、自动机理论、DNA计算等;陈永华(1962-),男,博士,副教授,主要研究方向为DNA计算,E-mail:ieyhchen@zzu.edu.cn(通信作者)。
  • 基金资助:
    国家自然科学基金项目(U1204608,61572444)资助

DNA Sticker Algorithm for k-vertex Induced Sub-graphs of Directed Graphs

ZHU Wei-jun, ZHANG Chun-yan, ZHOU Qing-lei, CHEN Yong-hua   

  1. (School of Information Engineering,Zhengzhou University,Zhengzhou 450001,China)
  • Received:2017-12-28 Online:2019-01-15 Published:2019-02-25

摘要: 在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题。DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术。文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法。首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图。仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间。

关键词: 顶点导出子图, 脱氧核糖核酸, 有向图, 粘贴机

Abstract: How to obtain all the k-vertex induced sub-graphs in a directed graph is a complex computational problem.The DNA computing is a nonclassical computing technique developed in recent years,which can be employed to solve some complex computational problems via DNAs and their biochemical reactions.Aiming at obtaining all the k-vertex induced sub-graphs in a directed graph using the DNA computing,a DNA sticker algorithm for constructing sub-graphs was proposed.First,the existing sticker system provides the basic operators for the new algorithm.Each of these basic operators has its basic computational function,and each of these basic operators can be implemented by a specific stan-dard biochemical reaction.Second,these basic operations can be organized in a certain logical way.As a result,some program structures,such as sequence and loop,are formed.At last,all the k-vertex induced sub-graphs can be obtained for a given directed graph,by reading the results of the biochemical reactions.These simulated results demonstrate that the new algorithm significantly reduces the time which is required by generating sub-graphs under ideal conditions,compared with the classical algorithms.

Key words: Directed graph, DNA, Sticker system, Vertex induced sub-graph

中图分类号: 

  • TP384
[1]XU J.The age of the biological computer is coming [J].Bulletin of Chinese Academy of Sciences,2014,29(1):42-54.(in Chinese)<br /> 许进.生物计算机时代即将来临[J].中国科学院院刊,2014,29(1):42-54.<br /> [2]ADLEMAN L M.Molecular computation of solutions to combinatorial problems[J].Nature,1994,369:40.<br /> [3]LIU W,ZHANG F,XU J.A DNA algorithm for the graph coloring problem[J].Journal of Chemical Information and Computer Sciences,2002,42(5):1176-1178.<br /> [4]WANG S D,LIU W B,XU J.DNA sticker algorithm for vertex-coloring problems of graph [J].Journal of Systems Engineering and Electronics,2005,27(3):568-572.(in Chinese)<br /> 王淑栋,刘文斌,许进.图顶点着色问题的 DNA 粘贴算法[J].系统工程与电子技术,2005,27(3):568-572.<br /> [5]BACH E,GLASER E,CONDON A,et al.DNA models and algorithms for NP-complete problems[C]//Proceedings ofEle-venth Annual IEEE Conference on Computational Complexity.IEEE,1996:290-300.<br /> [6]XU J,LI S P,DONG F Y,et al.The Sticker models of DNA computer(II):Application[J].Chinese Science Bulletin,2004,49(4):299-307.(in Chinese)<br /> 许进,李三平,董亚非,等.粘贴 DNA 计算机模型(II):应用[J].科学通报,2004,49(4):299-307.<br /> [7]CHANG W L,GUO M.Solving the clique problem and the vertex cover problem in Adleman-Lipton’s model[C]//IASTED International Conference on Networks,Parallel and Distributed Processing,and Applications.Japan,2002:431-436.<br /> [8]PAN L Q,XU J,LIU Y C.A surface-based DNA algorithm for the minimal vertex cover problem[J].Progress in NaturalScien-ce:Materials International,2003,13(1):78-80.<br /> [9]ZHOU K,XU J.Closed Circle DNA Algorithm of the Minimal Covering Problem[J].Computer Engineering and Applications,2006,42(20):7-9.(in Chinese)<br /> 周康,许进.最小顶点覆盖问题的闭环DNA算法[J].计算机工程与应用,2006,42(20):7-9.<br /> [10]OUALI M E,FOHLIN H,SRIVASTAV A.An approximation algorithm for the partial vertex cover problem in hypergraphs[J].Journal of Combinatorial Optimization,2012,7659(2):1-19.<br /> [11]NING J,LI Y,YU W.Molecular Sticker Model Stimulation on Silicon for a Maximum Clique Problem[J].International Journal of Molecular Sciences,2015,16(6):13474-13489.<br /> [12]Al JUNID S A M,TAHIR N M,MAJID Z A,et al.Potential of graph theory algorithm approach for DNA sequence alignment and comparison[C]//2012 Third International Conference on Intelligent Systems,Modelling and Simulation (ISMS).IEEE,2012:187-190.<br /> [13]WANG Z,TAN J,ZHU L,et al.A Biological Algorithm to Solve the Maximum Complete Subgraph Problem Based on Adleman-Lipton Model[J].Journal of Computational & Theoretical Nanoscience,2014,11(11):2310-2312.<br /> [14]XU J,TAN G J,FAN Y K,et al.DNA Computer Principle,Advances and Difficulties(IV):On the Models of DNA Computer[J].Chinese Journal of Computers,2007,30(6):881-893.(in Chinese)<br /> 许进,谭钢军,范月科,等.DNA计算机原理、进展及难点(IV):论DNA计算机模型[J].计算机学报,2007,30(6):881-893.<br /> [15]SHEN L J,SONG Z C,WU L Q,et al.A Molecular Computing Model for Maximum Clique Problem Based on DNA Nanoparticles[J].Journal of Computational & Theoretical Nanoscience,2014,11(10):2120-2124(5).<br /> [16]WU X,SONG C Y,ZHANG N,et al.DNA Algorithm for Maximum Matching Problem Based on Sticker Computation Model[J].Computer Science,2013,40(12):127-132.(in Chinese)<br /> 吴雪,宋晨阳,张楠,等.最大匹配问题的粘贴DNA算法[J].计算机科学,2013,40(12):127-132.<br /> [17]ZHOU X,LI K L,YUE G X,et al.A Volume Molecular Solution for the Maximum Matching Problem on DNA-Based Computing[J].Journal of Computer Research and Development,2011,48(11):2147-2154.(in Chinese)<br /> 周旭,李肯立,乐光学,等.一种最大匹配问题DNA计算算法[J].计算机研究与发展,2011,48(11):2147-2154.<br /> [18]HAN A,ZHU D.A new DNA encoding method for traveling salesman problem [C]//International Conference on Intelligent Computing.Springer,Berlin,Heidelberg,2006:328-335.<br /> [19]LEE J Y,SHIN S Y,PARK T H,et al.Solving traveling salesman problems with DNA molecules encoding numerical values[J].BioSystems,2004,78(1):39-47.<br /> [20]XU J.Probe machine [J].IEEE Transactions on Neural Net-works and Learning Systems,2016,27(7):1405-1416. <br /> [21]ROWEIS S,WINFREE E,BURGOYNE R,et al.A sticker-based model for DNA computation[J].Journal of Computational Biology,1998,5(4):615-629.<br /> [22]MARTÍNEZ-PÉREZ I M,ZIMMERMANN K H.Parallel bioinspired algorithms for NP complete graph problems[J].Journal of Parallel and Distributed Computing,2009,69(3):221-229.<br /> [23]ZHU W J,XU Z H,ZHANG H B,et al.DNA algorithm for k-edge induces sub-graphs of directed graphs[J].Journal of Xi-dian University,2013,40(5):175-180.(in Chinese)<br /> 朱维军,徐朝辉,张海宾,等.有向图k边导出子图的 DNA 粘贴算法[J].西安电子科技大学学报,2013,40(5):175-180.<br /> [24]IGNATOVA Z,MARTÍNEZ-PÉREZ I,ZIMMERMANN K H.DNA computing models [M].Berlin:Springer Science & Business Media,2008.<br /> [25]KARI L,PAUN G,ROZENBERG G,et al.DNA computing,sticker systems and universality [J].Acta Informatica,1998,35:401-420.<br /> [26]GEORGIADIS L,ITALIANO G F,PAROTSIDIS N.Strong connectivity in directed graphs under failures,with applications [C]//Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.2017:1880-1899.<br /> [27]KHULLER S,SAHA B.On finding dense subgraphs [C]//Lecture Notes in Computer Science:36th International Colloquium on Automata,Languages and Programming.Berlin:Springer-Verlag,2009:597-608.<br /> [28]ALHAZOV A,CAVALIERE M.Computing by observing bio-systems:The case of sticker systems[C]//International Workshop on DNA-Based Computers.Springer,Berlin,Heidelberg,2004:1-13.<br /> [29]SAKAKIBARA Y,KOBAYASHI S.Sticker systems with complex structures[J].Soft Computing,2001,5(2):114-120.<br /> [30]SELVARAJOO M,HENG F W,SARMIN N H,et al.Probabilistic sticker systems[J].Malaysian Journal of Fundamental and Applied Sciences,2013,9(3):402-420.<br /> [31]GAN Y S,FONG W H,SARMIN N H,et al.Some Properties and Variants of Weighted Sticker Systems[J].International Journal of Applied Mathematics and Statistics<sup>TM</sup>,2013,45(15):367-375.<br /> [32]SIANG G Y,HENG F W,SARMIN N H,et al.The generative power of weighted one-sided and regular sticker systems[C]//AIP Conference Proceedings.AIP,2014,1602:855-862.<br /> [33]KUSKE D,WEIGEL P.The role of the complementarity relation in Watson-Crick automata and sticker systems[C]//Deve-lopments in Language Theory.Springer,Berlin,Heidelberg,2004:272-283.
[1] 陶礼靖, 邱菡, 朱俊虎, 李航天.
面向网络安全训练评估的受训者行为描述模型
Model for the Description of Trainee Behavior for Cyber Security Exercises Assessment
计算机科学, 2022, 49(6A): 480-484. https://doi.org/10.11896/jsjkx.210800048
[2] 黄鑫权, 刘爱军, 梁小虎, 王桁.
基于矩阵论的一致性控制算法收敛速度分析
Matrix Theory Aided Convergence Analysis of Consensus Behavior in FANET with Beacon Loss
计算机科学, 2021, 48(6): 288-295. https://doi.org/10.11896/jsjkx.201000137
[3] 陈冰川,陈蔼祥,吴向军,李磊.
基于数据源向图的数据库设计中数据关系的表示工具
Representation Tool of Data Relations in Database Design Based on Data Source-target Digraph
计算机科学, 2017, 44(Z6): 470-474. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.105
[4] 徐喜荣,黄亚真,张思佳,董学智.
广义Kautz有向图GK(3,n)的反馈数的界
Feedback Numbers of Generalized Kautz Digraphs GK(3,n)
计算机科学, 2016, 43(5): 13-21. https://doi.org/10.11896/j.issn.1002-137X.2016.05.003
[5] 陈秋茹,文中华,袁润,戴良伟.
利用有向环的性质求解可达关系
Solving Reachability Relationship by Property of Directed Cycle
计算机科学, 2016, 43(4): 202-205. https://doi.org/10.11896/j.issn.1002-137X.2016.04.041
[6] 李健利,王艺谋,谢悦,丁洪骞.
一种基于多样化历史信息的自动信任协商策略
Automated Trust Negotiation Based on Diverse History Information
计算机科学, 2016, 43(3): 122-126. https://doi.org/10.11896/j.issn.1002-137X.2016.03.025
[7] 栗青生,张 莉,刘 泉,熊 晶,杨新新.
一种基于云端信息保护的汉字计算模型
Chinese Character Computing Model Based on Cloud Information Protection
计算机科学, 2015, 42(11): 73-79. https://doi.org/10.11896/j.issn.1002-137X.2015.11.015
[8] 师海忠,师越.
(V,R)-语言
(V,R)-Languages
计算机科学, 2014, 41(Z6): 33-36.
[9] 师越,师海忠.
自然语言是正则语言
Natural Languages Are Regular Languages
计算机科学, 2014, 41(Z11): 51-54.
[10] 崔宾阁,孟翱翔.
基于最近邻有向图的遥感图像快速分割算法
Fast Remote Sensing Image Segmentation Algorithm Based on Nearest Neighbor Direct Graph
计算机科学, 2013, 40(10): 274-278.
[11] 陈科,谢明霞,成毅.
空间信息服务链模型的有向图表示及其验证
Geo-serviceChain Model Expression by Directed Graph and Verification
计算机科学, 2012, 39(10): 240-244.
[12] 廖巍,吴晓平,严承华,钟志农.
一种新的道路网络连续查询处理方法
Novel Method for Continuous Queries Processing in Road Networks
计算机科学, 2009, 36(9): 151-153.
[13] 夏阳 陆余良.
计算机主机及网络脆弱性量化评估研究

计算机科学, 2007, 34(10): 74-79.
[14] 陈慧 熊光泽 刘璟.
组播分组数据源鉴别综述

计算机科学, 2004, 31(5): 27-30.
[15] 李燕 王秀峰.
DNA分子计算模型

计算机科学, 2003, 30(8): 21-23.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!