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

Hardness of flip-cut problems from optical mapping

V Dancík1, S Hannenhalli, S Muthurkrishnan

  • 1Department of Mathematics, University of Southern California, Los Angeles 90089-1113., USA. dancik@hto.usc.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|July 1, 1997
PubMed
Summary

Optical mapping, a new restriction map technology, faces computational challenges. The Exclusive Binary Flip Cut (EBFC) problem and its variants are proven NP-complete, indicating no efficient polynomial-time solutions exist.

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

Genome-wide analysis of chromosomal features repressing human immunodeficiency virus transcription.

Journal of virology·2005
Same author

Enrichment of regulatory signals in conserved non-coding genomic sequence.

Bioinformatics (Oxford, England)·2001
Same author

Promoter prediction in the human genome.

Bioinformatics (Oxford, England)·2001
Same author

Mutation-tolerant protein identification by mass spectrometry.

Journal of computational biology : a journal of computational molecular cell biology·2001
Same author

The sequence of the human genome.

Science (New York, N.Y.)·2001
Same author

Efficiency of database search for identification of mutated and modified proteins via mass spectrometry.

Genome research·2001

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Optical mapping is an emerging technology for generating DNA restriction maps.
  • Computational challenges exist in aligning partial maps and determining molecular orientation.

Purpose of the Study:

  • To analyze the computational complexity of the Exclusive Binary Flip Cut (EBFC) problem.
  • To determine efficient solutions for optical mapping data analysis.

Main Methods:

  • Formalization of the Exclusive Binary Flip Cut (EBFC) problem.
  • Complexity analysis using NP-completeness proofs.

Main Results:

  • The EBFC problem is proven to be NP-complete.
  • Several variants of the EBFC problem are also NP-complete.

Related Experiment Videos

  • Efficient polynomial-time solutions are unlikely unless P=NP.

    • Conclusions:

    • The computational problems associated with optical mapping are complex.
    • The findings suggest limitations for efficient algorithms in constructing consensus restriction maps from optical mapping data.