Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction.

Xiaolong Wang1, Zhenmin Bao, Jingjie Hu

  • 1Department of Biotechnology, Ocean University of China, Qingdao 266003, People's Republic of China. xiaolong@ouc.edu.cn

Bio Systems
|October 2, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Divergence From Temperate Models: Pollution Dominance and Stochastic Assembly in a Continental Freshwater System Under Compressed Modernity.

Global change biology·2026
Same author

Influence of short-term water sample storage on environmental RNA metabarcoding-based biodiversity assessment.

Journal of environmental sciences (China)·2026
Same author

Development of a dye-based enzymatic recombinase amplification method for rapid and visual detection of acute hepatopancreatic necrosis disease.

Journal of invertebrate pathology·2026
Same author

Distinguishing cancerous from non-malignant breast cells using viscoelastic creep and functional principal component analysis.

Journal of the mechanical behavior of biomedical materials·2026
Same author

Efficient DNA Extraction Coupled with Fluorescence Loop-Mediated Isothermal Amplification (LAMP) for On-Site Early Warning Detection of Vibrio parahaemolyticus.

Marine biotechnology (New York, N.Y.)·2026
Same author

Genome-wide characterization of the TGF-β superfamily identifies bmp15, gdf9, and gsdf as sex-biased candidate regulators of gonadal differentiation in the synchronous hermaphrodite Plectropomus leopardus.

Comparative biochemistry and physiology. Part D, Genomics & proteomics·2026
Same journal

The bridges evolution built: In search of mechanisms that couple scales of perception and action.

Bio Systems·2026
Same journal

Spatiotemporal bursting in simulated cultures of cortical neurons.

Bio Systems·2026
Same journal

A brief discussion on recent models shedding light on how life emerged.

Bio Systems·2026
Same journal

Memory-based strategy reputation and adaptive learning in spatial evolutionary games: A robust agent-based model for cooperation dynamics.

Bio Systems·2026
Same journal

Coherent Photonic Biofields: Revisiting Fritz-Albert Popp's Hypothesis.

Bio Systems·2026
Same journal

Ruliological Resilience: Pattern Restoration and Robustness in Wolfram Patterns. A Basis for Regeneration, Not Just in Cone Shells?

Bio Systems·2026
See all related articles

A novel DNA computing algorithm utilizes ligase chain reaction (LCR) to efficiently solve SAT problems. This method reduces DNA strand requirements and offers a scalable, error-tolerant approach for complex computational challenges.

Area of Science:

  • Biomolecular Computing
  • Computational Complexity
  • Synthetic Biology

Background:

  • Boolean satisfiability (SAT) problems are fundamental in computer science and AI.
  • Existing computational methods for SAT struggle with scalability for large, complex instances.
  • DNA computing offers a potential alternative with massive parallelism.

Purpose of the Study:

  • To introduce a new DNA computing algorithm for solving SAT problems.
  • To enhance efficiency and reduce resource requirements compared to existing DNA computing approaches.
  • To demonstrate the algorithm's scalability and error tolerance for hard SAT problems.

Main Methods:

  • Development of a DNA algorithm based on ligase chain reaction (LCR).
  • Step-by-step extension of partial solutions using DNA ligation with Taq DNA ligase.

Related Experiment Videos

  • Amplification of correct DNA strands and pruning of false strands via LCR.
  • Scoring and sorting of clauses to minimize DNA strand usage.

    • Main Results:

    • The algorithm solves an n-variable, m-clause SAT problem in m steps with computation time O(3m+n).
    • Computer simulations showed a maximum of 2(0.48n) DNA strands required for n=50 variables.
    • The number of DNA strands scales inversely with the number of variables and clause/variable ratio.
    • Demonstrated significant reduction in DNA strand requirements through clause scoring and sorting.

    Conclusions:

    • The proposed DNA computing algorithm is highly space-efficient and error-tolerant.
    • It presents a scalable solution for tackling large and complex SAT problems.
    • This LCR-based approach advances the field of DNA-based computation for combinatorial problems.