Computer Science ›› 2019, Vol. 46 ›› Issue (1): 309-313.doi: 10.11896/j.issn.1002-137X.2019.01.048

• Interdiscipline & Frontier • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] SUN Fu-quan, LIANG Ying. Identification of 6mA Sites in Rice Genome Based on XGBoost Algorithm [J]. Computer Science, 2022, 49(6A): 309-313.
[2] CHEN Wei, LI Hang, LI Wei-hua. Ensemble Learning Method for Nucleosome Localization Prediction [J]. Computer Science, 2022, 49(2): 285-291.
[3] WU Li-bo, HUANG Yu-fang. Logical Reasoning Based on DNA Strand Displacement [J]. Computer Science, 2022, 49(1): 259-263.
[4] HUANG Xin-quan, LIU Ai-jun, LIANG Xiao-hu, WANG Heng. Matrix Theory Aided Convergence Analysis of Consensus Behavior in FANET with Beacon Loss [J]. Computer Science, 2021, 48(6): 288-295.
[5] DU Liu-yun, ZHENG Zhi-jie, ZHENG Hua-xian. Visualization of DNA Sequences of Two Kinds of Bacteria Under Firmicutes [J]. Computer Science, 2020, 47(11A): 192-195.
[6] ZHANG Shu-fang, PENG Kang, SONG Xiang-ming, ZHANG Zi-yu, WANG Han-jie. Research Progress on DNA Data Storage Technology [J]. Computer Science, 2019, 46(6): 21-28.
[7] HAN Ying-jie, ZHOU Qing-lei, ZHU Wei-jun. Survey on DNA-computing Based Methods of Computation Tree Logic Model Checking [J]. Computer Science, 2019, 46(11): 25-31.
[8] CHEN Bing-chuan, CHEN Ai-xiang, WU Xiang-jun and LI Lei. Representation Tool of Data Relations in Database Design Based on Data Source-target Digraph [J]. Computer Science, 2017, 44(Z6): 470-474.
[9] ZUO Xiu-feng and SHEN Wan-jie. Improved Algorithm about Muti-shortest Path Problem Based on Floyd Algorithm [J]. Computer Science, 2017, 44(5): 232-234.
[10] Buhalqam AWDUN and LI Guo-dong. Study on DNA Encoding & Sine Chaos-based Meteorological Image Encryption Technology [J]. Computer Science, 2016, 43(Z11): 403-406.
[11] CHEN Qiu-ru, WEN Zhong-hua, YUAN Run and DAI Liang-wei. Solving Reachability Relationship by Property of Directed Cycle [J]. Computer Science, 2016, 43(4): 202-205.
[12] LI Jian-li, WANG Yi-mou, XIE Yue and DING Hong-qian. Automated Trust Negotiation Based on Diverse History Information [J]. Computer Science, 2016, 43(3): 122-126.
[13] KOU Guang-jie,MA Yun-yan,YUE Jun and ZOU Hai-lin. Survey of Bio-inspired Natural Computing [J]. Computer Science, 2014, 41(Z6): 37-41.
[14] SHI Hai-zhong and SHI Yue. (V,R)-Languages [J]. Computer Science, 2014, 41(Z6): 33-36.
[15] WU Xue,SONG Chen-yang,ZHANG Nan,ZHU Yu and CHEN Zhi-hua. DNA Algorithm for Maximum Matching Problem Based on Sticker Computation Model [J]. Computer Science, 2013, 40(12): 127-132.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!