Unconstraint Assignment Problem: A Molecular Computing Approach

Ibrahim Zuwairie^1&2, Tsuboi Yusei², Ono Osamu², and Khalid Marzuki³

¹Department of Mechatronics and Robotics, University Technology Malaysia, Malaysia

²Institute of Applied DNA Computing, Meiji University, Japan

³Center for Artificial Intelligence and Robotics (CAIRO), University Technology of Malaysia, Malaysia 

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. 

Keywords: DNA computing, assignment problem, optimization.