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

doi:10.3969/j.issn.1001-2400.2013.05.028

Abstract

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

CLC Number:

TP301

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.

References

［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]	ZHONG Ming-fu;HU Yu-pu;CHEN Jie. Square attack on the 14-round block cipher SMS4 [J]. J4, 2008, 35(1): 105-109.
[2]	CHI Xiao-ni;LIU San-yang. A primal-dual infeasible-interior-point algorithm for second-order cone programming [J]. J4, 2007, 34(2): 307-311.
[3]	LU Ming-xin(1;2);CHEN Yuan(1;2);QIN Lei(3);XIAO Guo-zhen(1;2). An encryption scheme based on DNA [J]. J4, 2006, 33(6): 939-942.
[4]	LU Ming-xin(1);FU Xiao-tong(1);QIN Lei(2);XIAO Guozhen(1). A study of the security of a steganography method and security enhancement methods [J]. J4, 2006, 33(3): 448-452.

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

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 0