Experimental Implementation of Direct-Proportional Length-Based DNA Computing for Numerical Optimization of the Shortest Path Problem
Zuwairie Ibrahim, Yusei Tsuboi, Osamu Ono and Marzuki Khalid
DNA computing has emerged as an interdisciplinary field that draws together chemistry, molecular biology, computer science, engineering, and mathematics. From DNA computing point of view, it has been proven that it is possible to solve weighted graph problems such as Traveling Salesman Problem (TSP) and the shortest path problem by exploiting some characteristics of DNA. Those characteristics are length, concentration, and melting temperature of DNA. In this paper, we present an alternative length-based DNA computing approach whereby the cost of each path is encoded by the length of the oligonucleotides in a proportional way. The advantage is such that, after an initial pool generation and amplification, polyacrylamide gel electrophoresis (PAGE) can be performed to separate the respective DNA duplex according to their length which directly decodes the results. For an efficient initial pool generation, parallel overlap assembly (POA) is employed. After amplification is done by polymerase chain reaction (PCR), the result of the computation is visualized by PAGE. The experimental results show the effectiveness of the proposed direct-proportional length-based computation and prove that the shortest path problem has been successfully solved on a DNA computer.