Search

International audience; Coarse-grained normal mode analyses of protein dynamics rely on the idea that the geometry of a protein structure contains enough information for computing its fluctuations around its equilibrium conformation. This geometry is captured in the form of an elastic network (EN), namely a network of edges between its residues. The normal modes of a protein are then identified with the normal modes of its EN. Different approaches have been proposed to construct ENs, focusing on the choice of the edges that they are comprised of, and on their parameterizations by the force constants associated with those edges. Here we propose new tools to guide choices on these two facets of EN. We study first different geometric models for ENs. We compare cutoff-based ENs, whose edges have lengths that are smaller than a cutoff distance, with Delaunay-based ENs and find that the latter provide better representations of the geometry of protein structures. We then derive an analytical method for the parameterization of the EN such that its dynamics leads to atomic fluctuations that agree with experimental B-factors. To limit overfitting, we attach a parameter referred to as flexibility constant to each atom instead of to each edge in the EN. The parameterization is expressed as a non-linear optimization problem whose parameters describe both rigid-body and internal motions. We show that this parameterization leads to improved ENs, whose dynamics mimic MD simulations better than ENs with uniform force constants, and reduces the number of normal modes needed to reproduce functional conformational changes.

International audience; While structural data on viruses are more and more common, information on their dynamics is much harder to obtain as those viruses form very large molecular complexes. In this paper, we propose a new method for computing the coarse-grained normal modes of such supra-molecules, NormalGo. A new formalism is developed to represent the Hessian of a quadratic potential using tensor products. This formalism is applied to the Tirion elastic potential, as well as to a Gō like potential. When combined with a fast method for computing a select set of eigenpairs of the Hessian, this new formalism enables the computation of thousands of normal modes of a full viral shell with more than one hundred thousand atoms in less than 2 h on a standard desktop computer. We then compare the two coarse-grained potentials. We show that, despite significant differences in their formulations, the Tirion and the Gō like potentials capture very similar dynamics characteristics of the molecule under study. However, we find that the Gō like potential should be preferred as it leads to less local deformations in the structure of the molecule during normal mode dynamics. Finally, we use NormalGo to characterize the structural transitions that occur when FAB fragments bind to the icosahedral outer shell of serotype 3 of the Dengue virus. We have identified residues at the surface of the outer shell that are important for the transition between the FAB-free and FAB-bound conformations, and therefore potentially useful for the design of antibodies to Dengue viruses.

We present a new method to sample conditioned trajectories of a system evolving under Langevin dynamics, based on Brownian bridges. The trajectories are conditioned to end at a certain point (or in a certain region) in space. The bridge equations can be recast exactly in the form of a non linear stochastic integro-differential equation. This equation can be very well approximated when the trajectories are closely bundled together in space, i.e. at low temperature, or for transition paths. The approximate equation can be solved iteratively, using a fixed point method. We discuss how to choose the initial trajectories and show some examples of the performance of this method on some simple problems. The method allows to generate conditioned trajectories with a high accuracy., Comment: 9 pages, 3 figures

International audience; Optimal transport (OT) has become a discipline by itself that offers solutions to a wide range of theoretical problems in probability and mathematics with applications in several applied fields such as imaging sciences, machine learning, and in data sciences in general. The traditional OT problem suffers from a severe limitation: its balance condition imposes that the two distributions to be compared be normalized and have the same total mass. However, it is important for many applications to be able to relax this constraint and allow for mass creation and/or destruction. This is true, for example, in all problems requiring partial matching. In this paper, we propose an approach to solving a generalized version of the OT problem, which we refer to as the discrete variable-mass optimal-transport (VMOT) problem, using techniques adapted from statistical physics. Our first contribution is to fully describe this formalism, including all the proofs of its main claims. In particular, we derive a strongly concave effective free-energy function that captures the constraints of the VMOT problem at a finite temperature. From its maximum we derive a weak distance (i.e., a divergence) between possibly unbalanced distribution functions. The temperature-dependent OT distance decreases monotonically to the standard variable-mass OT distance, providing a robust framework for temperature annealing. Our second contribution is to show that the implementation of this formalism has the same properties as the regularized OT algorithms in time complexity, making it a competitive approach to solving the VMOT problem. We illustrate applications of the framework to the problem of partial two- and three-dimensional shape-matching problems.

We present an extension of the Poisson-Boltzmann model in which the solute of interest is immersed in an assembly of self-orienting Langevin water dipoles, anions, cations, and hydrophobic molecules, all of variable densities. Interactions between charges are controlled by electrostatics, while hydrophobic interactions are modeled with a Yukawa potential. We impose steric constraints by assuming that the system is represented on a cubic lattice. We also assume incompressibility, i.e. all sites of the lattice are occupied. This model, which we refer to as the Hydrophobic Dipolar Poisson Boltzmann Langevin (HDPBL) model, leads to a system of two equations whose solutions give the water dipole, salt, and hydrophobic molecule densities, all of them in the presence of the others in a self-consistent way. We use those to study the organization of the ions, co-solvent and solvent molecules around proteins. In particular, peaks of densities are expected to reveal, simultaneously, the presence of compatible binding sites of different kinds on a protein. We have tested and validated the ability of HDPBL to detect pockets in proteins that bind to hydrophobic ligands, polar ligands and charged small probes as well as to characterize the environment of membrane proteins., Comment: 45 pages, 6 figures

