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
Current Nanoscience
Title: A “Nano-Dial” Molecular Computing Model Based on Circular DNA
Volume: 6 Issue: 3
Author(s): Cheng Zhang, Jing Yang, Jin Xu and Shudong Wang
Affiliation:
Keywords: Circular DNA, backtracking, algorithm complexity, 3-coloring graph problem
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.
Export Options
About this article
Cite this article as:
Zhang Cheng, Yang Jing, Xu Jin and Wang Shudong, A “Nano-Dial” Molecular Computing Model Based on Circular DNA, Current Nanoscience 2010; 6 (3) . https://dx.doi.org/10.2174/157341310791171072
DOI https://dx.doi.org/10.2174/157341310791171072 |
Print ISSN 1573-4137 |
Publisher Name Bentham Science Publisher |
Online ISSN 1875-6786 |
Call for Papers in Thematic Issues
Role of nanomaterials in fabrication of coatings, Machining and Joining
The application of nanoscience has brought about a revolution in the field of mechanical engineering by providing novel materials, boosting manufacturing processes, and generating cutting-edge products. The purpose of this special issue is to investigate the enormous impact that nanoscience has had on mechanical engineering, with a particular emphasis on ...read more
Advanced Inorganic Nanocomposites and Their Emerging Applications
This special issue collection will highlight developments on the recent trends about the synthesis of metal oxides, nanoclusters, biomaterials, 2D nanomaterials, nanocrystals, nanocomposites, etc. and their applications in electrochemical systems, tissue regeneration, energy storage and harvesting, sensors, etc. The novelty of the methods in the chemical synthesis and their characterizations, ...read more
Applicability of Nanotechnology for Performance Enhancement of Clean Energy Technologies
Population growth, industrialization, and improvement in living quality would lead to further increase in energy demand in near future. Regarding the disadvantages of fossil fuels such as fluctuations in their price, high emissions of greenhouse gases and restriction of their sources, it is crucial to use and exploit alternative energy ...read more
Graphene and 2D Materials for Energy Storage and Conversion
This thematic issue will discuss the recent advances in graphene-based nanomaterials for different energy technologies. Graphene possesses a high surface area, and stable structure and exhibits many interesting electronic, optical, and mechanical properties due to its 2D crystal structure. Graphene is of both fundamental interest and suitable for a wide ...read more
Related Journals
- Author Guidelines
- Graphical Abstracts
- Fabricating and Stating False Information
- Research Misconduct
- Post Publication Discussions and Corrections
- Publishing Ethics and Rectitude
- Increase Visibility of Your Article
- Archiving Policies
- Peer Review Workflow
- Order Your Article Before Print
- Promote Your Article
- Manuscript Transfer Facility
- Editorial Policies
- Allegations from Whistleblowers