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

Sun-Yuan Hsieh, Chao Wen Huang, Hsin Hung Chou

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)502-512
Number of pages11
JournalApplied Mathematics and Computation
Volume203
Issue number2
DOIs
Publication statusPublished - 2008 Sep 15

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Computational Mathematics
  • Numerical Analysis

Fingerprint Dive into the research topics of 'A DNA-based graph encoding scheme with its applications to graph isomorphism problems'. Together they form a unique fingerprint.

Cite this