## 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 language | English |
---|---|

Pages (from-to) | 502-512 |

Number of pages | 11 |

Journal | Applied Mathematics and Computation |

Volume | 203 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2008 Sep 15 |

## All Science Journal Classification (ASJC) codes

- Applied Mathematics
- Computational Mathematics
- Numerical Analysis