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

Protein design is NP-hard.

Niles A Pierce1, Erik Winfree

  • 1Applied and Computational Mathematics, California Institute of Technology, Pasadena, CA 91125, USA. niles@caltech.edu

Protein Engineering
|December 7, 2002
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

Combinatorial decision-making driven by multicomponent surface condensates.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same author

NUPACK: Computational Nucleic Acid Analysis and Design.

ACS synthetic biology·2026
Same author

Models and Algorithms for Equilibrium Analysis of Mixed-Material Nucleic Acid Systems.

ACS synthetic biology·2026
Same author

<i>k</i> -spaces: Mixtures of Gaussian latent variable models.

bioRxiv : the preprint server for biology·2025
Same author

Models and Algorithms for Equilibrium Analysis of Mixed-Material Nucleic Acid Systems.

bioRxiv : the preprint server for biology·2025
Same author

HCR spectral imaging: 10-plex, quantitative, high-resolution RNA and protein imaging in highly autofluorescent samples.

Development (Cambridge, England)·2024
Same journal

Structure of a human Rhinovirus complexed with its receptor molecule.

Protein engineering·2024
Same journal

pH-responsive polymer-assisted refolding of urea- and organic solvent-denatured alpha-chymotrypsin.

Protein engineering·2004
Same journal

Evaluation of different linker regions for multimerization and coupling chemistry for immobilization of a proteinaceous affinity ligand.

Protein engineering·2004
Same journal

Recombinant porcine intestinal carboxylesterase: cloning from the pig liver esterase gene by site-directed mutagenesis, functional expression and characterization.

Protein engineering·2004
Same journal

Periplasmic expression of human growth hormone via plasmid vectors containing the lambdaPL promoter: use of HPLC for product quantification.

Protein engineering·2004
Same journal

Shift of fibril-forming ability of the designed alpha-helical coiled-coil peptides into the physiological pH region.

Protein engineering·2004
See all related articles

Computational protein design faces NP-hard algorithmic challenges in sequence selection. This paper explains the complexity and discusses implications for future algorithm development in protein engineering.

Area of Science:

  • Computational biology
  • Bioinformatics
  • Protein engineering

Background:

  • The field of computational protein design involves complex algorithmic challenges.
  • Sequence selection is a critical step in designing novel proteins computationally.
  • These challenges are recognized within the computer science community.

Purpose of the Study:

  • To elucidate the context of algorithmic challenges in computational protein design.
  • To present a simplified proof demonstrating the complexity.
  • To discuss the impact of these challenges on the advancement of protein design algorithms.

Main Methods:

  • Explanation of the discrete optimization problem.
  • Illustrative proof of NP-hardness.
  • Discussion of algorithmic implications.

Related Experiment Videos

Main Results:

  • The sequence selection problem in computational protein design is NP-hard.
  • Understanding this complexity is crucial for algorithm development.
  • The findings highlight the need for advanced algorithmic approaches.

Conclusions:

  • The NP-hard nature of sequence selection presents significant hurdles for computational protein design.
  • Future progress depends on developing sophisticated algorithms to address this complexity.
  • This research provides a foundation for further algorithmic innovation in the field.