Feynman first proposed DNA-based computation in 1961, but his idea was not implemented by experiment for a few decades. By properly manipulating DNA strands as the input instance of the Hamiltonian path problem, Adleman succeeded in solving the problem in a test tube. Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. In this paper, we propose a DNA-based graph encoding scheme which can be used to solve some intractable graph problems, such as the subgraph isomorphism problem and its generalized problem - the maximum common subgraph problem, which are known to be NP-complete problems, in the Adleman-Lipton model using polynomial number of basic biological operations.
All Science Journal Classification (ASJC) codes
- Computational Mathematics
- Applied Mathematics