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

DNA solution of the maximal clique problem

Q Ouyang1, P D Kaplan, S Liu

  • 1NEC Research Institute, 4 Independence Way, Princeton, NJ 08540, USA.

Science (New York, N.Y.)
|October 23, 1997
PubMed
Summary

Researchers solved the maximal clique problem using DNA computing. This molecular biology approach created DNA molecules representing cliques, demonstrating DNA

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

Test of CP Symmetry in the Neutral Decays of Λ via J/ψ→ΛΛ[over ¯].

Physical review letters·2026
Same author

Precise Measurement of the Chromoelectric Dipole Moment of the Charm Quark.

Physical review letters·2026
Same author

Precise Measurement of Matter-Antimatter Asymmetry with Entangled Hyperon-Antihyperon Pairs.

Physical review letters·2026
Same author

Observation of Λ[over ¯]p→K^{+}π^{+}π^{-}π^{0} and Λ[over ¯]p→K^{+}π^{+}π^{-}2π^{0}.

Physical review letters·2026
Same author

First Measurement of the D_{s}^{+}→K^{0}μ^{+}ν_{μ} Decay.

Physical review letters·2026
Same author

Observation of the Electromagnetic Radiative Decays of the Λ(1520) and Λ(1690) to γΣ^{0}.

Physical review letters·2026

Area of Science:

  • Computational biology
  • Molecular computing

Background:

  • The maximal clique problem is a known NP-complete problem.
  • Solving NP-complete problems efficiently remains a significant challenge in computer science.

Purpose of the Study:

  • To investigate the use of molecular biology techniques for solving the maximal clique problem.
  • To demonstrate the potential of DNA computing for tackling complex search problems.

Main Methods:

  • A DNA pool was constructed to represent all six-vertex cliques.
  • A series of selection processes were applied to identify the cliques.

Main Results:

  • The maximal clique problem was successfully solved using the developed DNA computing algorithm.
  • The algorithm exhibited high parallelism and satisfactory fidelity.

Conclusions:

  • This study provides evidence for DNA computing's capability in solving NP-complete search problems.
  • Molecular biology techniques offer a viable approach for computational problem-solving.

Related Experiment Videos