A DNA-based graph encoding scheme with its applications to graph isomorphism problems

摘要

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.