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 protein threading problem with sequence amino acid interaction preferences is NP-complete

R H Lathrop1

  • 1Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge 02139.

Protein Engineering
|September 1, 1994
PubMed
Summary

Finding the optimal protein threading is NP-hard when allowing variable-length gaps and sequence interactions. This means polynomial time algorithms are unlikely for protein structure prediction, impacting computational strategies.

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

DNA sequence and structure: direct and indirect recognition in protein-DNA binding.

Bioinformatics (Oxford, England)·2002
Same author

A multi-queue branch-and-bound algorithm for anytime optimal search with biological applications.

Genome informatics. International Conference on Genome Informatics·2002
Same author

An anytime local-to-global optimization algorithm for protein threading in theta (m2ñ2) space.

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

A Bayes-optimal sequence-structure theory that unifies protein sequence-structure recognition and alignment.

Bulletin of mathematical biology·1998
Same author

Modeling protein homopolymeric repeats: possible polyglutamine structural motifs for Huntington's disease.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·1998
Same author

Global optimum protein threading with gapped alignment and empirical pair score functions.

Journal of molecular biology·1996

Area of Science:

  • Computational biology
  • Bioinformatics
  • Protein structure prediction

Background:

  • Protein structure prediction is crucial for understanding protein function.
  • Amino acid interaction preferences are used for threading sequences onto known structural motifs.
  • The computational complexity of finding globally optimal protein threading remains an open question.

Purpose of the Study:

  • To determine if a polynomial time algorithm exists for globally optimal protein threading.
  • To identify the conditions that influence the computational complexity of protein threading.
  • To provide a theoretical basis for current and future protein structure prediction algorithms.

Main Methods:

  • Analysis of the protein threading decision problem under specific conditions.

Related Experiment Videos

  • Proof of NP-completeness for the decision problem and NP-hardness for the optimization problem.
  • Theoretical computer science, specifically complexity theory.

    • Main Results:

    • The protein threading decision problem is NP-complete when variable-length gaps and sequence interactions are permitted.
    • The problem of finding the globally optimal protein threading is NP-hard under these conditions.
    • This implies no polynomial time algorithm is possible unless P=NP.

    Conclusions:

    • The inverse protein folding problem is computationally complex, akin to the direct protein folding problem.
    • Current algorithms for protein threading may need to consider these complexity limitations.
    • Insights from other NP-complete problems could inform the development of more efficient predictive algorithms.