DNA Computing Adopting DNA Coding Method for Hamiltonian Path Problem

摘要

DNA computing is a new paradigm to perform calculation using genetic engineering technology, and has used to solve NP-complete problems. However, when current DNA computing is applied to NP-complete problems, some problems are raised. In this paper we proposed an algorithm called ACO (Algorithm for Code Optimization) that can efficiently express DNA sequence and create good codes through composition and separation processes as many as the numbers of reaction by DNA coding method. Also, we applied ACO to Hamiltonian path problem of NP-complete problems. As a result, ACO could express DNA codes of variable lengths more efficiently than Adleman's DNA computing algorithm could. In addition, compared to Adleman's DNA computing algorithm, ACO could reduce search time and biological error rate by 50% and could search for accurate paths in a short time.