Plasmid Resolving the Satisfiability Problem with DNA Computing Models
Abstract:Resolving the satisfiability problem is the current focus of much research in DNA computing models. This paper proposes a DNA computing model that resolves the satisfiability problem based on plasmids, in order to overcome the difficulty of DNA computing that requires the conversion of time complexity into space complexity. The model firstly constructs a DNA segment, encoding all variables of the given satisfiability problem, then the segment is inserted as foreign DNA into modified plasmid via genetic recombinant technology. During the course of computation, the plasmid is gradually enzymatically digested by means of restriction enzymes, followed by gel electrophoresis and ligation, to generate and separate the solution of the given problem. The initial data pool of the proposed model contains only one type of DNA strand, and the required steps of enzymatic digestion operations is m, where m is the number of clauses of the given satisfiability problem. The proposed computing model demonstrates the massive parallelism of DNA computing.
Document Type: Research Article
Publication date: 2007-11-01
More about this publication?
- Journal of Computational and Theoretical Nanoscience is an international peer-reviewed journal with a wide-ranging coverage, consolidates research activities in all aspects of computational and theoretical nanoscience into a single reference source. This journal offers scientists and engineers peer-reviewed research papers in all aspects of computational and theoretical nanoscience and nanotechnology in chemistry, physics, materials science, engineering and biology to publish original full papers and timely state-of-the-art reviews and short communications encompassing the fundamental and applied research.
- Editorial Board
- Information for Authors
- Submit a Paper
- Subscribe to this Title
- Terms & Conditions
- Ingenta Connect is not responsible for the content or availability of external websites