The linear assignment problem is a fundamental problem in combinatorial optimization with a wide range of applications, from operational research to data science. It consists of assigning ``agents'' to ``tasks'' on a one-to-one basis, while minimizing the total cost associated with the assignment. While many exact algorithms have been developed to identify such an optimal assignment, most of these methods are computationally prohibitive for large size problems. In this paper, we propose an alternative approach to solving the assignment problem using techniques adapted from statistical physics. Our first contribution is to fully describe this formalism, including all the proofs of its main claims. In particular we derive a strongly concave effective free-energy function that captures the constraints of the assignment problem at a finite temperature. We prove that this free energy decreases monotonically as a function of $\ensuremath{\beta}$, the inverse of temperature, to the optimal assignment cost, providing a robust framework for temperature annealing. We prove also that for large enough $\ensuremath{\beta}$ values the exact solution to the generic assignment problem can be derived using simple roundoff to the nearest integer of the elements of the computed assignment matrix. Our second contribution is to derive a provably convergent method to handle degenerate assignment problems, with a characterization of those problems. We describe computer implementations of our framework that are optimized for parallel architectures, one based on CPU, the other based on GPU. We show that the latter enables solving large assignment problems (of the orders of a few 10 000s) in computing clock times of the orders of minutes.

We present a new method to compare the shapes of genus-zero surfaces by introducing a measure of mutual stretching, the symmetric distortion energy. Given a pair of genus-zero surfaces, we establish the existence of a conformal diffeomorphism that minimizes this energy. We then prove that the energies of the minimizing diffeomorphisms produce a metric on the space of genus-zero Riemannian surfaces. This metric and the corresponding optimal diffeomorphisms are shown to have properties that are highly desirable for applications.

The pentameric ligand-gated ion channel (pLGIC) from Gloeobacter violaceus (GLIC) has provided insightful structure–function views on the permeation process and the allosteric regulation of the pLGICs family. However, GLIC is activated by pH instead of a neurotransmitter and a clear picture for the gating transition driven by protons is still lacking. We used an electrostatics-based (finite difference Poisson–Boltzmann/Debye–Hückel) method to predict the acidities of all aspartic and glutamic residues in GLIC, both in its active and closed-channel states. Those residues with a predicted pK a close to the experimental pH 50 were individually replaced by alanine and the resulting variant receptors were titrated by ATR/FTIR spectroscopy. E35, located in front of loop F far away from the orthosteric site, appears as the key proton sensor with a measured individual pK a at 5.8. In the GLIC open conformation, E35 is connected through a water-mediated hydrogen-bond network first to the highly conserved electrostatic triad R192-D122-D32 and then to Y197-Y119-K248, both located at the extracellular domain–transmembrane domain interface. The second triad controls a cluster of hydrophobic side chains from the M2-M3 loop that is remodeled during the gating transition. We solved 12 crystal structures of GLIC mutants, 6 of them being trapped in an agonist-bound but nonconductive conformation. Combined with previous data, this reveals two branches of a continuous network originating from E35 that reach, independently, the middle transmembrane region of two adjacent subunits. We conclude that GLIC’s gating proceeds by making use of loop F, already known as an allosteric site in other pLGICs, instead of the classic orthosteric site.

Residues in proteins that are in close spatial proximity are more prone to covariate as their interactions are likely to be preserved due to structural and evolutionary constraints. If we can detect and quantify such covariation, physical contacts may then be predicted in the structure of a protein solely from the sequences that decorate it. To carry out such predictions, and following the work of others, we have implemented a multivariate Gaussian model to analyze correlation in multiple sequence alignments. We have explored and tested several numerical encodings of amino acids within this model. We have shown that 1D encodings based on amino acid biochemical and biophysical properties, as well as higher dimensional encodings computed from the principal components of experimentally derived mutation/substitution matrices, do not perform as well as a simple twenty dimensional encoding with each amino acid represented with a vector of one along its own dimension and zero elsewhere. The optimum obtained from representations based on substitution matrices is reached by using 10 to 12 principal components, the corresponding performance is less than the performance obtained with the 20-dimensional binary encoding. We highlight also the importance of the prior when constructing the multivariate Gaussian model of a multiple sequence alignment.

RNA SHAPE experiments have become important and successful sources of information for RNA structure prediction. In such experiments, chemical reagents are used to probe RNA backbone flexibility at the nucleotide level, which in turn provides information on base pairing and therefore secondary structure. Little is known, however, about the statistics of such SHAPE data. In this work, we explore different representations of noise in SHAPE data and propose a statistically sound framework for extracting reliable reactivity information from multiple SHAPE replicates. Our analyses of RNA SHAPE experiments underscore that a normal noise model is not adequate to represent their data. We propose instead a log-normal representation of noise and discuss its relevance. Under this assumption, we observe that processing simulated SHAPE data by directly averaging different replicates leads to bias. Such bias can be reduced by analyzing the data following a log transformation, either by log-averaging or Kalman filtering. Application of Kalman filtering has the additional advantage that a prior on the nucleotide reactivities can be introduced. We show that the performance of Kalman filtering is then directly dependent on the quality of that prior. We conclude the paper with guidelines on signal processing of RNA SHAPE data.

Background Alignment-free methods for comparing protein sequences have proved to be viable alternatives to approaches that first rely on an alignment of the sequences to be compared. Much work however need to be done before those methods provide reliable fold recognition for proteins whose sequences share little similarity. We have recently proposed an alignment-free method based on the concept of string kernels, SeqKernel (Nojoomi and Koehl, BMC Bioinformatics, 2017, 18:137). In this previous study, we have shown that while Seqkernel performs better than standard alignment-based methods, its applications are potentially limited, because of biases due mostly to sequence length effects. Methods In this study, we propose improvements to SeqKernel that follows two directions. First, we developed a weighted version of the kernel, WSeqKernel. Second, we expand the concept of string kernels into a novel framework for deriving information on amino acids from protein sequences. Results Using a dataset that only contains remote homologs, we have shown that WSeqKernel performs remarkably well in fold recognition experiments. We have shown that with the appropriate weighting scheme, we can remove the length effects on the kernel values. WSeqKernel, just like any alignment-based sequence comparison method, depends on a substitution matrix. We have shown that this matrix can be optimized so that sequence similarity scores correlate well with structure similarity scores. Starting from no information on amino acid similarity, we have shown that we can derive a scoring matrix that echoes the physico-chemical properties of amino acids. Conclusion We have made progress in characterizing and parametrizing string kernels as alignment-based methods for comparing protein sequences, and we have shown that they provide a framework for extracting sequence information from structure. Electronic supplementary material The online version of this article (doi:10.1186/s12859-017-1795-5) contains supplementary material, which is available to authorized users.

