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

The approximability of the String Barcoding problem.

Giuseppe Lancia1, Romeo Rizzi

  • 1Dipartimento di Matematica ed Informatica, Universitá di Udine, Via delle Scienze 206, Udine, Italy. lancia@dimi.uniud.it

Algorithms for Molecular Biology : AMB
|August 10, 2006
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

Revisiting Viewing Graph Solvability: An Effective Approach Based on Cycle Consistency.

IEEE transactions on pattern analysis and machine intelligence·2022
Same author

Safety in Multi-Assembly via Paths Appearing in All Path Covers of a DAG.

IEEE/ACM transactions on computational biology and bioinformatics·2021
Same author

MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP.

Bioinformatics (Oxford, England)·2018
Same author

Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics.

IEEE/ACM transactions on computational biology and bioinformatics·2018
Same author

Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly.

IEEE/ACM transactions on computational biology and bioinformatics·2015
Same author

On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly.

BMC bioinformatics·2014
Same journal

Haplotype-aware long-read error correction.

Algorithms for molecular biology : AMB·2026
Same journal

Extension of partial atom-to-atom maps: uniqueness and algorithms.

Algorithms for molecular biology : AMB·2026
Same journal

Lossless pangenome indexing using tag arrays.

Algorithms for molecular biology : AMB·2026
Same journal

Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer.

Algorithms for molecular biology : AMB·2026
Same journal

Probing transcription factor subsets in gene regulatory networks.

Algorithms for molecular biology : AMB·2026
Same journal

Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features.

Algorithms for molecular biology : AMB·2026
See all related articles

This study proves that the String Barcoding (SBC) problem is computationally difficult to approximate, similar to the Set Cover problem. This finding has implications for virus identification using DNA probes.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genomics

Background:

  • The String Barcoding (SBC) problem seeks a minimal set of substrings to differentiate strings.
  • In computational biology, SBC is applied to identify viruses using DNA probes for hybridization experiments.

Purpose of the Study:

  • To analyze the approximation complexity of the String Barcoding problem.
  • To investigate the hardness of approximating the constrained version of SBC with bounded-length probes.

Main Methods:

  • Theoretical analysis of approximation algorithms.
  • Reduction from the Set Cover problem to demonstrate hardness.

Main Results:

  • The String Barcoding problem is proven to be as hard to approximate as the Set Cover problem.

Related Experiment Videos

  • The constrained version of SBC, with probes of bounded length, is also shown to be hard to approximate.
  • These hardness results are demonstrated to be tight.

    • Conclusions:

    • The findings indicate significant computational limitations for efficiently solving the SBC problem and its variants.
    • This has implications for the design and feasibility of microarray-based virus classification.