Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications

The protein folding problem and the notion of NP-completeness and NP-hardness are discussed. A lattice model is suggested to capture the essece of protein folding. For this model we present a proof that finding the lowest free energy conformation belongs to the class of NP-hard problems. The implications of the proof are discussed and we suggest that the natural folding process cannot be considered as a search for the global free energy minimum. However, we suggest an explanation as to why, for many proteins, the native functional conformation maycoincide with the lowest free energy conformation.     

Heterodimerization of the Entamoeba histolytica EhCPADH virulence complex through molecular dynamics and protein–protein docking

EhCPADH is a protein complex involved in the virulence of Entamoeba histolytica, the protozoan responsible for human amebiasis. It is formed by the EhCP112 cysteine protease and the EhADH adhesin. To explore the molecular basis of the complex formation, three-dimensional models were built for both proteins and molecular dynamics simulations (MDS) and docking calculations were performed. Results predicted that the pEhCP112 proenzyme and the mEhCP112 mature enzyme were globular and peripheral membrane proteins. Interestingly, in pEhCP112, the propeptide appeared hiding the catalytic site (C167, H329, N348); while in mEhCP112, this site was exposed and its residues were found structurally closer than in pEhCP112. EhADH emerged as an extended peripheral membrane protein with high fluctuation in Bro1 and V shape domains. 500 ns-long MDS and protein–protein docking predictions evidenced different heterodimeric complexes with the lowest free energy. pEhCP112 interacted with EhADH by the propeptide and C-terminal regions and mEhCP112 by the C-terminal through hydrogen bonds. In contrast, EhADH bound to mEhCP112 by 442–479 residues, adjacent to the target cell-adherence region (480–600 residues), and by the Bro1 domain (9–349 residues). Calculations of the effective binding free energy and per residue free energy decomposition showed that EhADH binds to mEhCP112 with a higher binding energy than to pEhCP112, mainly through van der Waals interactions and the nonpolar part of solvation energy. The EhADH and EhCP112 structural relationship was validated in trophozoites by immunofluorescence, TEM, and immunoprecipitation assays. Experimental findings fair agreed with in silico results.     

Energetics of permeation of thin lipid membranes by ions

The energy of an ion in a thin hydrocarbon membrane relative to its energy in a bulk aqueous phase is considered in terms of the electrostatic and surface components that may be expected to be involved. Except when diffusion activation energies are large compared to partition free energies, the latter will control permeation rate and the state of an ion having the lowest partition energy will be critical for its permeability. This minimum is found when an ion is surrounded with a thin layer of water. All ions of the same charge will tend to be at their lowest state in a sphere of water of the same size. It is concluded, therefore, that all ions of a given charge will have about the same permeability in lipid membranes.     

Revolutions in RNA secondary structure prediction

RNA structure formation is hierarchical and, therefore, secondary structure, the sum of canonical base-pairs, can generally be predicted without knowledge of the three-dimensional structure. Secondary structure prediction algorithms evolved from predicting a single, lowest free energy structure to their current state where statistics can be determined from the thermodynamic ensemble. This article reviews the free energy minimization technique and the salient revolutions in the dynamic programming algorithm methods for secondary structure prediction. Emphasis is placed on highlighting the recently developed method, which statistically samples structures from the complete Boltzmann ensemble.     

A molecular dynamics study of a miRNA:mRNA interaction

In this paper we present a methodology to evaluate the binding free energy of a miRNA:mRNA complex through molecular dynamics (MD)–thermodynamic integration (TI) simulations. We applied our method to the Caenorhabditis elegans let-7 miRNA:lin-41 mRNA complex—a validated miRNA:mRNA interaction—in order to estimate the energetic stability of the structure. To make the miRNA:mRNA simulation possible and realistic, the methodology introduces specific solutions to overcome some of the general challenges of nucleic acid simulations and binding free energy computations that have been discussed widely in many previous research reports. The main features of the proposed methodology are: (1) positioning of the restraints imposed on the simulations in order to guarantee complex stability; (2) optimal sampling of the phase space to achieve satisfactory accuracy in the binding energy value; (3) determination of a suitable trade-off between computational costs and accuracy of binding free energy computation by the assessment of the scalability characteristics of the parallel simulations required for the TI. The experiments carried out demonstrate that MD simulations are a viable strategy for the study of miRNA binding characteristics, opening the way to the development of new computational target prediction methods based on three-dimensional structure information.     

