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

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.

Authors:

• Zuwairie Ibrahim
• Yusei Tsuboi
• Osamu Ono
• Marzuki Khalid

Keywords:

• DNA computing
• operation research
• 1-center problem.

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.