KSL-95-19

Computing the Structure of Large Complexes: Applying Constraint Satisfaction Techniques to Modeling the 16S Ribosomal RNA

Reference: Chen, R.; Fink, D.; & Altman, R. B. Computing the Structure of Large Complexes: Applying Constraint Satisfaction Techniques to Modeling the 16S Ribosomal RNA. Knowledge Systems Laboratory, Medical Computer Science Group, May, 1995.

Abstract: Large macromolecular complexes such as the 16S ribosomal RNA (16S rRNA) frustrate traditional experimental methods of structure determination that succeed with smaller molecules. These large complexes often contain both protein and nucleic acid components composed of thousands of atoms, making them intractable to X-ray crystallographic techniques. Extensive biochemical studies of these macromolecules, however, often yield useful, though sparse, structural information by revealing particular interactions between parts of the macromolecular complex. This type of experimental data can be conceptualized as constraints on the three-dimensional structure of the macromolecule. Computational techniques can be used to reduce the number of valid molecular conformations based on satisfaction of these constraints. In this paper, we apply constraint satisfaction methodologies to produce a set of three-dimensional structures for the 16S rRNA that is consistent with experimental data and provides an estimate of the range of valid 16S rRNA conformations. Starting with the fixed positions of the protein subunits (as determined by neutron diffraction experiments) as well as the predicted secondary structure for the RNA, we determine the location of the RNA segments using information about the proximity these segments to particular proteins (as determined by labelling-protection experiments). In our computations, we use an object representation of the 16S rRNA in which helices are represented as cylindrical objects and proteins as spherical objects. Distance constraints between objects represent experimentally determined helix-helix and helix-protein interactions. An initially large list of possible locations and orientations for each object is reduced by an iterative process involving satisfaction of these constraints. This method eventually produces a list of valid locations/orientations for each object. Based on these final location lists, we can produce candidate three-dimensional structures, or coherent instances, each of which satisfies all the constraints. The system uses an exhaustive grid search, checks distances in a direction-sensitive manner, accommodates disjunctive constraints, and checks for volume overlap violations.

Full paper available as ps.


Jump to... [KSL] [SMI] [Reports by Author] [Reports by KSL Number] [Reports by Year]
Send mail to: ksl-info@ksl.stanford.edu to send a message to the maintainer of the KSL Reports.