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

An exponential example for a partial digest mapping algorithm

Z Zhang1

  • 1Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.

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

Microphthalmia (mi) in murine mast cells: regulation of its stimuli-mediated expression on the translational level.

Blood·1997
Same author

Tamoxifen activates cellular phospholipase C and D and elicits protein kinase C translocation.

International journal of cancer·1997
Same author

The effect of patient characteristics on response to focal laser treatment for diabetic macular edema.

Ophthalmology·1997
Same author

Use of buccal smears for rapid detection of peroxisomes.

European journal of pediatrics·1997
Same author

Development of a novel thiol reagent for probing ion channel structure: studies in a model system.

Biochemistry·1997
Same author

Fast measurements of transmission of erythema effective irradiance through clothing fabrics.

Health physics·1997
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 presents an exponential example for Skiena et al.'s backtracking algorithm used in the turnpike reconstruction problem for DNA physical mapping. This finding addresses a long-standing question about the algorithm's practical efficiency.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Computer Science Algorithms

Background:

  • The turnpike reconstruction problem is a key challenge in DNA physical mapping.
  • Skiena et al. developed a practical backtracking algorithm for this problem.
  • The existence of exponential examples for this algorithm remained an open question.

Purpose of the Study:

  • To investigate whether exponential worst-case examples exist for Skiena et al.'s backtracking algorithm.
  • To provide a concrete counterexample to the algorithm's practical efficiency in certain scenarios.

Main Methods:

  • The study focuses on theoretical computer science and algorithmic analysis.
  • A specific, constructed dataset is used as an input for the backtracking algorithm.

Related Experiment Videos

  • The performance of the algorithm on this dataset is analyzed to demonstrate exponential time complexity.

    • Main Results:

    • An exponential example for Skiena et al.'s backtracking algorithm has been identified.
    • This example demonstrates that the algorithm's runtime can grow exponentially with input size.
    • The findings challenge the assumption of consistent practical efficiency for all inputs.

    Conclusions:

    • The existence of exponential examples for the turnpike reconstruction backtracking algorithm is confirmed.
    • This has implications for the theoretical limitations of the algorithm in DNA physical mapping.
    • Further research may be needed to develop more robust algorithms for this problem.