Despite years of effort, the problem of predicting the conformations of protein side chains remains a subject of inquiry. This problem has three major issues, namely defining the conformations that a side chain may adopt within a protein, developing a sampling procedure for generating possible side-chain packings, and defining a scoring function that can rank these possible packings. To solve the former of these issues, most procedures rely on a rotamer library derived from databases of known protein structures. We introduce an alternative method that is free of statistics. We begin with a rotamer library that is based only on stereochemical considerations; this rotamer library is then optimized independently for each protein under study. We show that this optimization step restores the diversity of conformations observed in native proteins. We combine this protein-dependent rotamer library (PDRL) method with the self-consistent mean field (SCMF) sampling approach and a physics-based scoring function into a new side-chain prediction method, SCMF-PDRL. Using two large test sets of 831 and 378 proteins, respectively, we show that this new method compares favorably with competing methods such as SCAP, OPUS-Rota, and SCWRL4 for energy-minimized structures.

Phycocyanobilin:ferredoxin oxidoreductase (PcyA) catalyzes the proton-coupled four-electron reduction of biliverdin IXa's two vinyl groups to produce phycocyanobilin, an essential chromophore for phytochromes, cyanobacteriochromes and phycobiliproteins. Previous site directed mutagenesis studies indicated that the fully conserved residue His74 plays a critical role in the H-bonding network that permits proton transfer. Here, we exploit X-ray crystallography, enzymology and molecular dynamics simulations to understand the functional role of this invariant histidine. The structures of the H74A, H74E and H74Q variants of PcyA reveal that a ''conserved'' buried water molecule that bridges His74 and catalytically essential His88 is not required for activity. Despite distinct conformations of Glu74 and Gln74 in the H74E and H74Q variants, both retain reasonable activity while the H74A variant is inactive, suggesting smaller residues may generate cavities that increase flexibility, thereby reducing enzymatic activity. Molecular dynamic simulations further reveal that the crucial active site residue Asp105 is more dynamic in H74A compared to wild-type PcyA and the two other His74 variants, supporting the conclusion that the Ala74 mutation has increased the flexibility of the active site. © 2013 Elsevier Inc. All rights reserved.

It is well known that protein fold recognition can be greatly improved if models for the underlying evolution history of the folds are taken into account. The improvement, however, exists only if such evolutionary information is available. To circumvent this limitation for protein families that only have a small number of representatives in current sequence databases, we follow an alternate approach in which the benefits of including evolutionary information can be recreated by using sequences generated by computational protein design algorithms. We explore this strategy on a large database of protein templates with 1747 members from different protein families. An automated method is used to design sequences for these templates. We use the backbones from the experimental structures as fixed templates, thread sequences on these backbones using a self-consistent mean field approach, and score the fitness of the corresponding models using a semi-empirical physical potential. Sequences designed for one template are translated into a hidden Markov model-based profile. We describe the implementation of this method, the optimization of its parameters, and its performance. When the native sequences of the protein templates were tested against the library of these profiles, the class, fold, and family memberships of a large majority (>90%) of these sequences were correctly recognized for an E-value threshold of 1. In contrast, when homologous sequences were tested against the same library, a much smaller fraction (35%) of sequences were recognized; The structural classification of protein families corresponding to these sequences, however, are correctly recognized (with an accuracy of >88%). Proteins 2013; © 2013 Wiley Periodicals, Inc.

Protein structure prediction techniques proceed in two steps, namely the generation of many structural models for the protein of interest, followed by an evaluation of all these models to identify those that are native-like. In theory, the second step is easy, as native structures correspond to minima of their free energy surfaces. It is well known however that the situation is more complicated as the current force fields used for molecular simulations fail to recognize native states from misfolded structures. In an attempt to solve this problem, we follow an alternate approach and derive a new potential from geometric knowledge extracted from native and misfolded conformers of protein structures. This new potential, Metric Protein Potential (MPP), has two main features that are key to its success. Firstly, it is composite in that it includes local and nonlocal geometric information on proteins. At the short range level, it captures and quantifies the mapping between the sequences and structures of short (7-mer) fragments of protein backbones through the introduction of a new local energy term. The local energy term is then augmented with a nonlocal residue-based pairwise potential, and a solvent potential. Secondly, it is optimized to yield a maximized correlation between the energy of a structural model and its root mean square (RMS) to the native structure of the corresponding protein. We have shown that MPP yields high correlation values between RMS and energy and that it is able to retrieve the native structure of a protein from a set of high-resolution decoys. Proteins 2013. © 2012 Wiley Periodicals, Inc.

Computational protein sequence design is the rational design based on computer simulation of new protein molecules to fold to target three-dimensional structures, with the ultimate goal of designing novel functions. It requires a good understanding of the thermodynamic equilibrium properties of the protein of interest. Here, we consider the contribution of the solvent to the stability of the protein. We describe implicit solvent models, focusing on approximations of their nonpolar components using geometric potentials. We consider the surface area (SA) model in which the nonpolar solvation free energy is expressed as a sum of the contributions of all atoms, assumed to be proportional to their accessible surface areas (ASAs). We briefly review existing numerical and analytical approaches that compute the ASA. We describe in more detail the alpha shape theory as it provides a unifying mathematical framework that enables the analytical calculations of the surface area of a macromolecule represented as a union of balls.

