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

Computational complexity of a problem in molecular structure prediction.

J T Ngo1, J Marks

  • 1Committee on Higher Degrees in Biophysics, Harvard University, Cambridge, MA 02138.

Protein Engineering
|June 1, 1992
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

Search for charged lepton flavor violation in narrow upsilon decays.

Physical review letters·2010
Same author

The standardization of staphylococcal alpha-antitoxin, with special reference to anomalous haemolysins including delta-lysin.

The Journal of hygiene·2010
Same author

Laparoscopic transanal abdominal transanal resection with sphincter preservation for rectal cancer in the distal 3 cm of the rectum after neoadjuvant therapy.

Surgical endoscopy·2010
Same author

Measurement of D{0}-D[-over]{0} mixing from a time-dependent amplitude analysis of D{0}-->K+pi{-}pi{0} decays.

Physical review letters·2010
Same author

Measurement of B-->K{*}(892)gamma branching fractions and CP and Isospin asymmetries.

Physical review letters·2010
Same author

Precise measurement of the e+e- --> pi+pi-(gamma) cross section with the initial state radiation method at BABAR.

Physical review letters·2010

Protein structure prediction is computationally hard. This study proves the NP-hardness of typical energy minimization problems, suggesting efficient algorithms must exploit protein-specific properties.

Area of Science:

  • Computational biology
  • Theoretical computer science
  • Biophysics

Background:

  • Protein structure prediction is a fundamental challenge in biology.
  • Previous complexity arguments focused on conformational space size, not algorithmic efficiency.
  • The theory of NP-completeness offers a framework for assessing computational intractability.

Purpose of the Study:

  • To investigate the computational complexity of protein structure prediction.
  • To determine if typical energy minimization formulations are NP-hard.
  • To guide the development of efficient protein folding algorithms.

Main Methods:

  • Formalizing protein structure prediction as mathematical problems.
  • Applying the theory of NP-completeness to analyze problem intractability.

Related Experiment Videos

  • Proving the NP-hardness of empirical potential energy function minimization for macromolecules.

    • Main Results:

    • Two typical mathematical formulations of macromolecule energy minimization are NP-hard.
    • Efficient exact algorithms for protein structure prediction are unlikely unless NP-complete problems are efficiently solvable.
    • Potential for efficient algorithms hinges on exploiting protein-specific properties.

    Conclusions:

    • Protein structure prediction, via typical energy minimization, is computationally intractable.
    • Future algorithms must leverage unique protein characteristics for efficiency.
    • Systematic analysis of prediction problems can reveal complexity sources and guide algorithm design.