Algorithmic Problems in Computational Structural Biology

Instructors : frederic.cazals@inria.fr, dorian.mazauric@inria.fr

Topics covered

• Lecture 1: fundamental geometric constructions for collections of balls
  • Delaunay triangulations and Voronoi diagrams [G-BY,G-E1]
  • alpha-shapes [G-E2,G-E3]
• Lecture 2: Molecular surfaces, volumes, and interfaces
  • Collections of balls and space-filling diagrams [G-E3]
  • Unions of balls: surfaces and volumes [G-C1]
  • Modeling macro-molecular interfaces [G-C2,P-JBC]
• Lecture 3: Introduction to protein structure
  • Structural biology: the structure-function-dynamics paradigm [P-F]
  • Modeling protein structures: the static setting [P-F]
  • Modeling protein structures: the dynamic setting [P-FS,P-W]
• Lecture 4: Practical with Visual Molecular Dynamics and the Structural Bioinformatics Library
  • Proteins and their hierarchical structure [P-BT]
  • The PDB file format
  • Elementary analysis under VMD: static structures
  • Elementary analysis under VMD: trajectories
• Lecture 5: Graphs and algorithms--introduction
  • Modeling and graph problems (chapter 1 of [C-1])
  • Algorithms and complexity of algorithms (chapter 8 of [C-1])
  • Application to structural biology ([C-3] and [C-4])
• Lecture 6: Graphs, combinatorial problems, and complexity theory
  • Some complexity classes: P, NP... (chapter 15 and chapter 16 of [C-1])
  • Approximability and hardness of approximation ([C-2] and chapter 17 of [C-1])
  • Applications in structural biology ([C-3] and [C-4])
• Lecture 7: Graphs and algorithmic techniques
  • Decomposition of graphs for dynamic programming (chapter 18 of [C-1])
  • Exponential algorithm (e.g. Branch & Bound) (chapter 18 of [C-1])
  • Mathematical programs (e.g. linear programming) (chapter 2 and chapter 13 of [C-1])
  • Application to structural biology, continued ([C-3] and [C-4])
• Lecture 8: Exam

References sorted by topic

Geometric and topological modeling

• [G-BY] Algorithmic Geometry, J-D. Boissonnat and M. Yvinec, Cambridge University Press, 1998.
• [G-E1] Geometry and topology for mesh generation, volume 7 of Cambridge Monographs on Applied and Computational Mathematics, H. Edelsbrunner, Cambridge, 2001.
• [G-E2] H. Edelsbrunner; Weighted alpha shapes; Technical Report UIUCDCS-R-92-1760, Univ Illinois; 1992.
• [G-E3] H. Edelsbrunner; The union of balls and its dual shape; Discrete Comput. Geom. 13; 1995.
• [G-C1] F. Cazals and H. Kanhere and S. Loriot; Computing the Volume of Union of Balls: a Certified Algorithm; ACM Transactions on Mathematical Software; 38 (1); 2011.
• [G-C2] F. Cazals; Revisiting the Voronoi description of Protein-Protein interfaces: Algorithms; IPAR International Conference on Pattern Recognition in Bioinformatics; 2010.

Protein structure

• [P-F] A. Fersht, Structure and mechanism in protein science: a guide to enzyme catalysis and protein folding, Freeman, 1999.
• [P-BT] C. Branden and J. Tooze, Introduction to Protein Structure (2nd Ed.), Garland publishing, 1999.
• [P-FW] D. Frankel and B. Smit, Understanding molecular simulation, Academic press, 2002.
• [P-W] D.J. Wales, Energy Landscapes, Cambridge University Press, 2003.
• [P-JBC] J. Janin and R. P. Bahadur and P. Chakrabarti; Protein-protein interaction and quaternary structure; Quarterly reviews of biophysics 41 (2); 2008.

Graph algorithms

• [C-1] Combinatorial optimization: algorithms and complexity C. H. Papadimitriou, and K. Steiglitz Courier Corporation. 1982 (new versions available).
• [C-2] Approximation algorithms, V. V. Vazirani, College of Computing, Georgia Institute of Technology, 1997 (new versions available).
• [C-3] Unveiling Contacts within Macro-molecular assemblies by solving Minimum Weight Connectivity Inference Problems, D. Agarwal, C. Caillouet, D. Coudert, and F. Cazals, Molecular and Cellular Proteomics, 14, 2015.
• [C-4] Protein Structure Comparison: From Contact Map Overlap Maximisation to Distance-based Alignment Search Tool, N. Malod-Dognin, PhD thesis, Univ. Rennes 1, 2010.

Grading