Shape Analysis for Protein Alignment
Jeff M Phillips

Protein structure analysis is an important aspect of understanding the similarity between different proteins and their function. We realize that chemical properties also play an important role in this understanding. So our goal is to analyze the geometric and structural components of these problems (our strengths) within frameworks domain experts are familiar. Our contributions are described in two areas: analyzing alignment under the ubiquitous RMSD measure and finding geometric structure on protein-protein interface surfaces.
Alignment under Transformations with RMSD
Summary
The most common distance used to determine the similarity between two protein structures is the root mean squared distance (RMSD) between two corresponding sets of atoms. When two proteins have the same chemistry this is straightforward, so we focus on the case of aligning two proteins with different chemistry, but similar structure. We provide an empirically effective technique for dealing with outliers that has nice provable convergence properties that builds upon the Iterative Closest Point (ICP) algorithm. Code is available upon request. Furthermore, the points under alignment can be annotated with chemical information. This heuristic approach is complimented by our work on the first polynomial algorithm to provably approximate the minimum RMSD distance between two point sets under rotation and translation. For backbone alignment, we have also inverstigated techniques, both heuristic and with guarantees but less practical, for aligning piecewise-linear curves using RMSD.
Visuals

Alignment of two scans of the dragon model (left) and zoom of tail (right) with standard ICP algorithm.

Alignment of two scans of the dragon model (left) and zoom of tail (right) with our FICP algorithm accouting for outliers.
Structural Motifs in Protein-Protein Interface Surfaces
Summary
Given two proteins in a complementary alignment (a bound docking configuration), the anatomy of this alignment provides many clues to why and how proteins become a compound. One well-defined way to analyze this alignment is by constructing a protein-protein interface surface describing the Voronoi faces of the atoms separating these proteins. Our contribution constructs geometric motifs on these interfaces, akin to alpha-helices and beta-strips in a protein structure. These motifs are bumps on the interface surface representing protrusions of one protein into the other. The pattern and magnitude of these motifs can compactly describe an interface surface as well as pointing to likely hot-spot residues which are critical to the overall binding energy. This information has been integrated into the Biogeometry's Protein-Protein Interface Surface MAPS software.
Visuals

Motifs in the protein-protein interface surface for 1BRS from two views.
Publications (and other documents)
  • Outlier Robust ICP for Minimizing Fractional RMSD.
         Jeff M. Phillips, Ran Liu, Carlo Tomasi. 6th International Conference on 3-D Digital Imaging and Modeling. August 2007.
         long version as Duke University Technical Report CS-2006-05. May 2006.
         poster/abstract for 4th Eurographics Symposium on Geometry Processing. June 2006.

  • Segmenting Motifs in Protein-Protein Interface Surfaces.
         Jeff M. Phillips, Johannes Rudolph, Pankaj K. Agarwal. Proceedings of the 6th Workshop on Algorithms in Bioinformatics (WABI). September 2006.
         poster for Duke Frontiers 2006.

  • On Bipartite Matching under the RMS Distance.
         Pankaj K. Agarwal, Jeff M. Phillips. 18th Canadian Conference on Computational Geometry. August 2006.

  • Mean Shape Backbone Alignment.
         Jeff M. Phillips.
         slides from a talk I gave a a BioGeometry meeting in August 2005.
    jeff's home page