Talking with Ken Dill

Yesterday I had the chance to speak with Ken Dill for an hour about protein folding, dynamical simulation of small molecules (e.g. proteins), etc. He was at Brown to give a talk, but I had a class during his talk so I had to miss it. Here's a brief transcript of the ideas I got out of the informal discussion before his talk.

One interestng idea he mentioned is called the "replica exchange" method of combinatorial optimization. The idea is similar to simulated annealing, but it's more parallelizeable, and you don't have to choose an exponent. Here's how it works. You create a fixed number of "levels". Each level has a temperature, which is higher than the temperature of the level below it. Each level is initialized with some point from your search space (probably chosen randomly). Then each level does a local search of its solution, and rather frequently it checks to see whether its point is "better" than the point in the level below it (the cooler one). If so, then you swap the points in the two levels (note: you don't just copy the point in the higher level and overwrite the one in the lower level). Intuitively this means that at any given time, your best solution is being explored very carefully (with the lowest temperature), while your worst solution is thrashing about wildly, trying to find a better point in your search space. The algorithm is highly parallel in the number of levels.

Another idea he mentioned was using the CYK algorithm to do protein folding. It sounded like it was really more of a metaphor than actually reusing the exact algorithm. The only "grammar rule" they seem to use is to eliminate a stretch of amino acids if there's a fold that brings two hydrophobic amino acids into contact, according to the HP model. Repeat until there's nothing left. Ties are broken by the lowest energy conformation. They haven't introduced backtracking yet.

The final thing he mentioned was the idea of trying to derive macro-level laws about a dynamical system by trying to simulate all possibilities of a micro-level simulation, and then combining them in some way (e.g. averaging). The inspiration is Feynman's demonstration of why light travels in a straight line -- which is because the wave function of all the infinite possibilities cancel each other out until the straight line is all you have left. (By the way, this is a reall cool demonstration, since it explains things like why the shadow cast by a wall is fuzzy instead of crisp). But it seems to me that Feynman's idea worked out mainly because the system he was talking about actually had a real wave function, and canceling out of probabilities was a real quantum mechanical phenomenon. On the other hand, molecular simulation is largely based on classical models which really don't have the same kind of probabilistic behavior (even if they are really small). So I'm not sure how well it would actually work. Clearly it has to stop working at some point, since truly dynamical systems aren't predictable by closed-form laws (by which I mean systems with positive feedback loops, multiple stable basins of attraction, discrete transition points, etc).