Searching for the Pareto frontier in multi-objective protein design

The goal of protein engineering and design is to identify sequences that adopt three-dimensional structures of desired function. Often, this is treated as a single-objective optimization problem, identifying the sequence–structure solution with the lowest computed free energy of folding. However, many design problems are multi-state, multi-specificity, or otherwise require concurrent optimization of multiple objectives. There may be tradeoffs among objectives, where improving one feature requires compromising another. The challenge lies in determining solutions that are part of the Pareto optimal set—designs where no further improvement can be achieved in any of the objectives without degrading one of the others. Pareto optimality problems are found in all areas of study, from economics to engineering to biology, and computational methods have been developed specifically to identify the Pareto frontier. We review progress in multi-objective protein design, the development of Pareto optimization methods, and present a specific case study using multi-objective optimization methods to model the tradeoff between three parameters, stability, specificity, and complexity, of a set of interacting synthetic collagen peptides.     

On the Spectrum of Prebiotic Chemical Systems

We reexamine Eigen’s paradox using the asymptotic limit theorems of information theory. Applying the homology between information source uncertainty and free energy density, under rate distortion constraints, the error catastrophe emerges as the lowest energy state for simple prebiotic systems without error correction. Invoking the usual compartmentalization – i.e., ‘vesicles’ – and using a Red Queen argument, suggests that information crosstalk between two or more properly interacting structures can initiate a coevolutionary dynamic having at least two quasi-stable states. The first is a low energy realm near the error threshold, and, depending on available energy, the second can approach zero error as a limit. A large deviations argument produces jet-like global transitions which, over sufficient time, may enable shifts between the many quasi-stable modes available to more complicated structures, ‘locking in’ to some subset of the various possible low error rate chemical systems, which become subject to development by selection and chance extinction. Energy availability, according to the model, is thus a powerful necessary condition for low error rate replication, suggesting that some fundamental prebiotic ecosystem transformation entrained reproductive fidelity. This work, then, supports speculation that our RNA/DNA world may indeed be only the chance result of a very broad prebiotic evolutionary phenomenon. Processes in vitro, or ex planeta, might have other outcomes.     

Quinary interactions with an unfolded state ensemble

Anfinsen's thermodynamic hypothesis states that the native three‐dimensional fold of a protein represents the structure with the lowest Gibbs free energy. Changes in the free energy of denaturation can arise from changes to the folded state, the unfolded state, or both. It has been recently recognized that quinary interactions, transient contacts that take place only in cells, can modulate protein stability through interactions involving the folded state. Here we show that the cellular environment can also remodel the unfolded state ensemble.     

Prediction of the mutation-induced change in thermodynamic stabilities of membrane proteins from free energy simulations

Comparative protein structure modeling and free energy perturbation simulation have been applied in a consecutive manner to investigate the mutation-induced stabilization of membrane proteins (MPs) in aqueous solution without knowledge of their three-dimensional structures. The calculated difference in protein solvation free energy between the wild type and a mutant compares well with their relative thermodynamic stabilities in solution. For monomeric MPs, a mutant reveals a higher stability than the wild type if the calculated solvation free energy indicates a favorable change. On the contrary, for oligomeric MPs the stability of a mutant increases as the solvation free energy of a mutated monomer becomes less favorable, indicating that the oligomeric MP mutant would be stabilized in solution due to the reduced desolvation cost for oligomerization. The present computational strategy is expected to find its way as a useful tool for assessing the relative stability of a mutant MP with respect to its wild type in solution.     

Spread of information through a population with socio-structural bias: I. Assumption of transitivity

