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

Reconstructing strings from substrings

S S Skiena1, G Sundaram

  • 1Department of Computer Science, State University of New York, Stony Brook 11794-4400, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 1, 1995
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

Trial of protective effect of fissure sealants, in vivo, on the palatal surfaces of anterior teeth, in patients suffering from erosion.

Journal of dentistry·2010
Same author

Effect of resin coating on dentine compared to repeated topical applications of fluoride mouthwash after an abrasion and erosion wear regime.

Journal of dentistry·2007
Same author

Bonding to and protecting worn palatal surfaces of teeth with dentine bonding agents.

Journal of oral rehabilitation·2004
Same author

Preventative measures for bulimic patients with dental erosion.

The European journal of prosthodontics and restorative dentistry·2001
Same author

Dealing with errors in interactive sequencing by hybridization.

Bioinformatics (Oxford, England)·2001
Same author

Designing better phages.

Bioinformatics (Oxford, England)·2001
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

This study introduces an interactive DNA sequencing method using substring queries. This approach significantly reduces the number of queries needed to determine DNA sequences compared to traditional methods.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Traditional DNA sequencing by hybridization (SBH) involves fixed chips and can be query-intensive.
  • Interactive approaches offer potential for more efficient DNA sequence determination.

Purpose of the Study:

  • To investigate an interactive approach for DNA sequencing using substring queries.
  • To establish theoretical bounds on the number of queries required for sequence reconstruction.
  • To compare the power of substring versus subsequence queries and explore optimizations for known sequence information.

Main Methods:

  • Developing an interactive model where queries ask if a specific string is a substring of the unknown DNA sequence.
  • Deriving tight lower bounds on query complexity using arguments based on de Bruijn sequences.

Related Experiment Videos

  • Analyzing the power of subsequence queries in comparison to substring queries.
  • Investigating the computational complexity of building optimal decision trees for DNA reconstruction with prior information.

    • Main Results:

    • Interactive substring queries significantly reduce the number of queries needed for DNA sequencing compared to fixed SBH chips.
    • Tight bounds on the complexity of reconstructing unknown strings from substring queries were established.
    • Subsequence queries were shown to be substantially more powerful than substring queries, achieving information-theoretic limits.
    • Determining an optimal decision tree for reconstructing partially known DNA strings is NP-complete, but an approximation algorithm was developed.

    Conclusions:

    • Interactive DNA sequencing via substring queries offers a more efficient alternative to conventional methods.
    • The theoretical framework provides insights into the fundamental limits of sequence reconstruction from different query types.
    • While optimal decision tree construction is complex, approximation algorithms can yield efficient solutions for specific applications.