Protein structure determination via an efficient geometric build-up algorithm

Background

A protein structure can be determined by solving a so-called distance geometry problem whenever a set of inter-atomic distances is available and sufficient. However, the problem is intractable in general and has proved to be a NP hard problem. An updated geometric build-up algorithm (UGB) has been developed recently that controls numerical errors and is efficient in protein structure determination for cases where only sparse exact distance data is available. In this paper, the UGB method has been improved and revised with aims at solving distance geometry problems more efficiently and effectively.

Methods

An efficient algorithm (called the revised updated geometric build-up algorithm (RUGB)) to build up a protein structure from atomic distance data is presented and provides an effective way of determining a protein structure with sparse exact distance data. In the algorithm, the condition to determine an unpositioned atom iteratively is relaxed (when compared with the UGB algorithm) and data structure techniques are used to make the algorithm more efficient and effective. The algorithm is tested on a set of proteins selected randomly from the Protein Structure Database-PDB.

Results

We test a set of proteins selected randomly from the Protein Structure Database-PDB. We show that the numerical errors produced by the new RUGB algorithm are smaller when compared with the errors of the UGB algorithm and that the novel RUGB algorithm has a significantly smaller runtime than the UGB algorithm.

Conclusions

The RUGB algorithm relaxes the condition for updating and incorporates the data structure for accessing neighbours of an atom. The revisions result in an improvement over the UGB algorithm in two important areas: a reduction on the overall runtime and decrease of the numeric error.

     

A polynomial-time algorithm for de novo protein backbone structure determination from nuclear magnetic resonance data.

We describe an efficient algorithm for protein backbone structure determination from solution Nuclear Magnetic Resonance (NMR) data. A key feature of our algorithm is that it finds the conformation and orientation of secondary structure elements as well as the global fold in polynomial time. This is the first polynomial-time algorithm for de novo high-resolution biomacromolecular structure determination using experimentally recorded data from either NMR spectroscopy or X-ray crystallography. Previous algorithmic formulations of this problem focused on using local distance restraints from NMR (e.g., nuclear Overhauser effect [NOE] restraints) to determine protein structure. This approach has been shown to be NP-hard, essentially due to the local nature of the constraints. In practice, approaches such as molecular dynamics and simulated annealing, which lack both combinatorial precision and guarantees on running time and solution quality, are used routinely for structure determination. We show that residual dipolar coupling (RDC) data, which gives global restraints on the orientation of internuclear bond vectors, can be used in conjunction with very sparse NOE data to obtain a polynomial-time algorithm for structure determination. Furthermore, an implementation of our algorithm has been applied to six different real biological NMR data sets recorded for three proteins. Our algorithm is combinatorially precise, polynomialtime, and uses much less NMR data to produce results that are as good or better than previous approaches in terms of accuracy of the computed structure as well as running time.     

A differential geometric treatment of protein structure comparison

The technique of model-building a protein of known sequence but unknown tertiary structure from the structures of homologous proteins is probably so far the most reliable means of mapping from primary to tertiary structure. A key step towards the realization of the aim is to develop ways of aligning three-dimensional structures of homologus proteins, thereby deriving the rules useful for protein modelling. We have developed a generalized differential-geometric representation of protein local conformation for use in a protein comparison program which aligns protein sequences on the basis of their sequence and conformational knowledge. Because the differetial-geometric distance measure between local conformations is independent of the coordinate frame and remains chirality information, the comparison program is easily implemented, relatively rational and reasonably fast. The utility of this program for aligning closely and distantly related homologous proteins is demonstrated by multiple alignment of globins, serine proteinases and aspartic proteinase domains. Particularly, the method has reached the rational alignment between the mammalian and microbial serine proteinases as compared with many published alignment programs.     

A parameterized algorithm for protein structure alignment.

This paper proposes a parameterized polynomial time approximation scheme (PTAS) for aligning two protein structures, in the case where one protein structure is represented by a contact map graph and the other by a contact map graph or a distance matrix. If the sequential order of alignment is not required, the time complexity is polynomial in the protein size and exponential with respect to two parameters D(u)/D(l) and D(c)/D(l), which usually can be treated as constants. In particular, D(u) is the distance threshold determining if two residues are in contact or not, D(c) is the maximally allowed distance between two matched residues after two proteins are superimposed, and D(l) is the minimum inter-residue distance in a typical protein. This result clearly demonstrates that the computational hardness of the contact map based protein structure alignment problem is related not to protein size but to several parameters modeling the problem. The result is achieved by decomposing the protein structure using tree decomposition and discretizing the rigid-body transformation space. Preliminary experimental results indicate that on a Linux PC, it takes from ten minutes to one hour to align two proteins with approximately 100 residues.     

