Generic placeholder image

Current Nanoscience

Editor-in-Chief

ISSN (Print): 1573-4137
ISSN (Online): 1875-6786

A “Nano-Dial” Molecular Computing Model Based on Circular DNA

Author(s): Cheng Zhang, Jing Yang, Jin Xu and Shudong Wang

Volume 6, Issue 3, 2010

Page: [285 - 291] Pages: 7

DOI: 10.2174/157341310791171072

Price: $65

Abstract

A novel molecular computing model based on circular DNA was developed to solve a 3-coloring graph problem. This computing model uses circular DNA and works as to dial a number. The method of selecting true solutions is similar to dialing on a telephone. Moreover, the key methods in this model were circularization of single single-strand DNA (ssDNA) molecules and a backtracking deletion algorithm. In the course of computing, the structure of the DNA molecule was transformed into linear double-strand DNA (dsDNA), linear ssDNA, and circular ssDNA. For a 3-coloring graph problem with n vertices, the algorithm time complexity and the space complexity are both O(n2) at most. The computing achievement by this model indicates that circular DNA has extensive applications in molecular computing research.

Keywords: Circular DNA, backtracking, algorithm complexity, 3-coloring graph problem


Rights & Permissions Print Cite
© 2024 Bentham Science Publishers | Privacy Policy