Background The amino acid sequence of a protein is the blueprint from which its structure and ultimately function can be derived. Therefore, sequence comparison methods remain essential for the determination of similarity between proteins. Traditional approaches for comparing two protein sequences begin with strings of letters (amino acids) that represent the sequences, before generating textual alignments between these strings and providing scores for each alignment. When the similitude between the two protein sequences to be compared is low however, the quality of the corresponding sequence alignment is usually poor, leading to poor performance for the recognition of similarity. Results In this study, we develop an alignment free alternative to these methods that is based on the concept of string kernels. Starting from recently proposed kernels on the discrete space of protein sequences (Shen et al, Found. Comput. Math., 2013,14:951-984), we introduce our own version, SeqKernel. Its implementation depends on two parameters, a coefficient that tunes the substitution matrix and the maximum length of k-mers that it includes. We provide an exhaustive analysis of the impacts of these two parameters on the performance of SeqKernel for fold recognition. We show that with the right choice of parameters, use of the SeqKernel similarity measure improves fold recognition compared to the use of traditional alignment-based methods. We illustrate the application of SeqKernel to inferring phylogeny on RNA polymerases and show that it performs as well as methods based on multiple sequence alignments. Conclusion We have presented and characterized a new alignment free method based on a mathematical kernel for scoring the similarity of protein sequences. We discuss possible improvements of this method, as well as an extension of its applications to other modeling methods that rely on sequence comparison.

A new exact algorithm is proposed to compute the 3D geometric moments of a homogeneous shape defined by an unstructured triangulation of its surface. This algorithm relies on the analytical integration of the moments on tetrahedra defined by the surface triangles and a central point and on a set of recurrent relationships between the corresponding integrals, and achieves linear running time complexities with respect to the number of triangles in the surface mesh and with respect to the number of moments that are computed. This effectively reduces the complexity for computing moments up to order N from N^6 to N^3 with respect to the fastest previously proposed exact algorithm.

We propose a new analytical method for detecting and computing contacts between atoms in biomolecules. It is based on the alpha shape theory and proceeds in three steps. First, we compute the weighted Delaunay triangulation of the union of spheres representing the molecule. In the second step, the Delaunay complex is filtered to derive the dual complex. Finally, contacts between spheres are collected. In this approach, two atoms i and j are defined to be in contact if their centers are connected by an edge in the dual complex. The contact areas between atom i and its neighbors are computed based on the caps formed by these neighbors on the surface of i; the total area of all these caps is partitioned according to their spherical Laguerre Voronoi diagram on the surface of i. This method is analytical and its implementation in a new program BallContact is fast and robust. We have used BallContact to study contacts in a database of 1551 high resolution protein structures. We show that with this new definition of atomic contacts, we generate realistic representations of the environments of atoms and residues within a protein. In particular, we establish the importance of nonpolar contact areas that complement the information represented by the accessible surface areas. This new method bears similarity to the tessellation methods used to quantify atomic volumes and contacts, with the advantage that it does not require the presence of explicit solvent molecules if the surface of the protein is to be considered. © 2012 Wiley Periodicals, Inc.

Determining the structure of protein-protein complexes remains a difficult and lengthy process, either by NMR or by X-ray crystallography. Several computational methods based on docking have been developed to support and even serve as possible alternatives to these experimental methods. In this paper, we introduce a new protein-protein docking algorithm, shDock, based on shape complementarity. We characterize the local geometry on each protein surface with a new shape descriptor, the surface-histogram. We measure the complementarity between two surface-histograms, one on each protein, using a modified Manhattan distance. When a match is found between two local protein surfaces, a model is generated for the protein complex, which is then scored by checking for collision between the two proteins. We have tested our algorithm on Version 3 of the ZDOCK protein-protein docking benchmark. We found that for 110 out of the 124 test cases of bound docking in the benchmark, our algorithm was able to generate a model in the top 3600 candidates for the protein complex within an RMSD of 2.5 A from its native structure. For unbound docking predictions, we found a model within 2.5 A in the top 3600 models in 54 out of 124 test cases. A comparison with other shape-based docking algorithms demonstrates that our approach gives significantly improved performance for both bound and unbound docking test cases.

The three-dimensional structure of a protein is organized around the packing of its secondary structure elements. Predicting the topology and constructing the geometry of structural motifs involving α-helices and/or β-strands are therefore key steps for accurate prediction of protein structure. While many efforts have focused on how to pack helices and on how to sample exhaustively the topologies and geometries of multiple strands forming a β-sheet in a protein, there has been little progress on generating native-like packings of helices on sheets. We describe a method that can generate the packing of multiple helices on a given β-sheet for αβα sandwich type protein folds. This method mines the results of a statistical analysis of the conformations of αβ2 motifs in protein structures to provide input values for the geometric attributes of the packing of a helix on a sheet. It then proceeds with a geometric builder that generates multiple arrangements of the helices on the sheet of interest by sampling through these values and performing consistency checks that guarantee proper loop geometry between the helices and the strands, minimal number of collisions between the helices, and proper formation of a hydrophobic core. The method is implemented as a module of ProteinShop. Our results show that it produces structures that are within 4–6 A RMSD of the native one, regardless of the number of helices that need to be packed, though this number may increase if the protein has several helices between two consecutive strands in the sequence that pack on the sheet formed by these two strands. Proteins 2011; Published 2011 Wiley-Liss, Inc.

Geometry plays a major role in our attempts to understand the activity of large molecules. For example, surface area and volume are used to quantify the interactions between these molecules and the water surrounding them in implicit solvent models. In addition, the detection of pockets serves as a starting point for predictive studies of biomolecule-ligand interactions. The alpha shape theory provides an exact and robust method for computing these geometric measures. Several implementations of this theory are currently available. We show however that these implementations fail on very large macromolecular systems. We show that these difficulties are not theoretical; rather, they are related to the architecture of current computers that rely on the use of cache memory to speed up calculation. By rewriting the algorithms that implement the different steps of the alpha shape theory such that we enforce locality, we show that we can remediate these cache problems; the corresponding code, UnionBall has an apparent (n) behavior over a large range of values of n (up to tens of millions), where n is the number of atoms. As an example, it takes 136 sec with UnionBall to compute the contribution of each atom to the surface area and volume of a viral capsid with more than five million atoms on a commodity PC. UnionBall includes functions for computing analytically the surface area and volume of the intersection of two, three and four spheres that are fully detailed in an appendix. UnionBall is available as an OpenSource software. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011

