Algorithmic Problems in Computational Structural Biology
Instructors : frederic.cazals@inria.fr, dorian.mazauric@inria.fr
Topics covered
This class covers topics at the crossroads of computational geometry,
computational topology, graph theory, combinatorial algorithms, and
structural biology  biophysics. Each lecture consists of two sessions
of 1h30.
 Lecture 1: fundamental geometric constructions for collections of balls
 Delaunay triangulations and Voronoi diagrams [GBY,GE1]
 alphashapes [GE2,GE3]
 Lecture 2: Molecular surfaces, volumes, and interfaces
 Collections of balls and spacefilling diagrams [GE3]
 Unions of balls: surfaces and volumes [GC1]
 Modeling macromolecular interfaces [GC2,PJBC]
 Lecture 3: Introduction to protein structure
 Structural biology: the structurefunctiondynamics paradigm [PF]
 Modeling protein structures: the static setting [PF]
 Modeling protein structures: the dynamic setting [PFS,PW]
 Lecture 4: Practical with Visual Molecular Dynamics and the Structural Bioinformatics Library
 Proteins and their hierarchical structure [PBT]
 The PDB file format
 Elementary analysis under VMD: static structures
 Elementary analysis under VMD: trajectories
 Lecture 5: Graphs and algorithmsintroduction
 Modeling and graph problems (chapter 1 of [C1])
 Algorithms and complexity of algorithms (chapter 8 of [C1])
 Application to structural biology ([C3] and [C4])
 Lecture 6: Graphs, combinatorial problems, and complexity theory
 Some complexity classes: P, NP... (chapter 15 and chapter 16 of [C1])
 Approximability and hardness of approximation ([C2] and chapter 17 of [C1])
 Applications in structural biology ([C3] and [C4])
 Lecture 7: Graphs and algorithmic techniques
 Decomposition of graphs for dynamic programming (chapter 18 of [C1])
 Exponential algorithm (e.g. Branch & Bound) (chapter 18 of [C1])
 Mathematical programs (e.g. linear programming) (chapter 2 and chapter 13 of [C1])
 Application to structural biology, continued ([C3] and [C4])
 Lecture 8: Exam
References sorted by topic
Geometric and topological modeling
 [GBY] Algorithmic Geometry, JD. Boissonnat and M. Yvinec, Cambridge University Press, 1998.
 [GE1] Geometry and topology for mesh generation, volume 7 of Cambridge
Monographs on Applied and Computational Mathematics,
H. Edelsbrunner, Cambridge, 2001.
 [GE2]
H. Edelsbrunner; Weighted alpha shapes; Technical Report
UIUCDCSR921760, Univ Illinois; 1992.

[GE3] H. Edelsbrunner; The union of balls and its dual shape;
Discrete Comput. Geom. 13; 1995.
 [GC1]
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.
 [GC2] F. Cazals;
Revisiting the Voronoi description of ProteinProtein interfaces: Algorithms;
IPAR International Conference on Pattern Recognition in
Bioinformatics; 2010.
Protein structure
 [PF] A. Fersht, Structure and mechanism in protein science: a guide to enzyme
catalysis and protein folding, Freeman, 1999.
 [PBT] C. Branden and J. Tooze, Introduction to Protein Structure (2nd
Ed.), Garland publishing, 1999.
 [PFW] D. Frankel and B. Smit, Understanding molecular simulation, Academic press, 2002.
 [PW] D.J. Wales, Energy Landscapes, Cambridge University Press, 2003.
 [PJBC]
J. Janin and R. P. Bahadur and P. Chakrabarti;
Proteinprotein interaction and quaternary structure;
Quarterly reviews of biophysics 41 (2); 2008.
Graph algorithms

[C1] Combinatorial optimization: algorithms and complexity
C. H. Papadimitriou, and K. Steiglitz
Courier Corporation. 1982 (new versions available).

[C2] Approximation algorithms,
V. V. Vazirani,
College of Computing, Georgia Institute of Technology, 1997 (new versions available).

[C3] Unveiling Contacts within Macromolecular assemblies by solving Minimum Weight Connectivity Inference Problems,
D. Agarwal, C. Caillouet, D. Coudert, and F. Cazals,
Molecular and Cellular Proteomics, 14, 2015.

[C4] Protein Structure Comparison: From Contact Map Overlap Maximisation to Distancebased Alignment Search Tool,
N. MalodDognin,
PhD thesis, Univ. Rennes 1, 2010.
Grading
The final grade will be the weighted average of the class
participation (1/5) and the mark of a 2h written exam (4/5).