Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
|
 |
|
|
|
|
|
 |
||||||
| ||||||
| ||||||
| ||||||
Geometric Computations in Molecular Biology SS07 (251-1416-00) | ||||||
| ||||||
| ||||||
| ||||||
| Jack Snoeyink, | CAB G39.2, | Phone: 044 632 77 28, |  | . |
| Yves Brise, | CAB G36.2, | Phone: 044 632 77 96, |  | . |
| ||||||
| ||||||
Course Description Course Material Molecule of the Week Assignments Grading and Testat Literature Links
[^ Back to Contents]Although the disciplines of biology and computer science have in the past been poles apart, and students of one discipline have traditionally avoided the other, some of the most exciting developments in science are at their interface. One example is the problem of protein folding − how a sequence of amino acids that is coded for by a gene folds into its three−dimensional structure to perform the processes of life. This is arguably the most intriguing puzzle in science today. The best software solutions known for this problem are built on models that are surprisingly geometric: atoms are often represented as hard spheres and molecules as kinematic chains with rotating joints.
In this seminar course we will explore these models, their use in existing software such as the Rosetta suite from the Baker lab at the University of Washington, and possible extensions to new algorithms or applications. The goal of the seminar is to enable cross-disciplinary communication: that each student will be able to learn enough of the motivation, terminology, problems, and existing applications of geometric computation in structural molecular biology that they will be able to contribute to the solution of problems at the interface. We expect to encounter many topics for possible further research projects.
This seminar is directed primarily at computer science students who would like to learn about biological applications, especially in molecular modeling. We will emphasize a "phenomenological" approach: considering a model embodied in software as more "real" than those that are derived from physical or chemical principles. Biology, biochemistry, and biophysics students who are interested in software are especially welcome, however, because they bring a wealth of background knowledge from a different perspective, and can help keep the instructor honest.
|
|
[^ Back to Contents]
Date Topics Notes Assignments Reading
#1 (21.03.2007) Indroduction, Amino acids,
Protein structures.Lecture slides [PPT],
Lecture notes [PDF],
Carbon origami [PDF], s
Other origami (text in Japanese) [PDF]Molecule of the week [PDF][PS],
Protein shape quiz (with solutions) [PDF],
Shape from hydrogen bonds [PDF]Koehl's Bio-ebook chapter on Structure Classification [Link];
Kavraki's module on Structural Computational Biology: "Introduction and Background" [Link].
Further: MIT Hyperbook on AI and Molecular Biology, Chapter 1 Molecular Biology for Computer Scientists / Lawrence Hunter [PDF]
#2 (28.03.2007) Models of protein structure and energies: simplistic statistical thermodynamics for combinatorialists and hackers Lecture notes [PDF] Exercise Set 2 [PDF][PS] Handout from "Molecular Driving Forces", by Dill and Bromberg;
Theoretical studies of protein-folding thermodynamics and kinetics [PDF];
A Test of Lattice Protein Folding Algorithms [PDF].
Further: A Complete and Effective Move Set for Simplified Protein Folding [PDF]
#3 (04.04.2007) RMSD and optimal alignment Closed-form solution of absolute orientation using unit quaternions [PDF] Exercise Set 3 (Programming assignment) [PDF][PS],
TAM.pdb [PDB],
LF_A.pdb [PDB],
RMSD Solution in MATLAB [ZIP]Closed-form solution of absolute orientation using orthonormal matrices [PDF];
Kavraki's module "Molecular Distance Measures" [Link];
Matlab Primer [PDF][PS]
#4 (11.04.2007) Fragments and Rosetta Molecule of the week: Ribosome [PPT] - "Protein Structure and Function" Sections 1-22 [PDF], 2-0 [PDF], 2-1 [PDF], 2-2 [PDF], 4-6 [PDF], 4-7 [PDF];
Report on CASP4 from the Rosetta group (Schonbrun etal.) [PDF];
A decade of CASP (Moult) [PDF]
#5 (18.04.2007) Evaluating structure quality: MolProbity Lecture notes [PDF],
H-bonds in Rosetta [PPT], Molecule of the week: ATP Synthase [PPT]Exercise Set 4 (MolProbity) [PDF][PS],
MolProbity notebook of exercise session [HTML]Kavraki's modules: "Representing Proteins in Silico and Protein Forward Kinematics" [Link], and "Motion Planning for Proteins: Biophysics and Applications" [Link]
#6 (25.04.2007) Forward & inverse kinematics for protein & RNA Baxter slides [Link],
Lotan slides [PPT]Programming assignment 2 [Link],
Exercise Set 5 (H-bond) [PDF][PS],
H-bond exercise file [KIN]Kavraki's modules: "Protein Inverse Kinematics and the Loop Closure Problem" [Link],
Cyclic coordinate descent [PDF]
#7 (02.05.2007) Sidechain placement and loop modeling Protein design [PPT], Notes on Cyclic Coordinate Descent [PDF] - -
#8 (09.05.2007) Protein design & combinatorial search algorithms - - -
#9 (16.05.2007) Rigidity & the molecular conjecture Lecture notes [PDF] CCD Solution in MATLAB [ZIP],
Linkage worksheet [DOC]Protein Flexibility Predictions Using Graph Theory [PDF]
#10 (23.05.2007) Pebble games for analysis of first order rigidity - Project Ideas [DOC] -
#11 (30.05.2007) Crystallography and electron density Electron density, contour trees [PPT],
Clustering [PDF]- -
#12 (06.06.2007) Class canceled! - - -
#13 (13.06.2007) Molecular surfaces and solvent accessibility Docking [PPT],
Distance Geometry [PPT],
Nuclear Magnetic Resonance [PDF]- Havel on Distance Geometry [PDF]
#14 (20.06.2007) Power diagrams and skin - - Kavraki's module on Molecular Shapes and Surfaces [Link],
Connolly review of molecular surfaces [Link],
Alpha shapes & skin surfaces [Link 1] [Link 2]
| ||||||
| ||||||
| ||||||
[^ Back to Contents]
Student Molecule Presentation Slides Jack Snoeyink GroEL, GroES June 20 [PPT] Jack Snoeyink Rhinovirus May 30 [PPT] Justas Arasimavićius Immunoglobulin May 23 [PPT] Bálint Miklós Anthrax toxin May 16 [PDF] Ahmet Cengiz Öztireli Luciferase May 9 [PPT] Andreas Razen Prion protein May 2 [PPT] Sara Van Nortwick Kinesin April 25 [PPT] Johanna Wolf ATP Synthase April 18 [PPT] Jack Snoeyink Ribosome April 11 [PPT]
| ||||||
| ||||||
| ||||||
The students are required to give two short presentations and work on one key project during the semester. Key projects will involve programming, although there is freedom in designing projects that are of appropriate level of difficulty and in the choice of programming language.
The first presentation will be 15-20 minutes in class on a protein structure. The second will be 20-30 minutes on a problem area or software approach that will ideally develop into a course project on an algorithm for molecular structure classification, manipulation, analysis, visualization, or ...
Students will be able to design a project that meets their ability and interests, and either work alone or in small teams if the project merits; a written report will be required. Guidelines on presentations, projects, and reports will be forthcoming on this web site.Other than the presentations and the key assignment there will also be weekly assignments, which may invlove some written exercises, or classroom exercises, or simply getting familiar with the software used in this course.
| ||||||
| ||||||
| ||||||
[^ Back to Contents]The grade for this seminar course will be based on two presentations and a project report. No final examination is anticipated, although one could be created if there is student demand.
Since the grading depends on the participation and the assignments during the semester, there is no Testat given for this lecture.
| ||||||
| ||||||
| ||||||
[^ Back to Contents]Some of the following books are accessible online. The others are available at the Computer Science Library in the IFW building.
- Gregory Petsko & Dagmar Ringe: Protein Structure and Function, Primers in Biology, New Science Press Ltd, 2004.
This book is available online for access from inside the ETH network. You can download chapters as PDF files by clicking on the link beside the chapter heading. (Note: you do not have to download the individual sections; when you download a whole chapter, all its sections are included.)- Patrice Koehl: The Bio eBook: Technical notes on biocomputing, 2002.
This book is only available online.- Andrew Leach: Molecular Modelling: Principles and Applications (2nd edition), Pearson Education, 2001.
- Ken A. Dill: Molecular Driving Forces: Statistical Thermodynamics in Chemistry & Biology, Garland Science Publishing, 2002.
- Tamar Schlick: Molecular Modeling and Simulation, Springer, 2002.
| ||||||
| ||||||
| ||||||
| Last modified: , by Yves Brise. |
|
|