Breaking symmetry in the structure determination of (large) symmetric protein dimers

We demonstrate a novel methodology to disrupt the symmetry in the NMR spectra of homodimers. A paramagnetic probe is introduced sub-stoichiometrically to create an asymmetric system with the paramagnetic probe residing on only one monomer within the dimer. This creates sufficient magnetic anisotropy for resolution of symmetry-related overlapped resonances and, consequently, detection of pseudocontact shifts and residual dipolar couplings specific to each monomeric component. These pseudocontact shifts can be readily incorporated into existing structure refinement calculations and enable determination of monomer orientation within the dimeric protein. This methodology can be widely used for solution structure determination of symmetric dimers.     

A calculation strategy for the structure determination of symmetric demers by 1H NMR

The structure determination of symmetric dimers by NMR is impeded by the ambiguity of inter- and intramonomer NOE crosspeaks. In this paper, a calculation strategy is presented that allows the calculation of dimer structures without resolving ther ambuguity by additional experiments (like asymmetric labeling). The strategy employs a molecular dynamic-based simulated annealing approach to minimize a traget function. The experimental part of the target function contains distance restraints that correctly describe the ambiguity of the NOE peaks, and a novel term that restrains the symmetry of the dimer without requiring the knowledge of the symmetry axis. The use of the method is illustrated by three examples, using experimentally obtained data and model data derived from a known structure. For the purpose of testing the method, it is assumed that every NOE crosspeak is ambiguous in all three cases. It is shown that the structure of a homologous protein is known and in ab intio structure determination. The method can be extended to higher order symmetric multimers. © 1993 Wiley-Liss, Inc.     

A modified Chou and Fasman protein structure algorithm

A FORTRAN program PRSTRC has been developed for protein secondarystructure prediction, which is a modified Chou and Fasman (1978)analysis. This implementation carries out a running averageof amino acid structure occurrence frequencies, utilizes a simpleset of nucleation conditions, and allows user control over nucleationthreshold and cutoff parameters. The algorithm includes predictionof the newly defined secondary structure elements: omega loops(1986). It also generates a charge distribution and hydropathyprofile. Output includes a simple graphic display for a printer,or a CRT using color addition. Correct structures are predictedfor T. dyscritum hemerythrin and the variable domain of mouseimmunoglobin k-chain. Received on November 17, 1986; accepted on June 10, 1987     

A probabilistic fragment-based protein structure prediction algorithm

Conformational sampling is one of the bottlenecks in fragment-based protein structure prediction approaches. They generally start with a coarse-grained optimization where mainchain atoms and centroids of side chains are considered, followed by a fine-grained optimization with an all-atom representation of proteins. It is during this coarse-grained phase that fragment-based methods sample intensely the conformational space. If the native-like region is sampled more, the accuracy of the final all-atom predictions may be improved accordingly. In this work we present EdaFold, a new method for fragment-based protein structure prediction based on an Estimation of Distribution Algorithm. Fragment-based approaches build protein models by assembling short fragments from known protein structures. Whereas the probability mass functions over the fragment libraries are uniform in the usual case, we propose an algorithm that learns from previously generated decoys and steers the search toward native-like regions. A comparison with Rosetta AbInitio protocol shows that EdaFold is able to generate models with lower energies and to enhance the percentage of near-native coarse-grained decoys on a benchmark of [Formula: see text] proteins. The best coarse-grained models produced by both methods were refined into all-atom models and used in molecular replacement. All atom decoys produced out of EdaFold's decoy set reach high enough accuracy to solve the crystallographic phase problem by molecular replacement for some test proteins. EdaFold showed a higher success rate in molecular replacement when compared to Rosetta. Our study suggests that improving low resolution coarse-grained decoys allows computational methods to avoid subsequent sampling issues during all-atom refinement and to produce better all-atom models. EdaFold can be downloaded from http://www.riken.jp/zhangiru/software/.     

Dynamic dissociating homo-oligomers and the control of protein function

Homo-oligomeric protein assemblies are known to participate in dynamic association/disassociation equilibria under native conditions, thus creating an equilibrium of assembly states. Such quaternary structure equilibria may be influenced in a physiologically significant manner either by covalent modification or by the non-covalent binding of ligands. This review follows the evolution of ideas about homo-oligomeric equilibria through the 20th and into the 21st centuries and the relationship of these equilibria to allosteric regulation by the non-covalent binding of ligands. A dynamic quaternary structure equilibria is described where the dissociated state can have alternate conformations that cannot reassociate to the original multimer; the alternate conformations dictate assembly to functionally distinct alternate multimers of finite stoichiometry. The functional distinction between different assemblies provides a mechanism for allostery. The requirement for dissociation distinguishes this morpheein model of allosteric regulation from the classical MWC concerted and KNF sequential models. These models are described alongside earlier dissociating allosteric models. The identification of proteins that exist as an equilibrium of diverse native quaternary structure assemblies has the potential to define new targets for allosteric modulation with significant consequences for further understanding and/or controlling protein structure and function. Thus, a rationale for identifying proteins that may use the morpheein model of allostery is presented and a selection of proteins for which published data suggests this mechanism may be operative are listed.     

