Protein design is NP-hard.

By Niles A. Pierce, Erik Winfree. 2002

284 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

Citations in the corpus

Protein sequence design with a learned potential (2022, methodology): “This dif ﬁ cult task 12 is often described as the inverse of protein folding — given a protein backbone, design a sequence that folds into that conformation.”
Scientific Benchmarks for Guiding Macromolecular Energy Function Improvement (2013, methodology): “(6.2) would require us to compute the exact solution to the NP-Complete sidechain optimization problem (Pierce & Winfree, 2002) for the numerator, and, for an N residue protein, to repeat that computation 20 N times for each possible sequence for the denominator.”
Rosetta3: An Object-Oriented Software Suite for the Simulation and Design of Macromolecules (2011, neutral): “This problem is NP-complete (Pierce and Winfree, 2002).”
A Generic Program for Multistate Protein Design (2011, background): “The search through sequence space which the genetic algorithm performs is NP-Complete for the same reasons that the search through rotamer space is NP-complete [51].”
Machine-learning-guided directed evolution for protein engineering (2018, methodology): “The problem of finding optimal sequences is NP-hard: there is no known polynomial-time method for searching this space 4 .”
Direct prediction of profiles of sequences compatible with a protein structure by neural networks with fragment‐based local and energy‐based nonlocal profiles (2014, methodology): “Sequence or sequence profiles obtained from protein design programs require solving a NP -hard combinatorial optimization problem 25 .”
Rapid Protein Side-Chain Packing via Tree Decomposition (2005, methodology): “The tree decomposition of a sparse graph has been applied to many NP-hard problems such as frequency assignment problem [35] and Bayesian inference [36].”
Modeling Symmetric Macromolecular Structures in Rosetta3 (2011, methodology): “This problem is NP-Complete [6], so Rosetta uses a stochastic algorithm [7].”
Assessing computational methods for predicting protein stability upon mutation: good on average but not in the details. (2009, background): “As one further divides the space into smaller (higher resolution) bits, the search is growing exponentially (Pierce and Winfree, 2002).”
Realizing the classical XY Hamiltonian in polariton simulators. (2016, unknown): “The parameters of the numerical simulations of equations (1)”
Machine learning in protein engineering (2018, methodology): “The problem of ﬁnding optimal sequences is NP-hard, meaning that there is no known polynomial-time method for searching this space (Pierce & Winfree, 2002).”
FireDock: Fast interaction refinement in molecular docking (2007, methodology): “Most of the methods express the van der Waals interactions by the modified Lennard-Jones 6–12 potentials with a smoothed repulsive part to avoid extreme sensitivity to clashes caused by small backbone movements and the rotamer discretization.”
Navigating the protein fitness landscape with Gaussian processes (2012, background): “First, the space of possible protein sequences is incomprehensibly large and will never be searched exhaustively by any means, naturally, in the laboratory, or computationally (2, 3).”
De Novo Protein Design for Novel Folds using Guided Conditional Wasserstein Generative Adversarial Networks (gcWGAN) (2019, background): “, 2017) The inverse problem of protein design is often similarly pursued following the energy minimum principle (Koga et al., 2012; Gainza et al., 2016; Pierce and Winfree, 2002).”