The three-dimensional structure of a protein is organized around the packing of its secondary structure elements. While much is known about the packing geometry observed between α-helices and between β-sheets, there has been little progress on characterizing helix-sheet interactions. We present an analysis of the conformation of αβ2 motifs in proteins, corresponding to all occurrences of helices in contact with two strands that are hydrogen-bonded. The geometry of the αβ2 motif is characterized by the azimuthal angle θ between the helix axis and an average vector representing the two strands, the elevation angle ψ between the helix axis and the plane containing the two strands, and the distance D between the helix and the strands. We observe that the helix tends to align to the two strands, with a preference for an antiparallel orientation if the two strands are parallel; this preference is diminished for other topologies of the β-sheet. Sidechain packing at the interface between the helix and the strands is mostly hydrophobic, with a preference for aliphatic amino acids in the strand and aromatic amino acids in the helix. From the knowledge of the geometry and amino acid propensities of αβ2 motifs in proteins, we have derived different statistical potentials that are shown to be efficient in picking native-like conformations among a set of non-native conformations in well-known decoy datasets. The information on the geometry of αβ2 motifs as well as the related statistical potentials has applications in the field of protein structure prediction.

Finding structural similarities between proteins often helps reveal shared functionality, which otherwise might not be detected by native sequence information alone. Such similarity is usually detected and quantified by protein structure alignment. Determining the optimal alignment between two protein structures, however, remains a hard problem. An alternative approach is to approximate each three-dimensional protein structure using a sequence of motifs derived from a structural alphabet. Using this approach, structure comparison is performed by comparing the corresponding motif sequences or structural sequences. In this article, we measure the performance of such alphabets in the context of the protein structure classification problem. We consider both local and global structural sequences. Each letter of a local structural sequence corresponds to the best matching fragment to the corresponding local segment of the protein structure. The global structural sequence is designed to generate the best possible complete chain that matches the full protein structure. We use an alphabet of 20 letters, corresponding to a library of 20 motifs or protein fragments having four residues. We show that the global structural sequences approximate well the native structures of proteins, with an average coordinate root mean square of 0.69 A over 2225 test proteins. The approximation is best for all alpha-proteins, while relatively poorer for all beta-proteins. We then test the performance of four different sequence representations of proteins (their native sequence, the sequence of their secondary-structure elements, and the local and global structural sequences based on our fragment library) with different classifiers in their ability to classify proteins that belong to five distinct folds of CATH. Without surprise, the primary sequence alone performs poorly as a structure classifier. We show that addition of either secondary-structure information or local information from the structural sequence considerably improves the classification accuracy. The two fragment-based sequences perform better than the secondary-structure sequence but not well enough at this stage to be a viable alternative to more computationally intensive methods based on protein structure alignment.

A new method is proposed for unravelling the patterns between a set of experiments and the features that characterize those experiments. The aims are to extract these patterns in the form of a coupling between the rows and columns of the corresponding data matrix and to use this geometry as a support for model testing. These aims are reached through two key steps, namely application of an iterative geometric approach to couple the metric spaces associated with the rows and columns, and use of statistical physics to generate matrices that mimic the original data while maintaining their inherent structure, thereby providing the basis for hypothesis testing and statistical inference. The power of this new method is illustrated on the study of the impact of water stress conditions on the attributes of ‘Cabernet Sauvignon’ Grapes, Juice, Wine and Bottled Wine from two vintages. The first step, named data mechanics, de-convolutes the intrinsic effects of grape berries and wine attributes due to the experimental irrigation conditions from the extrinsic effects of the environment. The second step provides an analysis of the associations of some attributes of the bottled wine with characteristics of either the matured grape berries or the resulting juice, thereby identifying statistically significant associations between the juice pH, yeast assimilable nitrogen, and sugar content and the bottled wine alcohol level.

Distance-dependent, pairwise, statistical potentials are based on the concept that the packing observed in known protein structures can be used as a reference for comparing different 3D models for a protein. Here, packing refers to the set of all pairs of atoms in the molecule. Among all methods developed to assess three-dimensional models, statistical potentials are subject both to praise for their power of discrimination, and to criticism for the weaknesses of their theoretical foundations. Classical derivations of pairwise potentials assume statistical independence of all pairs of atoms. This assumption, however, is not valid in general. We show that we can filter the list of all interactions in a protein to generate a much smaller subset of pairs that retains most of the structural information contained in proteins. The filter is based on a geometric method called alpha shapes that captures the packing in a conformation. Statistical scoring functions derived from such subsets perform as well as scoring functions derived from the set of all pairwise interactions.

We report the largest and most comprehensive comparison of protein structural alignment methods. Specifically, we evaluate six publicly available structure alignment programs: SSAP, STRUCTAL, DALI, LSQMAN, CE and SSM by aligning all 8,581,970 protein structure pairs in a test set of 2930 protein domains specially selected from CATH v.2.4 to ensure sequence diversity. We consider an alignment good if it matches many residues, and the two substructures are geometrically similar. Even with this definition, evaluating structural alignment methods is not straightforward. At first, we compared the rates of true and false positives using receiver operating characteristic (ROC) curves with the CATH classification taken as a gold standard. This proved unsatisfactory in that the quality of the alignments is not taken into account: sometimes a method that finds less good alignments scores better than a method that finds better alignments. We correct this intrinsic limitation by using four different geometric match measures (SI, MI, SAS, and GSAS) to evaluate the quality of each structural alignment. With this improved analysis we show that there is a wide variation in the performance of different methods; the main reason for this is that it can be difficult to find a good structural alignment between two proteins even when such an alignment exists. We find that STRUCTAL and SSM perform best, followed by LSQMAN and CE. Our focus on the intrinsic quality of each alignment allows us to propose a new method, called "Best-of-All" that combines the best results of all methods. Many commonly used methods miss 10-50% of the good Best-of-All alignments. By putting existing structural alignments into proper perspective, our study allows better comparison of protein structures. By highlighting limitations of existing methods, it will spur the further development of better structural alignment methods. This will have significant biological implications now that structural comparison has come to play a central role in the analysis of experimental work on protein structure, protein function and protein evolution.