A previously derived iteration formula for a random net was applied to some data on the spread of information through a population. It was found that if the axon density (the only free parameter in the formula) is determined by the first pair of experimental values, the predicted spread is much more rapid than the observed one. If the successive values of the “apparent axon density” are calculated from the successive experimental values, it is noticed that this quantity at first suffers a sharp drop from an initial high value to its lowest value and then gradually “recovers”. An attempt is made to account for this behavior of the apparent axon density in terms of the “assumption of transitivity”, based on a certain socio-structural bias, namely, that the likely contacts of two individuals who themselves have been in contact are expected to be strongly overlapping. The assumption of transitivity leads to a drop in the apparent axon density from an arbitrary initial value to the vicinity of unity (if the actual axon density is not too small). However, the “recovery” is not accounted for, and thus the predicted spread turns out to beslower than the observed.     

A new tripodal poly-imine indole-containing ligand: Synthesis, complexation, spectroscopic and theoretical studies

A novel flexible tripodal ligand derived from 3-methylindole, (“InTREN” L), and its mononuclear Zn(II), Cu(II), Ni(II), Hg(II) and Pd(II) complexes are described. All compounds gave analytically pure solid samples. Characterisation of the compounds was accomplished by ¹H NMR, IR and absorption spectroscopies, matrix-assisted laser desorption/ionization time-of-flight mass spectrometry (MALDI-TOF-MS) and elemental analysis and their geometry optimized using density functional theory (DFT).Time-dependent-density functional theory (TD-DFT) calculations have been used to assign the lowest energy absorption bands of the free ligand and the Zn(II) complex. The system is a very good candidate for in situ recognition/coordination effects by MALDI-TOF-MS spectrometry and absorption spectroscopy. The presence of three indole groups in InTREN opens up the possibility to synthesize new three-dimensional self-assembly supramolecular structures.     

The steady state kinetics of some biological systems: III. Thermodynamic aspects

Some thermodynamic aspects of steady systems are considered. The time rates of changes, “flux”, of various thermodynamic quantities are formulated. In particular the free energy flux in the steady state, the difference between the free energy flux in the steady and time dependent states and the change in free energy flux upon transition between steady states are discussed. Equations are derived which exhibit the formal similarities and differences between the free energy flux and the conventional free energy change. The temperature dependence of the steady state rate is examined and conditions for “mastery” by a single step discussed. A brief discussion of the role ofrate in the coupling of exergonic and endergonic reactions is given.     

Modeling of the pH-and the temperature-dependant deviations of the free to total PSA (Prostate Specific Antigen) ratios for clinical predictability of prostate cancer and benign prostate hyperplasia

Both the free and total PSA had been reported to be pH-and temperature-labile. We have introduced two submodels to describe the decay of PSAs. The overall pH-dependent decay model (OPDDM) describes the ratio of free to true scientific total PSA including both the immunoreactive and the nonimmunoreactive. We elucidated four pH-dependent formation constants for the free PSA with hydronium ion [H⁺], the PSA-ACT (α ₁-antichymotrypsin), the PSA-API (α ₁-protease inhibitor), and the nonimmunoreactive PSA-AMG (α ₂-macroglobulin) complexes, respectively, to model the stability of the free to total PSA ratios. Model simulation indicated a highly pH-sensitive behavior of the free to total PSA ratios. While the temperature dependent decay model (TDDM) indicated that kinetically, free PSA revealed the most rapid decay rates due to its low activation energy, total PSA was shown to be relatively more thermally stable. The decay of all PSA species could be more accelerated at temperatures higher than −4°C, while it is kept below −70°C throughout. It is thus recommended to use the preparation fresh (better within 8 h) after venipuncture. And it is advisable that all the results are advised to perform corrections for each determination by calculating back to the data at the original physiological pH prior to clinical diagnostic interpretation.     

Progress in protein-protein docking: atomic resolution predictions in the CAPRI experiment using RosettaDock with an improved treatment of side-chain flexibility