A novel strategy for NMR resonance assignment and protein structure determination

The quality of protein structures determined by nuclear magnetic resonance (NMR) spectroscopy is contingent on the number and quality of experimentally-derived resonance assignments, distance and angular restraints. Two key features of protein NMR data have posed challenges for the routine and automated structure determination of small to medium sized proteins; (1) spectral resolution – especially of crowded nuclear Overhauser effect spectroscopy (NOESY) spectra, and (2) the reliance on a continuous network of weak scalar couplings as part of most common assignment protocols. In order to facilitate NMR structure determination, we developed a semi-automated strategy that utilizes non-uniform sampling (NUS) and multidimensional decomposition (MDD) for optimal data collection and processing of selected, high resolution multidimensional NMR experiments, combined it with an ABACUS protocol for sequential and side chain resonance assignments, and streamlined this procedure to execute structure and refinement calculations in CYANA and CNS, respectively. Two graphical user interfaces (GUIs) were developed to facilitate efficient analysis and compilation of the data and to guide automated structure determination. This integrated method was implemented and refined on over 30 high quality structures of proteins ranging from 5.5 to 16.5 kDa in size.     

Distance geometry and related methods for protein structure determination from NMR data

Computational tools have been developed in the last few years, to allow a direct determination of protein structures from NMR data. Numerical calculations with simulated and experimental NMR constraints for distances and torsional angles show that data sets available with present NMR techniques carry enough information to determine reliably the global fold of a small protein. The maximum size of a protein for which the direct method can be applied is not limited by the computational tools but rather by the resolution of the two-dimensional spectra. A general estimate of the maximum size would be a molecular weight of about 10,000 (Markley et al. 1984), but parts of larger proteins might be accessible with the method. Effort for improvement of the NMR structures should be concentrated more on the local conformation rather than the global features. The r.m.s. D values for variations of the polypeptide backbone fold are on the order of 1.5-2 A for several of the studied proteins, indicating that the global structure is well determined by the present NMR data and their interpretation. The local structures are sometimes rather poor, with standard deviations for the backbone torsion angles of about 50 degrees. Possible improvements would be stereospecific resonance assignments of individual methylene protons and individual assignments of the methyl groups of the branched side-chains. Accurate estimates of the short-range NOE distance constraints by calibrating the distance constraints, including segmental flexibility effects, and combined use of distance geometry, energy minimization and molecular dynamics calculations, are further tools for improving the structures.     

Multidimensional NMR methods for protein structure determination

Structural studies of proteins are critical for understanding biological processes at the molecular level. Nuclear magnetic resonance (NMR) spectroscopy is a powerful technique for obtaining structural and dynamic information on proteins and protein-ligand complexes. In the present review, methodologies for NMR structure determination of proteins and macromolecular complexes are described. In addition, a number of recent advances that reduce the molecular weight limitations previously imposed on NMR studies of biomolecules are discussed, highlighting applications of these technologies to protein systems studied in our laboratories.     

A sensitive and robust method for obtaining intermolecular NOEs between side chains in large protein complexes

A method for measuring intermolecular NOEs in protein complexes based on asymmetric sample deuteration is described. ¹³C/¹H-I,L,V-methyl, U-²H labeled protein is produced using the biosynthetic precursors [-¹³C]--ketobutyrate and [,-¹³C₂]--ketoisovalerate. The labeled protein is mixed with its unlabeled binding partner and a 3D ¹³C-HMQC-NOESY is recorded, yielding unambiguous intermolecular aromatic/methyl NOEs. A simple synthesis of the biosynthetic precursors via reaction of diethyl oxalate with alkyl Grignard compounds is reported. The method is demonstrated for a 35 kDa heterodimeric protein complex dissolved in a CHAPS micelle. This approach will facilitate the solution structure determination of protein/protein, protein/ligand or protein/nucleic acid complexes.These authors contributed equallyThese authors contributed equally     

A photon-free approach to transmembrane protein structure determination