Assembling fragments from known protein structures is a widely used approach to construct structural models for new proteins. We describe an application of this idea to an important inverse kinematics problem in structural biology: the loop closure problem. We have developed an algorithm for generating the conformations of candidate loops that fit in a gap of given length in a protein structure framework. Our method proceeds by concatenating small fragments of protein chosen from small libraries of representative fragments. Our approach has the advantages of ab initio methods since we are able to enumerate all candidate loops in the discrete approximation of the conformational space accessible to the loop, as well as the advantages of database search approach since the use of fragments of known protein structures guarantees that the backbone conformations are physically reasonable. We test our approach on a set of 427 loops, varying in length from four residues to 14 residues. The quality of the candidate loops is evaluated in terms of global coordinate root mean square (cRMS). The top predictions vary between 0.3 and 4.2 Å for four-residue loops and between 1.5 and 3.1 Å for 14-residue loops, respectively.

Quantitative reasoning and techniques are increasingly ubiquitous across the life sciences. However, new graduate researchers with a biology background are often not equipped with the skills that are required to utilize such techniques correctly and efficiently. In parallel, there are increasing numbers of engineers, mathematicians, and physical scientists interested in studying problems in biology with only basic knowledge of this field. Students from such varied backgrounds can struggle to engage proactively together to tackle problems in biology. There is therefore a need to establish bridges between those disciplines. It is our proposal that the beginning of graduate school is the appropriate time to initiate those bridges through an interdisciplinary short course. We have instigated an intensive 10-day course that brought together new graduate students in the life sciences from across departments within the National University of Singapore. The course aimed at introducing biological problems as well as some of the quantitative approaches commonly used when tackling those problems. We have run the course for three years with over 100 students attending. Building on this experience, we share 11 quick tips on how to run such an effective, interdisciplinary short course for new graduate students in the biosciences.

We describe a new approach to explore and quantify the sequence space associated with a given protein structure. A set of sequences are optimized for a given target structure, using all-atom models and a physical energy function. Specificity of the sequence for its target is ensured by using the random energy model, which keeps the amino acid composition of the sequence constant. The designed sequences provide a multiple sequence alignment that describes the sequence space compatible with the structure of interest; here the size of this space is estimated by using an information entropy measure. In parallel, multiple alignments of naturally occurring sequences can be derived by using either sequence or structure alignments. We compared these 3 independent multiple sequence alignments for 10 different proteins, ranging in size from 56 to 310 residues. We observed that the subset of the sequence space derived by using our design procedure is similar in size to the sequence spaces observed in nature. These results suggest that the volume of sequence space compatible with a given protein fold is defined by the length of the protein as well as by the topology (i.e., geometry of the polypeptide chain) and the stability (i.e., free energy of denaturation) of the fold.

The ASTRAL compendium provides several databases and tools to aid in the analysis of protein structures, particularly through the use of their sequences. It is partially derived from the SCOP database of protein domains, and it includes sequences for each domain as well as other resources useful for studying these sequences and domain structures. Several major improvements have been made to the ASTRAL compendium since its initial release 2 years ago. The number of protein domain sequences included has doubled from 15 190 to 30 867, and additional databases have been added. The Rapid Access Format (RAF) database contains manually curated mappings linking the biological amino acid sequences described in the SEQRES records of PDB entries to the amino acid sequences structurally observed (provided in the ATOM records) in a format designed for rapid access by automated tools. This information is used to derive sequences for protein domains in the SCOP database. In cases where a SCOP domain spans several protein chains, all of which can be traced back to a single genetic source, a ‘genetic domain’ sequence is created by concatenating the sequences of each chain in the order found in the original gene sequence. Both the original-style library of SCOP sequences and a new library including genetic domain sequences are available. Selected representative subsets of each of these libraries, based on multiple criteria and degrees of similarity, are also included. ASTRAL may be accessed at http://astral.stanford.edu/.

In this paper, we propose a new method for computing a distance between two shapes embedded in three-dimensional space. Instead of comparing directly the geometric properties of the two shapes, we measure the cost of deforming one of the two shapes into the other. The deformation is computed as the geodesic between the two shapes in the space of shapes. The geodesic is found as a minimizer of the Onsager–Machlup action, based on an elastic energy for shapes that we define. Its length is set to be the integral of the action along that path; it defines an intrinsic quasi-metric on the space of shapes. We illustrate applications of our method to geometric morphometrics using three datasets representing bones and teeth of primates. Experiments on these datasets show that the variational quasi-metric we have introduced performs remarkably well both in shape recognition and in identifying evolutionary patterns, with success rates similar to, and in some cases better than, those obtained by expert observers.

We propose a new method inspired from statistical mechanics for extracting geometric information from undirected binary networks and generating random networks that conform to this geometry. In this method an undirected binary network is perceived as a thermodynamic system with a collection of permuted adjacency matrices as its states. The task of extracting information from the network is then reformulated as a discrete combinatorial optimization problem of searching for its ground state. To solve this problem, we apply multiple ensembles of temperature regulated Markov chains to establish an ultrametric geometry on the network. This geometry is equipped with a tree hierarchy that captures the multiscale community structure of the network. We translate this geometry into a Parisi adjacency matrix, which has a relative low energy level and is in the vicinity of the ground state. The Parisi adjacency matrix is then further optimized by making block permutations subject to the ultrametric geometry. The optimal matrix corresponds to the macrostate of the original network. An ensemble of random networks is then generated such that each of these networks conforms to this macrostate; the corresponding algorithm also provides an estimate of the size of this ensemble. By repeating this procedure at different scales of the ultrametric geometry of the network, it is possible to compute its evolution entropy, i.e. to estimate the evolution of its complexity as we move from a coarse to a fine description of its geometric structure. We demonstrate the performance of this method on simulated as well as real data networks.