RosettaDock uses real-space Monte Carlo minimization (MCM) on both rigid-body and side-chain degrees of freedom to identify the lowest free energy docked arrangement of 2 protein structures. An improved version of the method that uses gradient-based minimization for off-rotamer side-chain optimization and includes information from unbound structures was used to create predictions for Rounds 4 and 5 of CAPRI. First, large numbers of independent MCM trajectories were carried out and the lowest free energy docked configurations identified. Second, new trajectories were started from these lowest energy structures to thoroughly sample the surrounding conformation space, and the lowest energy configurations were submitted as predictions. For all cases in which there were no significant backbone conformational changes, a small number of very low-energy configurations were identified in the first, global search and subsequently found to be close to the center of the basin of attraction in the free energy landscape in the second, local search. Following the release of the experimental coordinates, it was found that the centers of these free energy minima were remarkably close to the native structures in not only the rigid-body orientation but also the detailed conformations of the side-chains. Out of 8 targets, the lowest energy models had interface root-mean-square deviations (RMSDs) less than 1.1 A from the correct structures for 6 targets, and interface RMSDs less than 0.4 A for 3 targets. The predictions were top submissions to CAPRI for Targets 11, 12, 14, 15, and 19. The close correspondence of the lowest free energy structures found in our searches to the experimental structures suggests that our free energy function is a reasonable representation of the physical chemistry, and that the real space search with full side-chain flexibility to some extent solves the protein-protein docking problem in the absence of significant backbone conformational changes. On the other hand, the approach fails when there are significant backbone conformational changes as the steric complementarity of the 2 proteins cannot be modeled without incorporating backbone flexibility, and this is the major goal of our current work.     

Nonadditive Interactions in Protein Folding: The Zipper Model of Cytochrome <Emphasis Type="Italic">c</Emphasis>

Hydrogen exchange experiments (Krishna et al. in J. Mol. Biol. 359:1410, 2006) reveal that folding–unfolding of cytochrome c occurs along a defined pathway in a sequential, stepwise manner. The simplified zipper-like model involving nonadditive coupling is proposed to describe the classical “on pathway” folding–unfolding behavior of cytochrome c. Using free energy factors extracted from HX experiments, the model can predict and explain cytochrome c behavior in spectroscopy studies looking at folding equilibria and kinetics. The implications of the proposed model are discussed for such problems as classical pathway vs. energy landscape conceptions, structure and function of a native fold, and interplay of secondary and tertiary interactions.     

Does Flory–Huggins theory help in interpreting solute partitioning experiments?

The development of Flory–Huggins (FH) theory is reviewed, particularly with regard to the molecular significance of the interaction parameter that scales the contact interaction of solute and solvent. The chemical potential given by FH theory for an “idealute” solute is then compared with that provided by a more general, statistical thermodynamic approach. It is found that the FH contact term does not directly correspond to the solvation free energy. The significance of this result for the interpretation of free energies of transfer of a solute from one solvent to another is examined. It is shown that neither the earlier recommended standard free energy change for the process (using the infinitely dilute reference state, mole fraction units) nor the recently recommended FH-corrected standard free energy change provides the solvation energy desired. Instead, the standard free energy using the infinitely dilute reference state and molarity units, as long advocated by Ben-Naim, provides the desired solvation free energy. Correction of extant values, based on mole fraction units, is easily made. However, application of such results to problems of protein folding is not straightforward. © 1994 John Wiley & Sons, Inc.     

Energetics of superhelicity and of B-Z transitions in superhelical DNA

The linking difference, α, imposed upon a superhelically constrained DNA molecule must be partitioned between twisting and bending deformations. Transitions to alternative secondary structures can occur at susceptible sites, altering the local molecular twist by an amount ΔTw _trans. That part of the linking difference not accommodated in this way, the residual linking difference α_res, must be manifested as smooth torsional and flexural deformations of secondary structure. The competition among the alternative ways of accommodating the imposed linking difference α determines a stressed equilibrium state. The superhelical free energy,G(α), is the excess free energy of the equilibrium state at linking difference α above that of the relaxed state under identical conditions. In this paper a method is described by which the free energies associated both to linking,G(α), and to residual linking differences can be determined from data on superhelical conformational transitions. The application of this approach to previously published experimental data on the B-Z transition suggests that the free energy associated with α_res is about 30% larger at substantial superhelicities than it is near the relaxed state. At the onset of transition the functional form ofG(α) is shown to change in a manner dependent upon the length of the Z-susceptible site.     

