Re: Protein folding and P = NP

From: Mark Kvale (kvale.nospam_at_pacbell.net)
Date: 01/23/04 

Date: Fri, 23 Jan 2004 01:00:18 GMT

mike3 wrote:

> Hi.
>
> What would happen if an algorithm capable of performing highly
> accurate protein folding in polynomial time was found? Would it prove
> P = NP? And if it did, what would this lead to?

The short answer is no, it would not prove P=NP.

The longer answer is that protein folding is not necessarily an NP problem.
Many biological proteins fold quickly and reproducibly, indicating a wide,
deep, unique basin of attraction and/or helper molecules to guide the
folding path. Even proteins, such as the immunoglobulins, which take a long
time to fold, do so reproducibly. If there were an exponential number of
deep minima, reproducibility could not happen unless there was a much
wider, deeper, unique basin of attraction and/or helper molecules guiding
the folding sequence.

When biologists talk of the protein folding problem, they are talking about
the class of proteins that are biologically relevant, which so far consist
of the proteins that fold reproducibly.

For random polymers of amino acids, there is empirical evidence of a random
energy landscape that does induce random glassy behavior in the
conformational dynamics, but I don't know of any theorems proving that
biologically realistic models are NP. You need to prove NP before finding a
P folding algorithm and proving P=NP :)

        -Mark

Relevant Pages

  • Re: Lifes range = 0-50C
    ... Allow me to reemphasize, life not only ... it *thrives.* Some Thermotoga microbes are ... explain the bias of salt bridges in thermophilic proteins. ... It is also a general consensus amongst biologists that the last common ...
    (sci.bio.evolution)
  • Re: proton to electron mass ratio may have changed
    ... I find it generally ironic that Biologists who are way more competent ... What is there to envy? ... Biological discoveries are made in spite of Darwin's theory. ... we have to remember that fooj thinks proteins are not molecules... ...
    (talk.origins)