计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 309-313.doi: 10.11896/j.issn.1002-137X.2019.01.048
朱维军, 张春艳, 周清雷, 陈永华
ZHU Wei-jun, ZHANG Chun-yan, ZHOU Qing-lei, CHEN Yong-hua
摘要: 在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题。DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术。文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法。首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图。仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间。
中图分类号:
[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. |
|