| 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?