Computational Geometry and 3D Structure in Molecular Biology

Honors class
Spring 2002

Tuesday 3:00 - 5:00 PM

Klara Kedem - klara@cs.bgu.ac.il , room 308, Bldg 58, 647-7845.

Overview

Schedule

List of Papers

Some Relevant WWW Links

Overview

My goal is to look at some algorithmic problems related to three-dimensional structures in chemistry and molecular biology, primarily from the perspective of computational geometry. There will be a brief introduction on computational geometry.

Schedule

Week 1: Introduction and some neat examples in computational geometry
Week 2: Analyzing protein shape with the unit-vector RMS
Week 3: Finding the consensus shape for a protein family

Abstracts of talks

Week 1: TBA

Week 2 (and paper): We consider the problem of identifying common three-dimensional substructures between proteins. Our method is based on comparing the shape of the alpha-carbon backbone structures of the proteins in order to find 3D rigid motions that bring portions of the geometric structures into correspondence. We propose a geometric representation of protein backbone chains that is compact yet allows for similarity measures that are robust against noise and outliers. We represent the structure of the backbone as a sequence of unit vectors, defined by each adjacent pair of $\alpha$-carbons; we then define a measure of the similarity of two protein structures based on the RMS (root mean squared) distance between corresponding orientation vectors of the two proteins.

Our measure has several advantages over measures that are commonly used for comparing protein shapes, such as the minimum RMS distance between the 3D positions of corresponding atoms in two proteins. This new measure behaves well for identifying common substructures, in contrast with position-based measures where the nonmatching portions of the structure dominate the measure. At the same time, it avoids the quadratic space and computational difficulties associated with methods based on distance matrices and contact maps. We show applications of our approach to detecting common contiguous substructures in pairs of proteins, as well as the more difficult problem of identifying common protein domains (i.e., larger substructures that are not necessarily contiguous along the protein chain).
Week 3 (and paper): We define and prove properties of the "consensus shape for a family of proteins", a protein-like structure that provides a compact summary of the significant structural information for a protein family. If all members of a protein family exhibit a geometric relationship between corresponding alpha carbons then that relationship is preserved in the consensus shape. In particular, distances and angles that are consistent across family members are preserved. For the consensus shape, the spacing between successive alpha carbons is variable, with small distances in regions where the members of the protein family exhibit significant variation and large distances (up to the standard spacing of about 4 angstrom) in regions where the family members agree. Despite this non-protein-like characteristic, the consensus shape preserves and highlights important structural information. We describe an iterative algorithm for computing the consensus shape and prove that the algorithm converges. We also present the results of experiments in which we build consensus shapes for several known protein families.

List of Papers

Below, we list some papers on relevant topics that might be interesting:

We use some abbreviations for various journals and conference proceedings below:

SCG = Proceedings of the ACM Symposium on Computational Geometry

JMB = Journal of Molecular Biology

PSFG = Proteins: Structure, Function, and Genetics

JCICS = J. Chem. Inf. Comput. Sci.