The structures of membrane proteins are generally solved using samples dissolved in micelles, bicelles, or occasionally phospholipid bilayers using X-ray diffraction or magnetic resonance. Because these are less than perfect mimics of true biological membranes, the structures are often confirmed by evaluating the effects of mutations on the properties of the protein in their native cellular environments. Low-resolution structures are also sometimes generated from the results of site-directed mutagenesis when other structural data are incomplete or not available. Here, we describe a rapid and automated approach to determine structures from data on site-directed mutants for the special case of homo-oligomeric helical bundles. The method uses as input an experimental profile of the effects of mutations on some property of the protein. This profile is then interpreted by assuming that positions that have large effects on structure/function when mutated project toward the center of the oligomeric bundle. Model bundles are generated, and correlation analysis is used to score which structures have inter-subunit C^β distances between adjoining monomers that best correlate with the experimental profile. These structures are then clustered and refined using energy-based minimization methods. For a set of 10 homo-oligomeric TM protein structures ranging from dimers to pentamers, we show that our method predicts structures to within 1-2 Å backbone RMSD relative to X-ray and NMR structures. This level of agreement approaches the precision of NMR structures solved in different membrane mimetics.     

In situ proteolysis for protein crystallization and structure determination

We tested the general applicability of in situ proteolysis to form protein crystals suitable for structure determination by adding a protease (chymotrypsin or trypsin) digestion step to crystallization trials of 55 bacterial and 14 human proteins that had proven recalcitrant to our best efforts at crystallization or structure determination. This is a work in progress; so far we determined structures of 9 bacterial proteins and the human aminoimidazole ribonucleotide synthetase (AIRS) domain.     

A quasi-physical algorithm for the structure optimization in an off-lattice protein model

Introduction Predicting the native structure of a protein from its amino acid sequence is one of the most challeng- ing problems in biophysics and bioinformatics. The difficulty of the problem comes from two aspects. One is the determination of the potential energy func- tion. The effective energy function can generally dis- tinguish the native states from non-native states of protein molecules. The other is that the potential en- ergy landscape of the system can be characterized by a multitu…     

A method for predicting protein structure from sequence

BACKGROUND: The ability to predict the native conformation of a globular protein from its amino-acid sequence is an important unsolved problem of molecular biology. We have previously reported a method in which reduced representations of proteins are folded on a lattice by Monte Carlo simulation, using statistically-derived potentials. When applied to sequences designed to fold into four-helix bundles, this method generated predicted conformations closely resembling the real ones. RESULTS: We now report a hierarchical approach to protein-structure prediction, in which two cycles of the above-mentioned lattice method (the second on a finer lattice) are followed by a full-atom molecular dynamics simulation. The end product of the simulations is thus a full-atom representation of the predicted structure. The application of this procedure to the 60 residue, B domain of staphylococcal protein A predicts a three-helix bundle with a backbone root mean square (rms) deviation of 2.25-3 A from the experimentally determined structure. Further application to a designed, 120 residue monomeric protein, mROP, based on the dimeric ROP protein of Escherichia coli, predicts a left turning, four-helix bundle native state. Although the ultimate assessment of the quality of this prediction awaits the experimental determination of the mROP structure, a comparison of this structure with the set of equivalent residues in the ROP dime- crystal structure indicates that they have a rms deviation of approximately 3.6-4.2 A. CONCLUSION: Thus, for a set of helical proteins that have simple native topologies, the native folds of the proteins can be predicted with reasonable accuracy from their sequences alone. Our approach suggest a direction for future work addressing the protein-folding problem.     

A new Hybrid Monte Carlo algorithm for protein potential function test and structure refinement

A new Hybrid Monte Carlo (HMC) algorithm has been developed to test protein potential functions and, ultimately, refine protein structures. The main principle of this algorithm is, in each cycle, a new trial conformation is generated by carrying out a short period of molecular dynamics (MD) iterations with a set of random parameters (including the MD time step, the number of MD steps, the MD temperature, and the seed for initial MD velocity assignment); then to accept or reject the new conformation on the basis of the Metropolis criterion. The novelty in this paper is that the potential in MD iterations is different from that in the MC step. In the former, it is a molecular mechanics potential, in the latter it is a knowledge-based potential (KBP). Directed by the KBP, the MD iteration is used to search conformational space for realistic conformations with low KBP energy. It circumvents the difficulty in using KBP functions directly in MD simulation, as KBP functions are typically incomplete, and do not always have continuous derivatives required for the calculation of the forces. The new algorithm has been tested in explorations of conformational space. In these test calculations the KBP energy was found to drop below the value for the native conformation, and the correlation between the root mean square deviation (RMSD) and the KBP energy was shown to be different from the test results in other references. At the present time, the algorithm is useful for testing new KBP functions. Furthermore, if a KBP function can be found for which the native conformation has the lowest energy and the energy/RMSD correlation is good, then this new algorithm also will be a tool for refinement of the theory-based structural models.