Abstract
Given an undirected graph with weights on the vertices, the maximum weight clique problem is to find a subset of mutually adjacent vertices, i.e. a clique, which have the largest total weight. We devised a new DNA encoding method to solve the maximum weight clique problem whose basic idea is that each vertex on weighted graph is encoded by two DNA strands of different length and each edge is encoded by one DNA strand with a length of 20. The longer DNA strand corresponding to vertexv i consists of three parts and its center part is with a length of w i ; the shorter DNA strand is the reverse complementation of the longer one’s center part. We also gave the correspond- ing molecule algorithm and its biological implementation. The proposed DNA computing method can be expanded to solve other NP-hard problems, and it provides further evidence for the ability of DNA computing to solve numerical optimization problems.
This work was supported by the Science and Technology Development Foundation from Shandong University at Weihai under Grant No.XZ2005005; the National Natural Science Foundation of China under Grant No.60573024; the National Grand Fundamental Research 973 Program of China under Grant No.2005CCA04500.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.M.: Molecular Computation of Solutions to Combinatorial problems. Science 266, 1021–1024 (1994)
Lipton, R.J.: DNA solution of Hard Computational Problems. Science 268, 542–545 (1995)
Ouyang, Q., Kaplan, P.D., Liu, S., et al.: DNA Solution of the Maximal Clique Problem. Science 278, 446–449 (1997)
Head, T., Rozenberg, G., Bladergroen, R.S., et al.: Computing with DNA by Operating on Plasmids. Biosystems 57, 87–93 (2000)
Sakamoto, K., Gouzu, H., Komiya, K., et al.: Molecular Computation by DNA Hairpin Formation. Science 288, 1223–1226 (2000)
Narayanan, A., Zorbalas, S., et al.: DNA Algorithms for Computing Shortest Paths. In: Proceedings of the Genetic Programming, pp. 718–723. Morgan Kaufmann, San Francisco (1998)
Shin, S.Y., Zhang, B.T., Jun, S.S., et al.: Solving Traveling Salesman Problems Using Molecular Programming. In: Proceedings of the Congress on Evolutionary Computation, pp. 994–1000. IEEE Press, Los Alamitos (1999)
Yamamura, M., Hiroto, Y., Matoba, T.: Solutions of Shortest Path Problems by Concentration Control. In: Jonoska, N., Seeman, N.C. (eds.) DNA 2001. LNCS, vol. 2340, pp. 231–240. Springer, Heidelberg (2002)
Lee, J.Y., Shin, S.Y., Park, T.H., et al.: Solving Traveling Salesman Problems with DNA Molecules Encoding Numerical Values. BioSystems 78, 39–47 (2004)
Yin, Z.: DNA Computing in Graph and Combination Optimization, pp. 57–72. Science Press (2004) (in Chinese)
Ma, R., Zhang, Q., Gao, L., Xu, J.: Using DNA to Solve the Maximum Weight Clique of Graphs. ACTA Electronica Sinica 32, 13–16 (2004)
Xu, J., Wang, S., Pan, Q., Paun, G., Rozenberg, G., Salomaa, A.: write: DNA Computing: New Computing Paradigms, vol. 1, pp. 3–54. Tsinghua University publishing company (2004) (in Chinese)
Liu, W., Wang, S., Xu, J.: Research on the Encoding Method of DNA Computing. Computer Engineering and Applications 27, 118–121 (2003)
Han, A., Yang, Z., et al.: Complexity Analysis for HEWN Algorithm. Journal of Software 13, 2337–2342 (2002) (in Chinese)
Han, A.: Complexity Research for B Algorithm. In: Proceedings of the Tenth Joint Internation-al Computer Conference, pp. 188–192. International Academic Publishers (2004)
Wang, L., Lin, Y., Li, Z.: DNA Computation for a Category of Special Integer Planning Problem. Computer Research and Development 42, 1431–1437 (2005) (in Chinese)
Chen, Z., Li, X., Wang, L., et al.: A Surface-Based DNA Algorithm for the Perfect Matching Problem. Computer Research and Development 42, 1241–1246 (2005) (in Chinese)
Lancia, G.: Integer Programming Models for Computional Biology Problems. Journal of Computer Science and Technology 19, 60–77 (2004)
Ibrahim, Z., Tsuboi, Y., Muhammad, M.S., et al.: DNA Implementation of k-shortest Paths Computation. In: IEEE Congress on Evolutionary Computation. IEEE CEC 2005 Proceedings, vol. 1, pp. 707–713 (2005)
Liu, Q., Wang, L., Frutos, A.G., et al.: DNA Computing on Surfaces. Nature 403, 175–179 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Han, A., Zhu, D. (2006). A New DNA-Based Approach to Solve the Maximum Weight Clique Problem. In: Huang, DS., Li, K., Irwin, G.W. (eds) Computational Intelligence and Bioinformatics. ICIC 2006. Lecture Notes in Computer Science(), vol 4115. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11816102_35
Download citation
DOI: https://doi.org/10.1007/11816102_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37277-6
Online ISBN: 978-3-540-37282-0
eBook Packages: Computer ScienceComputer Science (R0)