An error-resilient encoding with fewer DNA strands for graph problems on DNA computing

Abstract

Adleman, who created DNA computing, presented a solution method for the Hamiltonian path problem using a manipulation called extraction. However, the efficiency of extraction is considered low. Amos and colleagues presented a solution method for the NP-complete graph problem using an efficient manipulation called removal. But this method has the problem that a larger number of DNA strands are required. This paper improves Amos's method in which the sequence of vertices is used as the initial candidate solution. An encoding for the graph problem is proposed in which the number of required DNA strands is reduced by using the sequence of vertices connected by edges as the initial candidate solution. Using the proposed method, solution methods are presented for the Hamiltonian path problem and the subgraph isomorphism problem. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(8): 49–58, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20186

Related Papers

• → The Hamiltonian circuit problem for circle graphs is NP-complete(1989)60 cited
• → Towards solution of the set-splitting problem on gel-based DNA computing(2004)33 cited
• → Complexity of the hamiltonian cycle in regular graph problem(1994)26 cited
• → An error-resilient encoding with fewer DNA strands for graph problems on DNA computing(2005)
• → Application of DNA Nanoparticle Conjugation on the Hamiltonian Path Problem(2021)