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

doi:10.3969/j.issn.1001-2400.2013.05.028

J4 ›› 2013, Vol. 40 ›› Issue (5): 175-180.doi: 10.3969/j.issn.1001-2400.2013.05.028

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

朱维军^1,2,3;徐朝辉²;张海宾³;杨卫东²

(1. 郑州大学信息工程学院，河南郑州 450001；
2. 河南工业大学粮食信息处理与控制教育部重点实验室，河南郑州 450001;
3. 西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2012-12-05 出版日期:2013-10-20 发布日期:2013-11-27
通讯作者: 朱维军
作者简介:朱维军(1976-)，男，副教授，博士，E-mail: zhuweijun@zzu.edu.cn．
基金资助:
国家自然科学基金青年基金资助项目(61003079, 61202099)；国家自然科学基金委员会-河南省人民政府人才培养联合基金资助项目(U1204608)；国家自然科学基金主任基金资助项目(61250007)；中国博士后科学基金资助项目(2012M511588)；教育部博士点基金资助项目(20100203120012)；中央高校基本科研业务费资助项目(K5051203019)

DNA algorithm for k-edge induced sub-graphs of directed graphs

ZHU Weijun^1,2,3;XU Zhaohui²;ZHANG Haibin³;YANG Weidong²

(1. School of Information Engineering, Zhengzhou Univ., Zhengzhou 450001， China;
2. MOE Key Lab. of Grain Information Technology ＆ Control, Zhengzhou 450001， China;
3. School of Computer Science and Technology, Xidian Univ., Xi'an 710071， China)

Received:2012-12-05 Online:2013-10-20 Published:2013-11-27
Contact: ZHU Weijun

摘要/Abstract

摘要：

针对经典计算的有向图k边导出子图生成算法时间复杂度较高问题，提出了一种在脱氧核糖核酸粘贴机上运行的子图生成算法．首先，以粘贴系统提供的标准生化元操作为算法使用的基本元算子，并使用元操作所产生的生化结果的图论解释作为元算子的最小语义单元; 其次，使用包括顺序、循环等在内的程序控制结构，设计一定的逻辑方式把元算子组织起来，以计算有向图导出子图．复杂度分析表明，新算法可在线性时间生成所有子图．仿真实验结果表明，与经典算法相比，新算法在理想条件下大幅降低了子图生成时间．

关键词: 有向图, 脱氧核糖核酸, 时间复杂度, 粘贴系统

Abstract:

The classical algorithms for k-edge induced sub-graphs of the directed graph are very inefficient due to their high complexity. To solve this problem, a DNA sticker algorithm for constructing sub-graphs is put forward in this paper. First, the basic constructs in the algorithm consist of some pre-defined sticker operations. And then, the algorithm is organized in some logical orders of basic constructs. The complexity analysis indicates that the new algorithm can construct the sub-graphs in the linear time. As shown in the simulation results with MATLAB, compared with the classical algorithms, the new algorithm reduces significantly the time for constructing sub-graphs under ideal conditions.

Key words: directed graphs, DNA, time complexity, sticker systems

中图分类号:

TP301

朱维军;徐朝辉;张海宾;杨卫东. 有向图k边导出子图的DNA粘贴算法[J]. J4, 2013, 40(5): 175-180.

ZHU Weijun;XU Zhaohui;ZHANG Haibin;YANG Weidong. DNA algorithm for k-edge induced sub-graphs of directed graphs[J]. J4, 2013, 40(5): 175-180.

参考文献

［1］ Adleman L. Molecular Computation of Solutions to Combinatorial Problem ［J］. Science, 1994, 266: 1021-1024.
［2］ Lipton R J. DNA Solution of Hard Computational Problems ［J］. Science, 1995, 268: 542-545.
［3］ Liu Qinghua, Wang Liman, Frutos A G, et al. DNA Computing on Surface ［J］. Nature, 2000, 403(13):175-179.
［4］ Junid S A M A, Tahir N M, Majid Z A, et al. Potential of Graph Theory Algorithm Approach for DNA Sequence Alignment and Comparison［C］//Proceedings of 2012 3rd International Conference Intelligent Systems, Modelling and Simulation. Los Alamitos: IEEE, 2012: 187-190.
［5］ Brijder R, Gillis J J M, Van den Bussche J. A Comparison of Graph-theoretic DNA Hybridization Models ［J］. Theoretical Computer Science, 2012, 429: 46-53.
［6］ Eghdami H, Darehmiraki M. Application of DNA Computing in Graph Theory［J］. Artificial Intelligence Review, 2012, 38(3): 223-235.
［7］ Fouilhoux P, Mahjoub A. Solving VLSI Design and DNA Sequencing Problems Using Bipartization of Graphs ［J］. Computational Optimization and Applications, 2012, 51(2): 749-781.
［8］ Ellis-Monaghan J, Pangborn G. Using DNA Self-assembly Design Strategies to Motivate Graph Theory Concepts ［J］. Mathematical Modelling of Natural Phenomena, 2011, 6(6): 96-107.
［9］ Xue Jie, Liu Xiyu. Applying DNA Computation to Clustering in Graph［C］//Proceedings of 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce. Zhengzhou: IEEE, 2011: 986-989.
［10］ Brijder R, Gillis J J M, Van den Bussche J. Graph-theoretic Formalization of Hybridization in DNA Sticker Complexes［C］//Proceedings of 17th International Conference on DNA Computing and Molecular Programming. Pasadena: Springer Verlag, 2011: 49-63.
［11］ Zhang Xuncai, Lin Minqi, Niu Ying. Application of 3D DNA Self-assembly for Graph Coloring Problem［J］. Journal of Computational and Theoretical Nanoscience, 2011, 8(10): 2042-2049.
［12］卢明欣, 傅晓彤, 秦磊, 等. DNA信息隐藏方法的安全性分析和保密增强方法［J］. 西安电子科技大学学报, 2006, 33(3): 448-452.
Lu Mingxin, Fu Xiaotong, Qin Lei, et al. A Study of the Security of a Steganography Method and Security Enhancement Methods ［J］. Journal of Xidian University, 2006, 33(3): 448-452.
［13］ Adleman L. On Constructing a Molecular Computer in DNA Based Computers［M］. Washington: American Mathematical Society, 1996: 1-22.
［14］ Zimmermann K H. On Applying Molecular Computation to Binary Linear Codes ［J］. IEEE Transactions on Information Theory, 2002, 48(2): 505-510.
［15］ Zimmermann K H. Efficient DNA Sticker Algorithms for NP-complete Graph Problems ［J］. Computer Physics Communications, 2002, 144(3):297-309.
［16］ Martinez-Perez I. Biomolecular Computing Models for Graph Problems and Finite State Automata ［D］. Hamburg: Hamburg University of Technology, 2007.
［17］ Xu Jin, Li Sanping, Dong Yafei, et al. Sticker DNA Computer Model—Part II: Application ［J］. Chinese Science Bulletin, 2004, 49(9): 863-871.
［18］ Jiang Xingpeng, Li Yin, Meng Ya, et al. New DNA Alogorithm to Solve Graph Coloring Problem ［J］. Progress in Natural Science, 2007, 17(6): 733-738.
［19］ Liu Wenbin, Zhang Fengyue, Xu Jin. A DNA Algorithm for the Graph Coloring Problem ［J］. Journal of Chemical Information and Computer Sciences, 2002, 42(5): 1176-1178.
［20］ Wang Shiying. DNA Computing of Bipartite Graphs for Maximum Matching ［J］. Journal of mathematical chemistry, 2002, 31(3): 271-279.
［21］ Manrique D, Rodriguez-Paton A, Sosik P. On the Scalability of Biocomputing Algorithms: the Case of the Maximum Clique Problem ［J］. Theoretical Computer Science, 2011, 412(51): 7075-7086.
［22］ Garcia-Arnau M, Manrique D, Rodriguez-Paton A, et al. A P System and a Constructive Membrane-inspired DNA Algorithm for Solving the Maximum Clique Problem ［J］. Biosystems, 2007, 90(3): 687-697.
［23］ Sethuraman G, Kavitha J. Star Colouring Problem: the DNA Solution ［J］. Journal of Algorithms ＆ Computational Technology, 2011, 5(3): 423-436.
［24］ 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-3): 39-47.
［25］ Wang Shiying, Yuan Jun, Lin Shangwei. DNA Labelled Graphs with DNA Computing ［J］. Science in China Series A(Mathematics, Physics, Astronomy), 2008, 51(3): 437-452.
［26］ Ignatova Z, Martinez-Perez I, Zimmermann K H. DNA计算模型［M］. 郗方，王淑栋，强小利, 译. 北京: 清华大学出版社, 2010.
［27］ Martinez-Perez 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.

[1]	暂时无作者信息. 网格计算机上的最小包围框算法[J]. J4, 1996, 23(4): 0-0.
[2]	暂时无作者信息. 网格计算机上的平面凸壳算法[J]. J4, 1996, 23(3): 0-0.

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

DNA algorithm for k-edge induced sub-graphs of directed graphs

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

Metrics

本文评价

推荐阅读 0