title: Complexity of protein folding.
abstract: It is believed that the native folded three-dimensional conformation of a protein is its lowest free energy state, or one of its lowest. It is shown here that both a two- and three-dimensional mathematical model describing the folding process as a free energy minimization problem is NP-hard. This means that the problem belongs to a large set of computational problems, assumed to be very hard ("conditionally intractable"). Some of the possible ramifications of this result are speculated upon.
authors.affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia 19104-6395.
authors.forename: A S
authors.initials: AS
authors.lastname: Fraenkel
mesh_terms: D004247:DNA / Q000737:chemistry; D008433:Mathematics; D008962:Models, Theoretical; D009690:Nucleic Acid Conformation; D011487:Protein Conformation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*
chemical_list: D011506:Proteins; D004247:DNA