NMR relaxation parameters are usually derived from series of 2D experiments. The whole procedure can be very time consuming, especially for the study of the relaxation of nuclei at natural abundance. Palmer and Mandel have proposed the use of accordion spectroscopy to determine one relaxation parameter using two experiments only. In this paper, we show that the experimental time can be further reduced, by recording only three experiments for the determination of both the longitudinal and transverse relaxation rates. The analysis of the experiments is performed in the frequency domain, the relaxation rates being deduced from the linewidth of the peaks of interest. A detailed statistical analysis of errors introduced by the line fitting procedure on derived relaxation parameters was used to derive guidelines for the choice of experimental parameters. This procedure was applied to the study of the Ca relaxation parameters of a six-residue unlabeled peptide. The results were compared with those obtained by classical accordion spectroscopy. Copyright  2001 John Wiley & Sons, Ltd.

Comparison of protein structures can reveal distant evolutionary relationships that would not be detected by sequence information alone. This helps to infer functional properties. In recent years, many methods for pairwise protein structure alignment have been proposed and are now available on the World Wide Web. Although these methods have made it possible to compare all available protein structures, they also highlight the remaining difficulties in defining a reliable score for protein structure similarities.

It is generally accepted that many different protein sequences have similar folded structures, and that there is a relatively high probability that a new sequence possesses a previously observed fold. An indirect consequence of this is that protein design should define the sequence space accessible to a given structure, rather than providing a single optimized sequence. We have recently developed a new approach for protein sequence design, which optimizes the complete sequence of a protein based on the knowledge of its backbone structure, its amino acid composition and a physical energy function including van der Waals interactions, electrostatics, and environment free energy. The specificity of the designed sequence for its template backbone is imposed by keeping the amino acid composition fixed. Here, we show that our procedure converges in sequence space, albeit not to the native sequence of the protein. We observe that while polar residues are well conserved in our designed sequences, non-polar amino acids at the surface of a protein are often replaced by polar residues. The designed sequences provide a multiple alignment of sequences that all adopt the same three-dimensional fold. This alignment is used to derive a profile matrix for chicken triose phosphate isomerase, TIM. The matrix is found to recognize significantly the native sequence for TIM, as well as closely related sequences. Possible application of this approach to protein fold recognition is discussed.

We have developed a fully automated protein design strategy that works on the entire sequence of the protein and uses a full atom representation. At each step of the procedure, an all-atom model of the protein is built using the template protein structure and the current designed sequence. The energy of the model is used to drive a Monte Carlo optimization in sequence space: random moves are either accepted or rejected based on the Metropolis criterion. We rely on the physical forces that stabilize native protein structures to choose the optimum sequence. Our energy function includes van der Waals interactions, electrostatics and an environment free energy. Successful protein design should be specific and generate a sequence compatible with the template fold and incompatible with competing folds. We impose specificity by maintaining the amino acid composition constant, based on the random energy model. The specificity of the optimized sequence is tested by fold recognition techniques. Successful sequence designs for the B1 domain of protein G, for the lambda repressor and for sperm whale myoglobin are presented. We show that each additional term of the energy function improves the performance of our design procedure: the van der Waals term ensures correct packing, the electrostatics term increases the specificity for the correct native fold, and the environment solvation term ensures a correct pattern of buried hydrophobic and exposed hydrophilic residues. For the globin family, we show that we can design a protein sequence that is stable in the myoglobin fold, yet incompatible with the very similar hemoglobin fold.

The most recent critical assessment of structure prediction meeting (CASP3) revealed significant progress in predicting the three–dimensional folds of proteins with unknown structures.

The ab initio folding problem can be divided into two sequential tasks of approximately equal computational complex- ity: the generation of native-like backbone folds and the positioning of side chains upon these backbones. The prediction of side-chain confor- mation in this context is challenging, because at best only the near-native global fold of the protein is known. To test the effect of displace- ments in the protein backbones on side-chain prediction for folds generated ab initio, sets of near-native backbones (I 4ACa RMS error) for four small proteins were generated by two methods. The steric environment surrounding each residue was probed by placing the side chains in the native conformation on each of these decoys, followed by torsion-space optimi- zation to remove steric clashes on a rigid back- bone. We observe that on average 40% of the x1 angles were displaced by 40° or more, effec- tively setting the limits in accuracy for side- chain modeling under these conditions. Three different algorithms were subsequently used for prediction of side-chain conformation. The average prediction accuracy for the three meth- ods was remarkably similar: 49% to 51% of the x1 angles were predicted correctly overall (33% to 36% of the x112 angles). Interestingly, when the inter-side-chain interactions were disre- garded, the mean accuracy increased. A consen- sus approach is described, in which side-chain conformations are defined based on the most frequently predicted x angles for a given method upon each set of near-native back- bones. We find that consensus modeling, which de facto includes backbone flexibility, im- proves side-chain prediction: x1 accuracy im- proved to 51-54% (36-42% of x112). Implica- tions of a consensus method for ab initio protein structure prediction are discussed. Pro- teins 33:204-217, 1998. r 1998 Wiley-Liss, Inc.

An optimization protocol for modeling protein structures on lattice is proposed which is based on self-consistent mean field (SCMF) theory. In this procedure, the protein residues are supposed to be independent, and their possible positions are given by a list of lattice sites. To do this, an effective larger system is considered, in which each residue i is supposed to occupy all possible sites j, each with a weight V(i,j) stored in the so-called lattice probability matrix V. The effective energy of the system is computed, and iteratively minimized with respect to the weights V, the lattice sites being fixed in space. The final self-consistent V matrix describes the conformational space available to the protein, based on the energy function implemented. This energy function contains two types of terms, namely simple geometric terms which ensure bond connectivity and prevent chain intersection, and energy terms specific to the problem of interest. The application of the above protocol to building a lattice...

