Abstract Deoxyribonucleic Acid or DNA-based computing is an emerging field that bridging the gap between chemistry, molecular biology, computer science, and mathematics. This research area is a new paradigm whereby the computation can be done by the use of DNA molecules to encode the computational problem. During the massively parallel computation in a test tube, a series of bio-molecular reactions are employed and the output encoded also by DNA molecules can be printed and read out by electrophoretical fluorescent method. Since DNA computing is very suitable for combinatorial problems, in this paper, an idea on DNA-based computing algorithm for solving unconstraint assignment problem is proposed. The proposed approach basically consists of two phases; encoding phase and computational phase. During the encoding phase, a method to encode the computational problem is carried out by introducing four rules. On the other hand, for the computational phase, it is discovered that the complexity of the unconstraint assignment problem can be reduced to a path problem of a graph, and the possibility to solve the unconstraint assignment problem by DNA computing approach is shown in detail.

References

[1] Adleman L. M., Computing with DNA, Scientific American Journal, vol. 279, no. 2, pp. 54-61, 1998.

[2] Adleman L. M., Molecular Computation of Solutions to Combinatorial Problems, Science Journal , vol. 266, pp. 1021-1024, 1994.

[3] Amos M., DNA Computation, PhD Thesis, The University of Warwick, 1997.

[4] Arora A., Frieze A., and Kaplan H., A New Rounding Procedure for the Assignment Problem Unconstraint Assignment Problem: A Molecular Computing Approach 177 with Application to Dense Graph Arrangement Problem, in Proceedings of the 37th Annual Symposium on Foundation of Computer Science , pp. 21-30, 1996.

[5] Calude C. S. and Paun G., Computing with Cell and Atoms: An Introduction to Quantum, DNA, and Membrane Computing , Taylor and Francis, 2001.

[6] Fitch J. P., An Engineering Introduction to Biotechnology , SPIE-The International Society of Optical Engineering, 2002.

[7] Liu G., and Haralick R. M., Assignment Problem in Edge Detection Performance Evaluation, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , vol. 1, pp. 26-31, 2000.

[8] Moore G. E., Cramming More Components onto Integrated Circuits, Electronics Journal, vol. 38, no. 8, pp. 114-117, 1965.

[9] Paun G., Rozenberg G., and Salomaa A., DNA Computing: New Computing Paradigms , Springer-Verlag, 1998.

[10] Skiena, S. S. and Skiena S., The Algorithm Design Manual , Telos Pr, 1997.

[11] Udo F., Sam S., Wolfgang B., and Hilmar R., DNA Sequence Generator: A Program for the Construction of DNA Sequences, in Proceedings of the 7th International Workshop on DNA Based Computers , pp. 23-32, 2001.

[12] Yamamoto M., Kameda A., Matsuura N., Shiba T., Kawazoe Y., and Ohuchi A., A Separation Method for DNA Computing Based on Concentration Control, New Generation Computing Journal , vol. 20, no. 3, pp. 251-262, 2002.

[13] Zucca M., DNA Based Computational Model, PhD Thesis, Politecnico Di Torino, Italy, 2000. Ibrahim Zuwairie received his BEng in mechatronics and his MEng in image processing from University Teknology Malaysia, Malaysia, in 2000 and 2002, respectively. Since 2002, he has been engaged with the Department of Mechatronics and Robotics, Faculty of Electrical Engineering, University Technology Malaysia as a lecturer. Currently, he is pursuing his PhD at the Institute of Applied DNA Computing, Meiji University, Kanagawa, Japan. He is a student member of Institute of Electrical and Electronics Engineers (IEEE), International Computational Intelligence Society (ICIS), and International Signal Processing Society (ISPC). His research interests include signal and image processing, automated visual inspection, evolutionary, and unconventional computing such as molecular or DNA computing. Tsuboi Yusei received the BEng and Master s degree from Meiji University, Japan, in 2000 and 2002, respectively. Currently, he is pursuing the PhD degree also at Meiji University, Japan. Presently, his research interest includes robotics and DNA computing for artificial intelligence. Ono Osamu received the Bachelor, Master and Doctor Degree in Engineering all from Waseda University, Tokyo, in 1974, 1976, and 1979, respectively. He is a professor at the Department of Electrical and Electronic Engineering, Meiji University, Japan. He is the director of Tokyo Branch of Japan Institute Electrical Engineering and a committee member of Japan Society for Simulation Technology (JSST). His research interest includes large scale industrial process, mechatronics, advanced mobile robotics and image processing. Currently, he is interested in the application of DNA computing in engineering field. Khalid Marzuki is currently a professor in intelligent control and a director at the Centre of Artificial Inteligence and Robotics (CAIRO), University Technology Malaysia, Malaysia. His research interest is in the field of artificial intelligence with applications of control. He has been appointed to the editorial advisory board of the International Journal of Engineering Applications of Artificial Intelligence published by Elsevier Science and an associate editor of the Journal of Systems and Control Engineering published by the Institute of Mechanical Engineers, United Kingdom. Currently, he is the IEEE student activities chair for Region 10 (Asia Pacific) and also the founding member of the Asian Control Professors Association.