Transcript Document
Work In Progress Monte Carlo Simulation of Folding Processes for 2D Linkages Modeling Proteins with Off-Grid HP-Chains Ileana Streinu Leo Guibas Rachel Kolodny Michael Levitt Smith College Stanford University Simple Models of Proteins Model a Protein as 2D Chain of Beads – Each amino acid (=bead) in the chain is polar or hydrophobic – PHHPH (still need to specify distances) Simple Exact Models • Explores what non-local interactions can create – Structure – Stability – Folding kinetics • Proposed by K. Dill (1985) From: “Principles of protein folding – A perspective from simple exact models” Dill et al. Protein Science (1995) Simple Off-Grid Model • Still HP-chains – Same energy model • Still in 2D • Simple means simple motions – Based on pseudo-triangulation mechanisms • Focus on folding Overview • Pseudo Triangulations and 1DOF mechanisms in 2D • Simple simulation of folding • Problems and future work pseudo triangle pseudo 4-gon Pointy Pseudo Triangulation (PT) – 2n-3 edges - Pointy – Planar – Maximal • Laman graph – Minimally rigid Every chain can be pseudotriangulated by adding n-2 edges 1DOF mechanisms Removing a hull edge turns it into a 1DOF mechanism advantages 2D Grid Off-Grid by PT • Can explore exhaustively (exponential time) •Tighter sphere packing •Varying bond lengths •Every compact state can be reached • Fixed bond length • Fixed bond angles •More complicated •Need Monte-Carlo simulations to explore Monte-Carlo Simulation • A way to generate Boltzmann distribution on the states of the system 1 E ( C ) / kT p (C ) e Z • Need: – Transition probability between configurations satisfies detailed balance eE / kT if E 0 W ( A B) otherwise 1 – Finite number of steps between any 2 configurations System Validation • Measure (as a function of time) – Energy – Radius of gyration • Look for secondary structure formation • Can we “fold” large “proteins” ? PT Linkage Package Uses: •PT workbench by L.Kettner •CGAL •GLUT & GLUI •CLAPACK Runs on Linux PT Linkage Package H/P Nodes Calculates contractive and expansive motion Linkage edges Motion Model • Move mechanism until PT property is violated at an alignment event. – This guarantees chain self-avoidance throughout • Alignment can occur at any vertex – Not ones inside a rigid component – Find first one Motion Model • Write a quadratic system for each vertex – 2n-3 variables – 2n-3 equations i • Fixed edge lengths – 2n-4 edges j • Alignment edges ik and jk at vertex k k Motion Model • Take into account that nodes have radii • Expansive/Contractive • Use Newton-Raphson to solve set of equations • Doesn’t always work PT Linkage Package Rigid Components Rigid Components of a PT • Detecting rigid components in linear time – In PT: maximal convex components – with J. Snoeyink • O(n4) algorithm for general minimally rigid graphs minus one edge [SIH] Detecting Rigid Components Maximal convex components - Keep turning left (as little as possible) -Mark your path& notice when you visit twice -Backtrack if needed Linear time PT Linkage Package Random PT Picking a Random PT • Given set of points – Unknown: total number of PTs • Conjecture: Random walk on 1-Skeleton of PT polytope is rapidly mixing – Flip polynomial number of times to find random PT What Next ? • Understand why/when NewtonRaphson fails to find motion • Experiment with large proteins Thank you