TY - JOUR

T1 - A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers

AU - Hsieh, Sun-Yuan

AU - Chen, Ming Yu

PY - 2008/4/1

Y1 - 2008/4/1

N2 - Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. In this paper, we demonstrate the power of DNA-based computing by showing the graph isomorphism problem can be efficiently solved under this computation model. By generating the solution space using stickers, we present DNA-based algorithms to solve the problem using polynomial number of basic biological operations.

AB - Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. In this paper, we demonstrate the power of DNA-based computing by showing the graph isomorphism problem can be efficiently solved under this computation model. By generating the solution space using stickers, we present DNA-based algorithms to solve the problem using polynomial number of basic biological operations.

UR - http://www.scopus.com/inward/record.url?scp=39449100009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39449100009&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2007.08.005

DO - 10.1016/j.amc.2007.08.005

M3 - Article

AN - SCOPUS:39449100009

VL - 197

SP - 672

EP - 686

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

IS - 2

ER -