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

Hairpin formation in DNA computation presents limits for large NP-complete problems.

Dafa Li1, Hongtao Huang, Xinxin Li

  • 1Department of Mathematical Sciences, National Laboratory for AI, Tsinghua University, 100084 Beijing, PR China. dli@math.tsinghua.edu.cn

Bio Systems
|December 4, 2003
PubMed
Summary

DNA computing faces limitations in solving large NP-complete problems due to the high probability of hairpin loop formation. This instability restricts the size of problems solvable with current DNA computing paradigms.

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

Effects of Vitamin E on Growth Performance, Biochemical Indices, Antioxidant Capacity, and Ovarian Development in Female Chinese Sturgeon (<i>Acipenser sinensis</i>) Broodstock.

Animals : an open access journal from MDPI·2026
Same author

The impact of nursing intervention based on teach-back method on self-management behavior and negative emotions of postoperative patients with aortic dissection.

Frontiers in cardiovascular medicine·2026
Same author

Encephalomyocarditis virus impairs the blood-brain barrier by degrading tight junction proteins via AKT3-dependent autophagic and apoptotic pathways.

Virulence·2026
Same author

Decoupling Bulk Homogenization and Interfacial Reconstruction via a Triple-Alkali-Cation Interlayer for High-Performance Perovskite Solar Cells.

Advanced materials (Deerfield Beach, Fla.)·2026
Same author

Shared drone route scheduling optimization.

PloS one·2026
Same author

EMCV Non-Structural Protein 2C Antagonizes cGAS-STING-Mediated Type I Interferon Signaling via Promoting K48-Linked Polyubiquitination and Degradation of STING.

Viruses·2026

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Molecular Computing

Background:

  • DNA computing offers novel approaches for solving complex computational problems like NP-complete problems.
  • Previous paradigms, particularly for the 3-SAT problem, have shown promise but require rigorous evaluation for scalability.

Purpose of the Study:

  • To assess the practical limitations of current DNA computing paradigms for NP-complete problems.
  • To investigate the propensity for deleterious secondary structures, specifically hairpin loops, in DNA strands used for computation.

Main Methods:

  • Mathematical modeling and probability calculations were employed to analyze hairpin loop formation.
  • The probability of hairpin formation, p(n,l), was derived based on DNA strand length (n) and hairpin stability (l).

Related Experiment Videos

  • The maximum number of problem instances (m) solvable was determined as a function of p(n,l) and a desired probability threshold (a).

    • Main Results:

    • The study demonstrates that hairpin loops are highly probable in DNA strands used in current computing paradigms.
    • The probability of hairpin formation, p(n,l), is shown to be significantly high, even for moderate strand lengths.
    • Calculations indicate that the number of solvable NP-complete problem instances (m) is severely limited, restricting practical applications.

    Conclusions:

    • Current DNA computing paradigms are unlikely to solve large instances of NP-complete problems due to inherent instability.
    • The high probability of hairpin loop formation acts as a critical bottleneck, limiting the scalability and effectiveness of DNA-based computation for complex problems.