4 ms·

I don't know of anything in nature which solves the traveling sales person problem, but protein folding does progress in linear time in nature. That may mean t

I don't know of anything in nature which solves the traveling sales person problem, but protein folding does progress in linear time in nature. That may mean that proteins quickly collapse the probability space or have some other "trick" by which they are not NP-complete, or whatever, it is not magic. There is a way and I'm hopeful we can find it.

kurtosis 18y ago
Hey this is from the abstract of: Sequence optimization and designability of enzyme active sites - PNAS v. 102 (2005) Full text is here: http://www.pnas.org/content/102/34/12035.full http://www.pnas.org/content/102/34/12035.full """ Since it was first observed that all known natural proteins adopt one of only ≈1,000 distinct protein folds (1) [emphasis mine], researchers working in the field of computational protein design have endeavored to understand the basis of this biophysical phenomenon and apply the resultant knowledge to the construction of unnatural proteins. Motivated by the observation that certain folds are associated with more natural sequences than others, the principle of fold designability (the number of unique sequences compatible with the backbone structure of the fold) was introduced (1). To place the problem on a mathematical foundation, an analogy has been drawn between sequence space and phase space in statistical physics, where the backbone structure represents a macroscopic state of the system and distinct sequences are microscopic states whose occupation of the macroscopic state is associated with an energy, the folding free energy of the protein. In this language, a fold's designability is correlated with its sequence entropy (2). """
kurtosis 18y ago
For what it's worth I attended a seminar by this guy http://www.princeton.edu/~rajchak/ http://www.princeton.edu/~rajchak/ the other day and he was talking about using optimal control theory to optimize protein sequences for specific enzyme activity. He had a very sophisticated model for how the amino acid sequence determines the shape of the protein's active area. It was way over my head but he treated it as a solved problem. You may find his papers interesting. The combinatorial search results on protein folding are theoretically interesting, but I don't think that they are show stoppers for finding, or optimising the folded configuration of a protein. As you mentioned, most of the degrees of freedom which lead to the exponential size of the search space are irrelevant. A detailed understanding of the physics of how amino acids interact in water with ions can allow one to make approximations that vastly reduce the size of the search space. Plus how much time does it take a protein to find it's native conformation? Let's say the folding time is 10 ms. I think ultrafast pump probe spectroscopy has shown that alpha helices and other secondary structural motifs form on the time scale of 100 ps. Then the protein explores about 10^8 configurations before it finds the native one.
fizx 18y ago
I believe that the reason why proteins fold in polynomial time (not necessarily linear) is that nature's proteins are "easy" to fabricate. To use the TSP as an analogy, think of a protein as a configuration of cities. The proteins in our body are the solutions of the easy configurations, i.e. a group of cities arranged in a circle. Nature hasn't been able to find the really hard solutions. We would like to explore the full configuration space, to look for new proteins, and that's still hard. Or maybe I misunderstand.

kurtosis 18y ago

Hey this is from the abstract of: Sequence optimization and designability of enzyme active sites - PNAS v. 102 (2005) Full text is here: http://www.pnas.org/content/102/34/12035.full http://www.pnas.org/content/102/34/12035.full """ Since it was first observed that all known natural proteins adopt one of only ≈1,000 distinct protein folds (1) [emphasis mine], researchers working in the field of computational protein design have endeavored to understand the basis of this biophysical phenomenon and apply the resultant knowledge to the construction of unnatural proteins. Motivated by the observation that certain folds are associated with more natural sequences than others, the principle of fold designability (the number of unique sequences compatible with the backbone structure of the fold) was introduced (1). To place the problem on a mathematical foundation, an analogy has been drawn between sequence space and phase space in statistical physics, where the backbone structure represents a macroscopic state of the system and distinct sequences are microscopic states whose occupation of the macroscopic state is associated with an energy, the folding free energy of the protein. In this language, a fold's designability is correlated with its sequence entropy (2). """

kurtosis 18y ago

For what it's worth I attended a seminar by this guy http://www.princeton.edu/~rajchak/ http://www.princeton.edu/~rajchak/ the other day and he was talking about using optimal control theory to optimize protein sequences for specific enzyme activity. He had a very sophisticated model for how the amino acid sequence determines the shape of the protein's active area. It was way over my head but he treated it as a solved problem. You may find his papers interesting. The combinatorial search results on protein folding are theoretically interesting, but I don't think that they are show stoppers for finding, or optimising the folded configuration of a protein. As you mentioned, most of the degrees of freedom which lead to the exponential size of the search space are irrelevant. A detailed understanding of the physics of how amino acids interact in water with ions can allow one to make approximations that vastly reduce the size of the search space. Plus how much time does it take a protein to find it's native conformation? Let's say the folding time is 10 ms. I think ultrafast pump probe spectroscopy has shown that alpha helices and other secondary structural motifs form on the time scale of 100 ps. Then the protein explores about 10^8 configurations before it finds the native one.

fizx 18y ago

I believe that the reason why proteins fold in polynomial time (not necessarily linear) is that nature's proteins are "easy" to fabricate. To use the TSP as an analogy, think of a protein as a configuration of cities. The proteins in our body are the solutions of the easy configurations, i.e. a group of cities arranged in a circle. Nature hasn't been able to find the really hard solutions. We would like to explore the full configuration space, to look for new proteins, and that's still hard. Or maybe I misunderstand.