Feb. 11, 2004

BACK

Publications in Computational Chemistry & Molecular Biology on Electron Density Mappings by :

• Amenta, N., et al. :
  • Finding alpha-helices in skeletons, 2002.
• Greer, J. :
  • Computer Skeletonization and Automatic Electron Density Map Analysis, 1985.
  • Three-Dimensional Pattern Recognition: An Approach to Automated Interpretation of Electron Density Maps of Proteins, 1974.
• Ioerger, T.R. et al. :
  • Automatic Modeling of Protein Backbones in Electron Density Maps via Prediction of C-alpha Coordinates, 2002.
  • Determining Protein Structure from Electron-density Maps using Pattern Matching, 2000.
• Leherte, L. et al. :
  • Analysis of Three-Dimensional Protein Images, 1997.
• Hongzhi, Li et al.:
  • An Integrated Approach to Protein Backbone Modeling, 2002.
• Swanson, S.M. :
  • Core tracing: depicting connections between features in electron density, 1994.

BibTeX references.

Web links:

• TEXTAL: A Pattern Recognition System for Interpreting Electron Density Maps.

We consider a problem which is part of the process of determining the three-dimensional structure of a protein molecule using X-ray crystallography: given an estimated map of the electron density of the molecule as a function on three-dimensional space, we identify regions which are likely to belong to alpha-helices. Our approach is to compute a new kind of skeleton - the power shape - and then identify the helical substructures within the power shape with a variant of geometric hashing.

Automated methods are described for improved interpretation of protein electron density maps by using basic pattern recognition and other advances in computer science and artificial intelligence. Prepn. of the electron density map, its skeletonization, tracing of the chain, isolation of the central mol., and other features of the method are described, as well as applications to RNase S, Bence-Jones Rhe, and future directions.

Most crystallographers today solve protein structures by first building as much of the protein backbone as possible and then modeling the side chains. Automating the determination of backbone coordinates by computer-based interpretation of the electron density would enhance the speed and possibly improve the accuracy of the structure-solution process. In this paper, a new computational procedure called CAPRA is described that predicts coordinates of C-alpha atoms in density maps and outputs chains of C-alpha atoms representing the backbone of the protein. The result constitutes a significant step beyond tracing the density, because there is ideally a one-to-one correspondence between atoms predicted in the chains output by CAPRA and C-alpha atoms in the true structure (refined model). CAPRA is based on pattern-recognition techniques, including extraction of rotation-invariant numeric features to represent patterns in the density and use of a neural network to predict which pseudo-atoms in the trace are closest to true C-alpha atoms. Experiments with several MAD and MIR electron-density maps of 2.4-2.8 Å resolution reveal that CAPRA is capable of building 90% of the backbone of a protein molecule, with an r.m.s. error for C-alpha coordinates of around 0.9 Å.

Keywords: CAPRA (C-Alpha Pattern Recognition Algorithm); electron-density maps; modelling of protein backbones; prediction of C-alpha atom coordinates.

TEXTAL is an automated system for building protein structures from electron-density maps. It uses pattern recognition to select regions in a database of previously determined structures that are similar to regions in a map of unknown structure. Rotation-invariant numerical values, called features, of the electron density are extracted from spherical regions in an unknown map and compared with features extracted around regions in maps generated from a database of known structures. Those regions in the database that match best provide the local coordinates of atoms and these are accumulated to form a model of the unknown structure. Similarity between the regions in the database and an uninterpreted region is determined firstly by evaluating the numerical difference in feature values and secondly by calculating the electron-density correlation coefficient for those regions with similar feature values. TEXTAL has been successful at building protein structures for a wide range of test electron-density maps and can automatically model entire protein structures in a few hours on a workstation. Models built by TEXTAL from test electron-density maps of known protein structures were accurate to within 0.6-0.7 Å root-mean-square deviation, assuming prior knowledge of C positions. The system represents a new approach to protein structure determination and has the potential to greatly reduce the time required to interpret electron-density maps in order to build accurate protein models.

A fundamental goal of research in molecular biology is to understand protein structure. Protein crystallography is currently the most successful method for determining the three-dimensional (3D) conformation of a protein, yet it remains labor intensive and relies on an expert's ability to derive and evaluate a protein scene model. In this paper, the problem of protein structure determination is formulated as an exercise in scene analysis. A computational methodology is presented in which a 3D image of a protein is segmented into a graph of critical points. Bayesian and certainty factor approaches are described and used to analyze critical point graphs and identify meaningful substructures, such as alpha-helices and beta-sheets. Results of applying the methodologies to protein images at low and medium resolution are reported. The research is related to approaches to representation, segmentation and classification in vision, as well as to top-down approaches to protein structure prediction.

Web link: http://www.ace.uwaterloo.ca/~liho/thesis/protein.html

Two approaches are commonly used to build protein backbone models for protein crystallography: the skeletonization approach and the topological approach. Among the algorithms implementing skeletonization, Greer's algorithm is a popular one. From our testing, however, some problems exist in Greer's algorithm. This thesis addresses two of the problems and provides methods to improve the performance of Greer's algorithm.

One problem in the implementation of Greer's algorithm is the limitation of the thinning algorithm it used: Hilditch's thinning algorithm. The thinning method cannot thin a thick shape well. We developed two methods to address the problem: density-reuse and multiple-loop algorithms. Both methods can effectively eliminate the voxel clusters in the skeleton.

The other improvement of Greer's algorithm is to adopt some methods from the topological approach to improve the chain correctness. We convert the skeleton grid from Greer's algorithm to a skeleton graph. The skeleton graph is then used as the input of the FORR cognitive architecture, which is from the topological approach. Usually the backbone is among the most repeatable paths from the evaluation system in the topological approach. From our testing, this integrated method can improve the chain correctness significiantly (up to 99%).

Paths of high density are traced by (3D) lines (ridges) connecting peaks to passes. Picture complexity approximates that of alpha-carbon models.

BACK

Page created & maintained by Frederic Leymarie, 2003-4.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu