Concepedia

On the Complexity of Protein Folding

Pierluigi Crescenzi, DEBORAH GOLDMAN, Christos Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis

Journal of Computational Biology · 1998 · 365 citations · 8 references

DOI

Concepts

Abstract

We show that the protein folding problem in the two-dimensional H-P model is NP-complete.

References

8

The Protein Folding Problem

Hue Sun Chan, Ken A. Dill · Physics Today · 1993 · 303 citations

, , +12

Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications

Ron Unger, John Moult · Bulletin of Mathematical Biology · 1993 · 169 citations

, , +14

Complexity of protein folding

Aviezri S. Fraenkel · Bulletin of Mathematical Biology · 1993 · 133 citations

, , +12

Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications

Ron Unger, John Moult · Bulletin of Mathematical Biology · 1993 · 113 citations

, , +14

Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model

Richa Agarwala, Serafim Batzoglou, Vlado Dančík et al. · 1997 · 88 citations · Full text

, , +16