Algorithms for Protein Structure Determination by NMR
Time: October 15, 2007, 1pm - 2pm
Place: D344, LSRC
Speaker: Bruce Donald

While automation is revolutionizing many aspects of biology, the determination of three-dimensional protein structure remains a long, hard, and expensive task. Determination of protein structures by nuclear magnetic resonance (NMR) is valuable in many biomedical applications, such as structure-based drug design. Structural studies of proteins can not only provide clues to disease causes, but also provide a basis for the rational design of therapeutic interventions. In this talk, I will discuss novel algorithms and computational methods in biomolecular NMR.

NMR can record thousands of geometric measurements for a protein, as if by using tiny spectroscopic rulers and protractors. Protein structure determination can then be viewed as a combinatorial optimization algorithm for constraint satisfaction, subject to these measurements. For decades, structure determination has relied on interactive model building and stochastic refinement methods.

I will describe a linear-time, combinatorially-precise algorithm for NMR structure determination. The algorithm is optimal in terms of combinatorial (but not algebraic) complexity. This is also the first result showing how any structural data (X-ray or NMR) can be used to produce a deterministic, optimal solution for the protein structure in polynomial time.

I will present experimental results from an implementation of the algorithm on NMR data. I will also review some basic material on protein kinematics and the geometry of NMR data, and discuss applications to protein folding.