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

Complexity and approximability of double digest.

Mark Cieliebak1, Stephan Eidenbenz, Gerhard J Woeginger

  • 1Institute of Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerland. cieliebak@inf.ethz.ch

Journal of Bioinformatics and Computational Biology
|April 27, 2005
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

Quantum approximate multi-objective optimization.

Nature computational science·2025
Same author

A linear time algorithm for linearizing quadratic and higher-order shortest path problems.

Mathematical programming·2025
Same author

Provable bounds for noise-free expectation values computed from noisy samples.

Nature computational science·2024
Same author

Continuous facility location on graphs.

Mathematical programming·2022
Same author

Survey on evaluation methods for dialogue systems.

Artificial intelligence review·2021
Same author

The multi-stripe travelling salesman problem.

Annals of operations research·2017
Same journal

CNV-ECOD: A copy number variation detection method based on ECOD algorithm using next-generation sequencing data.

Journal of bioinformatics and computational biology·2026
Same journal

ReinVar: A model-free paradigm-based reinforcement learning approach to detect copy number variation.

Journal of bioinformatics and computational biology·2026
Same journal

When pipelines run but coordinates fail: A simple spatial specificity check for false locality in post-GWAS analysis.

Journal of bioinformatics and computational biology·2026
Same journal

Comparative benchmarking of template-based, evolutionary-diffusion, and generative language models for IsPETase structure prediction.

Journal of bioinformatics and computational biology·2026
Same journal

Trap spaces as labelled ideals of SCC posets: A structural-functional theory of reachability in asynchronous boolean networks.

Journal of bioinformatics and computational biology·2026
Same journal

Erratum - DDINet: Drug-drug interaction prediction network based on multi-molecular fingerprint features and multi-head attention centered weighted autoencoder.

Journal of bioinformatics and computational biology·2026
See all related articles

The DOUBLE DIGEST problem in DNA sequencing is strongly NP-complete, even with disallowed coincident cut sites. Variations with errors are hard to approximate, and some are impossible to approximate.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genomics

Background:

  • The DOUBLE DIGEST problem is crucial for reconstructing DNA sequences from enzymatic cut sites.
  • Previous studies established weak NP-completeness for this problem.

Purpose of the Study:

  • To establish the strong NP-completeness of the DOUBLE DIGEST problem.
  • To analyze the computational complexity of DOUBLE DIGEST variations under experimental error conditions.
  • To investigate approximation hardness for error-prone DOUBLE DIGEST scenarios.

Main Methods:

  • Complexity theory analysis, specifically focusing on strong NP-completeness.
  • Development of optimization variations to model partial cleavage errors in DNA sequencing.
  • Approximation algorithm analysis to determine hardness results.

Related Experiment Videos

Main Results:

  • DOUBLE DIGEST is proven to be strongly NP-complete, a higher complexity class than previously shown.
  • The variation disallowing coincident cut sites is also strongly NP-complete.
  • Most error-modeling variations of DOUBLE DIGEST are shown to be hard to approximate.
  • Finding feasible solutions for variations with disallowed coincident cut sites and errors is NP-hard, precluding approximation guarantees.

Conclusions:

  • The DOUBLE DIGEST problem and its common variations are computationally intractable.
  • Real-world experimental errors significantly increase the difficulty of approximating solutions for DNA sequence reconstruction.
  • The findings have implications for the efficiency and reliability of large DNA string sequencing methods.