An error-resilient encoding with less DNA strands for graph

摘要

Adleman presented the solution of the Hamiltonian path problem with extract operation. But extract has high error probability. Amos et al. presented the solution for some NP-complete graph problems with remove operation. Although remove has very low error probability, we need a large amount of DNA strands to encode the problems. In this paper, we improve the method by Amos and propose the encoding for graph problems to reduce amount of DNA. We also present the solution of the Hamiltonian path problem and the sub graph isomorphism problem.