DNA Computing for an Absolute 1-Center Problem: An Evolutionary Approach

Authors: Zuwairie Ibrahim, Yusei Tsuboi, Osamu Ono, Marzuki Khalid

Abstract:

Deoxyribonucleic Acid or DNA computing has emerged as an interdisciplinary field that draws together chemistry, molecular biology, computer science and mathematics. Thus, in this paper, the possibility of DNA-based computing to solve an absolute 1-center problem by molecular manipulations is presented. This is truly the first attempt to solve such a problem by DNA-based computing approach. Since, part of the procedures involve with shortest path computation, research works on DNA computing for shortest path Traveling Salesman Problem, in short, TSP are reviewed. These approaches are studied and only the appropriate one is adapted in designing the computation procedures. This DNA-based computation is designed in such a way that every path is encoded by oligonucleotides and the path-s length is directly proportional to the length of oligonucleotides. Using these properties, gel electrophoresis is performed in order to separate the respective DNA molecules according to their length. One expectation arise from this paper is that it is possible to verify the instance absolute 1-center problem using DNA computing by laboratory experiments.

Keywords: DNA computing, operation research, 1-center problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084866

References:

[1] G. E. Moore, "Cramming more components onto integrated circuits," Electronics, vol. 38, no. 8, 1965.
[2] L. Adleman, "Molecular computation of solutions to combinatorial problems," Science, vol. 266, 1994, pp. 1021-1024.
[3] S. Guha, A. Meyerson, and K. Munagala, "Hierarchical placement and network design problems," Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000.
[4] B. Li, M. Golin, G. Italiano, X. Deng, and K. Sohraby, "On the optimal placement of web proxies in the internet," Proceedings of 18th Annual Joint Conference of the IEEE Computer and Communications Societies, 1999, pp. 1282-1290.
[5] M. Andrews and L. Zhang, "The access network design problem," Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998.
[6] S. Guha, S. Meyerson, and K. Munagala, "Improve combinatorial algorithm for single sink edge installation problems," Technical Report STAN-CS-TN00-96: Stanford University, 2000.
[7] S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, "On the placement of internet instrumentations," Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies, 2000, pp. 26-30.
[8] E. S. Correa, M. T. A. Steiner, A. A. Freitas, and C. Carnieri, "A genetic algorithm for the p-medium problem," Proceedings of Genetic and Evolutionary Computation Conference, 2001, pp. 1268-1275.
[9] K. Jain, M. Mahdian, and A. Saberi, "A new greedy approach for facility location problems," Proceedings of 3rd ACM Symposium on Theory of Computing, 2002, pp. 731-740.
[10] O. Ouyang, P. D. Kaplan, L. Shumao, and A. Libchaber, "DNA solution of the maximal clique problem," Science, vol. 278, 1997, pp. 446-449.
[11] R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, and L. Adleman, "Solution of a 20-variable 3-SAT problem on a DNA computer," Science, vol. 296, 2002, pp. 499-502.
[12] L. M. Adleman, P. W. Rothemund, S. Rowies, and E. Winfree, "On applying molecular computation to the data encryption standard," Journal of Computational Biology, vol. 6, no. 1, 1999, pp. 53-63.
[13] T. Gonzalez, "Clustering to minimize the maximum inercluster distance," Theoretical Computer Science, vol. 38, 1985, pp. 293-306.
[14] J. Mihelic and B. Robic, "Approximation algorithms for k-center problem: an experimental evaluation," Proceedings of Operations Research, 2002.
[15] M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, New York: Wiley, 1995.
[16] A. Narayanan and S. Zorbalas, "DNA algorithms for computing shortest paths," Proceedings of Genetic Programming, 1998, pp. 718-723.
[17] M. Yamamoto, A. Kameda, N. Matsuura, T. Shiba, Y. Kawazoe, and A. Ohochi, "Local search by concentration-controlled DNA computing," International Journal of Computational Intelligence and Applications, vol. 2, no. 4, 2002, pp. 447-455.
[18] J. Y. Lee, S. Y. Shin, S. J. Augh, T. H. Park, and B. T. Zhang, "Temperature gradient-based DNA computing for graph problems with weighted edges," Lecture Notes in Computer Science, vol. 2568, 2003, pp. 73-84.
[19] J. Cheriyan and R. Ravi, Lecture Notes on Approximation Algorithms for Network Problems, Canada: University of Waterloo, 1998.
[20] E. A. Cabral, Lecture Notes on Distribution Managament (MGTSC 461), Canada: University of Alberta, 2000.
[21] L. M. Adleman, "Computing with DNA," Scientific American, 1998, pp. 34-41.
[22] J. P. Fitch, An Engineering Introduction to Biotechnology, Washington: SPIE, 2002.
[23] M. Zucca, DNA Based Computational Models, PhD Thesis, Politecnico Di Torino, Italy, 2000.
[24] C. S. Calude and G. Paun, Computing with Cells and Atoms: An Introduction to Quantum, DNA, and Membrane Computing, New York: Taylor & Francis Inc, 2001.
[25] G. Paun, G. Rozenberg, and A. Salomaa, DNA Computing: New Computing Paradigms, Heidelberg: Springer-Verlag, 1998.
[26] M. Amos, DNA Computation, PhD Thesis, The University of Warwick, UK, 1997.
[27] M. Yamamoto, A. Kameda, N. Matsuura, T. Shiba, Y. Kawazoe, and A. Ohochi, "A separation method for DNA computing based on concentration control," New Generation Computing, vol. 20, no. 3, 2002, pp. 251-262.