Document Detail


Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction.
MedLine Citation:
PMID:  17904730     Owner:  NLM     Status:  MEDLINE    
Abstract/OtherAbstract:
A new DNA computing algorithm based on a ligase chain reaction is demonstrated to solve an SAT problem. The proposed DNA algorithm can solve an n-variable m-clause SAT problem in m steps and the computation time required is O (3m+n). Instead of generating the full-solution DNA library, we start with an empty test tube and then generate solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the ligation of new variables using Taq DNA ligase. Correct strands are amplified and false strands are pruned by a ligase chain reaction (LCR) as soon as they fail to satisfy the conditions. If we score and sort the clauses, we can use this algorithm to markedly reduce the number of DNA strands required throughout the computing process. In a computer simulation, the maximum number of DNA strands required was 2(0.48n) when n=50, and the exponent ratio varied inversely with the number of variables n and the clause/variable ratio m/n. This algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard SAT problems.
Authors:
Xiaolong Wang; Zhenmin Bao; Jingjie Hu; Shi Wang; Aibin Zhan
Publication Detail:
Type:  Journal Article; Research Support, Non-U.S. Gov't     Date:  2007-08-26
Journal Detail:
Title:  Bio Systems     Volume:  91     ISSN:  0303-2647     ISO Abbreviation:  BioSystems     Publication Date:  2008 Jan 
Date Detail:
Created Date:  2007-12-25     Completed Date:  2008-03-12     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  0430773     Medline TA:  Biosystems     Country:  Ireland    
Other Details:
Languages:  eng     Pagination:  117-25     Citation Subset:  IM    
Affiliation:
Department of Biotechnology, Ocean University of China, Qingdao 266003, People's Republic of China. xiaolong@ouc.edu.cn
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:
Algorithms*
Base Sequence
Computer Simulation*
DNA / genetics*,  metabolism*
Ligases / metabolism*
Molecular Sequence Data
Software Design
Chemical
Reg. No./Substance:
9007-49-2/DNA; EC 6.-/Ligases

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Modelling metapopulations with stochastic membrane systems.
Next Document:  Chiropractic manipulation: reasons for concern?