Kinematics of Molecules
Notice a change in the schedule below (D.H., 19.12.04)
Nir Ben-Tal , Department of Biochemistry
Dan Halperin , School of Computer Science
Kinematics is the study of motion of objects regardless of the causes of this motion. (Not to be confused with Kinetics.) There are close connections between the study of motion in robotics and in molecular biology. However, structural bioinformatics raises new and challenging computational kinematic problems due to the large number of degrees of freedom typically involved. The goal of the seminar is to get the audience acquainted with kinematic issues (problems and some solutions) in structural bioinformatics. We will review techniques (heuristics as well as exact methods) and applications.
The seminar is primarily geared towards students with significant computational background. (It does not assume prior knowledge in molecular biology, but requires willingness to pick up the basics and relevant terminology.) This said, the first part of the seminar (inverse kinematics, loop closure) relies mainly on not-too-complex math. The second and shorter part (dynamic maintenance of kinematic structures) assumes familiarity with data structures and algorithms at the senior(last-year)-undergrad level.
The seminar will start with two introductory meetings, followed in subsequent weeks by student presentations. Here's the program, revised on 10/11/04.
Introduction I (D.H.)
Kinematics: Brief introduction and basic terminology.
Survey of the seminar's topics and papers.
27.10.04 + half of the meeting on 3.11
Introduction II (N.B.)
Introduction to protein structure.
PART I: Inverse kinematics, loop closure, and related problems
3.11.04 + 10.11 (Amit)
The Denavit-Hartenberg model, 3D direct and inverse kinematics, from J. Craig, "Introduction to Robotics: Mechanics and Control", Chapters 3 and 4.
Canutescu A.A., Dunbrack R.L. Jr., Cyclic coordinate descent: A robotics algorithm for protein loop closure, Protein Sci. 2003 May;12(5):963-72.
LaValle, S. M., Finn, P. W., Kavraki, L. E., and Latombe, J.-C., A Randomized Kinematics-based Approach to Pharmacophore-Constrained Conformational Search and Database Screening, Journal of Computational Chemistry, 21(9):731-747, 2000.
E. A. Coutsias, C. Seok, M. P. Jacobson and K. E. Dill, A kinematic view of loop closure, J. Comput. Chem. 25 (2004) 510-528.
J. Cortes, T, Simeon, M. Renaud-Simeon and V. Tran, Geometric algorithms for the conformational analysis of long protein loops, J. Comput. Chem. 25 (2004) 956-967.
Slides, set no. 1 (ppt)
I. Lotan, H van den Bedem, A. M. Deacon and J.-C Latombe, Computing protein structures from electron density maps: The missing loop problem, Proc. WAFR 2004, 153-168.
Slides, set no. 2 (ppt)
A. Enosh, S.J. Fleishma, N. Ben-Tal and D. Halperin, Assigning transmembrane segments to helics in intermediate-resolution structures, Bioinformatics Vol. 20, Suppl. 1 (ISMB 2004), pp. 122-129.
Database of Macromolecular Movements , M. Gerstein, W. Krebs, and others
M. Kim, G. Chirikjian, Modeling macromolecular machines using rigid-cluster networks, Proc. WAFR 2004, 123-136.
PART II: Dynamic maintenance of large kinematic structures
D. Halperin, J.-C. Latombe, and R. Motwani Dynamic maintenance of kinematic structures, Algorithms for Robotic Motion and manipulation (WAFR '96), J.-P. Laumond and M. Overmars (editors), A.K. Peters, Wellesley, 1997, 155-170.
29.12.04 No meeting
I. Lotan, F. Schwarzer, D. Halperin and J.-C. Latombe, Algorithm and data structures for efficient energy maintenance during Monte Carlo simulation of proteins. Journal of Computational Biology 11(2004), 902-932.
J. Gao, L. Guibas and A. Nguyen, Deformable spanners and applications, in Proc. ACM Symp. on Computational Geometry 2004, 190-199.
E. Eyal and D. Halperin, Dynamic maintenance of molecular surfaces under conformational changes. Manuscript, 2004.