A new algorithm is presented that provides a constructive way to conformally warp a triangular mesh of genus zero to a destination surface with minimal metric deformation, as well as a means to compute automatically a measure of the geometric difference between two surfaces of genus zero. The algorithm takes as input a pair of surfaces that are topological 2-spheres, each surface given by a distinct triangulation. The algorithm then constructs a map $(f)$ between the two surfaces. First, each of the two triangular meshes is mapped to the unit sphere using a discrete conformal mapping algorithm. The two mappings are then composed with a Möbius transformation to generate the function $(f)$. The Möbius transformation is chosen by minimizing an energy that measures the distance of $(f)$ from an isometry. We illustrate our approach using several "real life" data sets. We show first that the algorithm allows for accurate, automatic, and landmark-free nonrigid registration of brain surfaces. We then validate our approach by comparing shapes of proteins. We provide numerical experiments to demonstrate that the distances computed with our algorithm between low-resolution, surface-based representations of proteins are highly correlated with the corresponding distances computed between high-resolution, atomistic models for the same proteins.

Elastic network models (ENM) are based on the idea that the geometry of a protein structure provides enough information for computing its fluctuations around its equilibrium conformation. This geometry is represented as an elastic network (EN) that is, a network of links between residues. A spring is associated with each of these links. The normal modes of the protein are then identified with the normal modes of the corresponding network of springs. Standard approaches for generating ENs rely on a cutoff distance. There is no consensus on how to choose this cutoff. In this work, we propose instead to filter the set of all residue pairs in a protein using the concept of alpha shapes. The main alpha shape we considered is based on the Delaunay triangulation of the Cα positions; we referred to the corresponding EN as EN(∞). We have shown that heterogeneous anisotropic network models, called αHANMs, that are based on EN(∞) reproduce experimental B-factors very well, with correlation coefficients above 0.99 and root-mean-square deviations below 0.1 A(2) for a large set of high resolution protein structures. The construction of EN(∞) is simple to implement and may be used automatically for generating ENs for all types of ENMs.

Despite years of effort, the problem of predicting the conformations of protein side chains remains a subject of inquiry. This problem has three major issues, namely defining the conformations that a side chain may adopt within a protein, developing a sampling procedure for generating possible side-chain packings, and defining a scoring function that can rank these possible packings. To solve the former of these issues, most procedures rely on a rotamer library derived from databases of known protein structures. We introduce an alternative method that is free of statistics. We begin with a rotamer library that is based only on stereochemical considerations; this rotamer library is then optimized independently for each protein under study. We show that this optimization step restores the diversity of conformations observed in native proteins. We combine this protein-dependent rotamer library (PDRL) method with the self-consistent mean field (SCMF) sampling approach and a physics-based scoring function into a new side-chain prediction method, SCMF-PDRL. Using two large test sets of 831 and 378 proteins, respectively, we show that this new method compares favorably with competing methods such as SCAP, OPUS-Rota, and SCWRL4 for energy-minimized structures.

Morphing was initially developed as a cinematic effect, where one image is seamlessly transformed into another image. The technique was widely adopted by biologists to visualize the transition between protein conformational states, generating an interpolated pathway from an initial to a final protein structure. Geometric morphing seeks to create visually suggestive movies that illustrate structural changes between conformations but do not necessarily represent a biologically relevant pathway, while minimum energy path (MEP) interpolations aim at describing the true transition state between the crystal structure minima in the energy landscape.

International audience; Simulations of macromolecular structures involve the minimization of a potential-energy function that presents many local minima. Mean-field theory provides a tool that enables us to escape these minima, by enhancing sampling in conformational space. The number of applications of this technique has increased significantly over the past year, enabling problems with protein-homology modelling and inverted protein structure prediction to be solved.

An analytic formula is developed for calculating the generalized NMR order parameters in a protein from the normal mode analysis (NMA). The generalized order parameter, S2, is given as thermal ensemble average of a Taylor series in powers of Δ, the displacement of internuclear vector from its mean. Henry and Szabo developed a method to calculate the ensemble average based on the NMA carried out in the Cartesian coordinate space (CCS). However, atomic motions in each individual CCS normal modes are linear in the three‐dimensional space, which may cause interatomic distances even between covalently bonded atoms to change significantly. In this situation Henry and Szabo proposed to use a special formula for S2 which includes a trick to compensate such changes. We showed that by carrying out the NMA in the dihedral angle space (DAS) and by interpreting each DAS normal mode into curved atomic motions, S2 can be calculated reliably for spin pairs separated up to about 10 intervening covalent bonds by a natural formula without any trick.

Dynamics is essential to the biological functions of many bio-molecules, yet our knowledge of dynamics remains fragmented. Experimental techniques for studying bio-molecules either provide high resolution information on static conformations of the molecule or provide low-resolution, ensemble information that does not shed light on single molecule dynamics. In parallel, bio-molecular dynamics occur at time scale that are not yet attainable through detailed simulation methods. These limitations are especially noticeable when studying transition paths. To address this issue, we report in this paper two methods that derive meaningful trajectories for proteins between two of their conformations. The first method, MinActionPath, uses approximations of the potential energy surface for the molecule to derive an analytical solution of the equations of motion related to the concept of minimum action path. The second method, RelaxPath, follows the same principle of minimum action path but implements a more sophisticated potential, including a mixed elastic potential and a collision term to alleviate steric clashes. Using this new potential, the equations of motion cannot be solved analytically. We have introduced a relaxation method for solving those equations. We describe both the theories behind the two methods and their implementations, focusing on the specific techniques we have used that make those implementations amenable to study large molecular systems. We have illustrated the performance of RelaxPath on simple 2D systems. We have also compared MinActionPath and RelaxPath to other methods for generating transition paths on a well suited test set of large proteins, for which the end points of the trajectories as well as an intermediate conformation between those end points are known. We have shown that RelaxPath outperforms those other methods, including MinActionPath, in its ability to generate trajectories that get close to the known intermediates. We have also shown that the structures along the RelaxPath trajectories remain protein-like. Open source versions of the two programs MinActionPath and RelaxPath are available by request.