6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2012)

Prof. Erik Demaine       TA: Jayson Lynch


[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Accessibility]

Lecture 21 Video     [previous] [next]

[+] Protein folding: HP model of protein folding, NP-hardness and approximation, unique optimal foldings, protein design.
Interlocked 3D chains: Lubiw's problem, unlocking 2-chains, unlocking two 3-chains and 2-chains, interlocking 3-chains, interlocking 3-chain with 4-chain, interlocking 4-chain with triangle, interlocking 3-chain with quadrangle, topological vs. geometric arguments, rigid and fixed-angle variations.
OPTIONAL — questions will be answered during C20.

This lecture continues our discussion on protein folding, this time focusing on simple theoretical models of the forces, rather than the mechanics, behind protein folding. In particular, we'll see the HP model, a lattice model capturing the hydrophobia of certain amino, which try to hide from the surrounding water. Finding the optimal folding a given protein is NP-complete, but there are some decent constant-factor approximations, and it's also not known whether protein design is similarly hard. We'll see one step in the direction of design: guaranteeing a unique optimal folding.

Then we'll turn to a fun problem of interlocked linkages. It's known that you need five bars to lock an open chain, but can you interlock multiple chains each with less than five bars? The answer is yes, with a nearly complete characterization of the possibilities. One consequence we'll see is how to cut a chain of n bars into around n/2 pieces that are not interlocked, while n/4 pieces are necessary.

Download Video: 360p, 720p

Handwritten notes, page 1/12[previous page][next page][PDF]

Handwritten notes, page 1/12[previous page][next page][PDF]

Slides, page 1/16[previous page][next page][PDF]

Figure 9.10 of GFALOP

Slides, page 1/16[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.