Does conformational free energy distinguish loop conformations in proteins?

Limitations in protein homology modeling often arise from the inability to adequately model loops. In this paper we focus on the selection of loop conformations. We present a complete computational treatment that allows the screening of loop conformations to identify those that best fit a molecular model. The stability of a loop in a protein is evaluated via computations of conformational free energies in solution, i.e., the free energy difference between the reference structure and the modeled one. A thermodynamic cycle is used for calculation of the conformational free energy, in which the total free energy of the reference state (i.e., gas phase) is the CHARMm potential energy. The electrostatic contribution of the solvation free energy is obtained from solving the finite-difference Poisson-Boltzmann equation. The nonpolar contribution is based on a surface area-based expression. We applied this computational scheme to a simple but well-characterized system, the antibody hypervariable loop (complementarity-determining region, CDR). Instead of creating loop conformations, we generated a database of loops extracted from high-resolution crystal structures of proteins, which display geometrical similarities with antibody CDRs. We inserted loops from our database into a framework of an antibody; then we calculated the conformational free energies of each loop. Results show that we successfully identified loops with a "reference-like" CDR geometry, with the lowest conformational free energy in gas phase only. Surprisingly, the solvation energy term plays a confusing role, sometimes discriminating "reference-like" CDR geometry and many times allowing "non-reference-like" conformations to have the lowest conformational free energies (for short loops). Most "reference-like" loop conformations are separated from others by a gap in the gas phase conformational free energy scale. Naturally, loops from antibody molecules are found to be the best models for long CDRs (> or = 6 residues), mainly because of a better packing of backbone atoms into the framework of the antibody model.     

Prediction of geometrically feasible three-dimensional structures of pseudoknotted RNA through free energy estimation

Accurate free energy estimation is essential for RNA structure prediction. The widely used Turner''s energy model works well for nested structures. For pseudoknotted RNAs, however, there is no effective rule for estimation of loop entropy and free energy. In this work we present a new free energy estimation method, termed the pseudoknot predictor in three-dimensional space (pk3D), which goes beyond Turner''s model. Our approach treats nested and pseudoknotted structures alike in one unifying physical framework, regardless of how complex the RNA structures are. We first test the ability of pk3D in selecting native structures from a large number of decoys for a set of 43 pseudoknotted RNA molecules, with lengths ranging from 23 to 113. We find that pk3D performs slightly better than the Dirks and Pierce extension of Turner''s rule. We then test pk3D for blind secondary structure prediction, and find that pk3D gives the best sensitivity and comparable positive predictive value (related to specificity) in predicting pseudoknotted RNA secondary structures, when compared with other methods. A unique strength of pk3D is that it also generates spatial arrangement of structural elements of the RNA molecule. Comparison of three-dimensional structures predicted by pk3D with the native structure measured by nuclear magnetic resonance or X-ray experiments shows that the predicted spatial arrangement of stems and loops is often similar to that found in the native structure. These close-to-native structures can be used as starting points for further refinement to derive accurate three-dimensional structures of RNA molecules, including those with pseudoknots.     

The energy computation paradox and ab initio protein folding

The routine prediction of three-dimensional protein structure from sequence remains a challenge in computational biochemistry. It has been intuited that calculated energies from physics-based scoring functions are able to distinguish native from nonnative folds based on previous performance with small proteins and that conformational sampling is the fundamental bottleneck to successful folding. We demonstrate that as protein size increases, errors in the computed energies become a significant problem. We show, by using error probability density functions, that physics-based scores contain significant systematic and random errors relative to accurate reference energies. These errors propagate throughout an entire protein and distort its energy landscape to such an extent that modern scoring functions should have little chance of success in finding the free energy minima of large proteins. Nonetheless, by understanding errors in physics-based score functions, they can be reduced in a post-hoc manner, improving accuracy in energy computation and fold discrimination.