Search

Linear assignment problems hold a pivotal role in combinatorial optimization, offering a broad spectrum of applications within the field of data sciences. They consist of assigning "agents" to "tasks" in a way that leads to a minimum total cost associated with the assignment. The assignment is balanced when the number of agents equals the number of tasks, with a one-to-one correspondence between agents and tasks, and it is and unbalanced otherwise. Additional options and constraints may be imposed, such as allowing agents to perform multiple tasks or allowing tasks to be performed by multiple agents. In this paper, we propose a novel framework that can solve all these assignment problems employing methodologies derived from the field of statistical physics. We describe this formalism in detail and validate all its assertions. A major part of this framework is the definition of a concave effective free energy function that encapsulates the constraints of the assignment problem within a finite temperature context. We demonstrate that this free energy monotonically decreases as a function of a parameter β representing the inverse of temperature. As β increases, the free energy converges to the optimal assignment cost. Furthermore, we demonstrate that when β values are sufficiently large, the exact solution to the assignment problem can be derived by rounding off the elements of the computed assignment matrix to the nearest integer. We describe a computer implementation of our framework and illustrate its application to multi-task assignment problems for which the Hungarian algorithm is not applicable. [ABSTRACT FROM AUTHOR]

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. This method allows us to generate conditioned trajectories with a high accuracy. [ABSTRACT FROM AUTHOR]

A new algorithm is presented to compute nonrigid, possibly partial comparisons of shapes defined by unstructured triangulations of their surfaces. The algorithm takes as input a pair of surfaces with each surface given by a distinct and unrelated triangulation. Its goal is to define a possibly partial correspondence between the vertices of the two triangulations, with a cost associated with this correspondence that can serve as a measure of the similarity of the two shapes. To find this correspondence, the vertices in each triangulation are characterized by a signature vector of features. We tested both the LD-SIFT signatures, based on the concept of spin images, and the wave kernel signatures obtained by solving the Shrödinger equation on the triangulation. A cost matrix C is constructed such that C (k , l) is the norm of the difference of the signature vectors of vertices k and l. The correspondence between the triangulations is then computed as the transport plan that solves the optimal transport or optimal partial transport problem between their sets of vertices. We use a statistical physics approach to solve these problems. The presentation of the proposed algorithm is complemented with examples that illustrate its effectiveness and manageable computing cost. [ABSTRACT FROM AUTHOR]

The current SARS-CoV-2 pandemic highlights our fragility when we are exposed to emergent viruses either directly or through zoonotic diseases. Fortunately, our knowledge of the biology of those viruses is improving. In particular, we have more and more structural information on virions, i.e., the infective form of a virus that includes its genomic material and surrounding protective capsid, and on their gene products. It is important to have methods that enable the analyses of structural information on such large macromolecular systems. We review some of those methods in this paper. We focus on understanding the geometry of virions and viral structural proteins, their dynamics, and their energetics, with the ambition that this understanding can help design antiviral agents. We discuss those methods in light of the specificities of those structures, mainly that they are huge. We focus on three of our own methods based on the alpha shape theory for computing geometry, normal mode analyses to study dynamics, and modified Poisson–Boltzmann theories to study the organization of ions and co-solvent and solvent molecules around biomacromolecules. The corresponding software has computing times that are compatible with the use of regular desktop computers. We show examples of their applications on some outer shells and structural proteins of the West Nile Virus. [ABSTRACT FROM AUTHOR]

The Gromov-Wasserstein (GW) formalism can be seen as a generalization of the optimal transport (OT) formalism for comparing two distributions associated with different metric spaces. It is a quadratic optimization problem and solving it usually has computational costs that can rise sharply if the problem size exceeds a few hundred points. Recently fast techniques based on entropy regularization have being developed to solve an approximation of the GW problem quickly. There are issues, however, with the numerical convergence of those regularized approximations to the true GW solution. To circumvent those issues, we introduce a novel strategy to solve the discrete GW problem using methods taken from statistical physics. We build a temperature-dependent free energy function that reflects the GW problem's constraints. To account for possible differences of scales between the two metric spaces, we introduce a scaling factor s in the definition of the energy. From the extremum of the free energy, we derive a mapping between the two probability measures that are being compared, as well as a distance between those measures. This distance is equal to the GW distance when the temperature goes to zero. The optimal scaling factor itself is obtained by minimizing the free energy with respect to s. We illustrate our approach on the problem of comparing shapes defined by unstructured triangulations of their surfaces. We use several synthetic and "real life" datasets. We demonstrate the accuracy and automaticity of our approach in non-rigid registration of shapes. We provide numerical evidence that there is a strong correlation between the GW distances computed from low-resolution, surface-based representations of proteins and the analogous distances computed from atomistic models of the same proteins. [ABSTRACT FROM AUTHOR]

We propose a novel stochastic method to generate Brownian paths conditioned to start at an initial point and end at a given final point during a fixed time tf under a given potential U(x). These paths are sampled with a probability given by the overdamped Langevin dynamics.We showthat these paths can be exactly generated by a local stochastic partial differential equation. This equation cannot be solved in general but we present several approximations that are valid either in the low temperature regime or in the presence of barrier crossing. We show that this method warrants the generation of statistically independent transition paths. It is computationally very efficient.We illustrate the method first on two simple potentials, the two-dimensional Mueller potential and theMexican hat potential, and then on the multi-dimensional problem of conformational transitions in proteins using the "Mixed Elastic Network Model" as a benchmark. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract 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 [...]

This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines. Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problems--Computations on discrete structures, Geometrical problems and computations; 1.6.5 Simulation and Modeling: Model Development--Modeling methodologies General Terms: Algorithms Additional Key Words and Phrases: Computational geometry, computer vision, mobile networks, modeling, molecular biology, motion modeling, physical simulation, robotoics, spatio-temporal databases

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. [ABSTRACT FROM AUTHOR]

Two-dimensional 1H NMR spectroscopy establishes the solution structure of a 35 amino acid peptide, PMP-D2. This peptide isolated from Locusta migratoria possesses three disulfide bridges and a core region having a short antiparallel beta-sheet, which is three stranded. Ca2+ currents are blocked by this peptide, which is stable in organic solvents.

The application of nuclear magnetic resonance techniques to Ga3+ analogue yields the 3D structure of ferri-pyoverdin GM-II in solution. Ferri-pyoverdin GM-II is isolated from Pseudomonas fluorescens culture. Interprotein distances and coupling constants are used as constraints with FILMAN to calculate the distance geometry. Energy reduction using MM2 and AMBER are used to analyze energy conformation. The structures are determined using NOESY spectra back calculation technique.

Abstract Background The analysis of protein structures provides fundamental insight into most biochemical functions and consequently into the cause and possible treatment of diseases. As the structures of most known proteins cannot be solved experimentally for technical or sometimes simply for time constraints, in silico protein structure prediction is expected to step in and generate a more complete picture of the protein structure universe. Molecular modeling of protein structures is a fast growing field and tremendous works have been done since the publication of the very first model. The growth of modeling techniques and more specifically of those that rely on the existing experimental knowledge of protein structures is intimately linked to the developments of high resolution, experimental techniques such as NMR, X-ray crystallography and electron microscopy. This strong connection between experimental and in silico methods is however not devoid of criticisms and concerns among modelers as well as among experimentalists. Results In this paper, we focus on homology-modeling and more specifically, we review how it is perceived by the structural biology community and what can be done to impress on the experimentalists that it can be a valuable resource to them. We review the common practices and provide a set of guidelines for building better models. For that purpose, we introduce the H-factor, a new indicator for assessing the quality of homology models, mimicking the R-factor in X-ray crystallography. The methods for computing the H-factor is fully described and validated on a series of test cases. Conclusions We have developed a web service for computing the H-factor for models of a protein structure. This service is freely accessible at http://koehllab.genomecenter.ucdavis.edu/toolkit/h-factor.

Abstract Background The problem of determining the physical conformation of a protein dimer, given the structures of the two interacting proteins in their unbound state, is a difficult one. The location of the docking interface is determined largely by geometric complementarity, but finding complementary geometry is complicated by the flexibility of the backbone and side-chains of both proteins. We seek to generate candidates for docking that approximate the bound state well, even in cases where there is backbone and/or side-chain difference from unbound to bound states. Results We divide the surfaces of each protein into local patches and describe the effect of side-chain flexibility on each patch by sampling the space of conformations of its side-chains. Likely positions of individual side-chains are given by a rotamer library; this library is used to derive a sample of possible mutual conformations within the patch. We enforce broad coverage of torsion space. We control the size of the sample by using energy criteria to eliminate unlikely configurations, and by clustering similar configurations, resulting in 50 candidates for a patch, a manageable number for docking. Conclusions Using a database of protein dimers for which the bound and unbound structures of the monomers are known, we show that from the unbound patch we are able to generate candidates for docking that approximate the bound structure. In patches where backbone change is small (within 1 Å RMSD of bound), we are able to account for flexibility and generate candidates that are good approximations of the bound state (82% are within 1 Å and 98% are within 1.4 Å RMSD of the bound conformation). We also find that even in cases of moderate backbone flexibility our candidates are able to capture some of the overall shape change. Overall, in 650 of 700 test patches we produce a candidate that is either within 1 Å RMSD of the bound conformation or is closer to the bound state than the unbound is.

We present an extension of the self-consistent mean field theory for protein side-chain modeling in which solvation effects are included based on the Poisson-Boltzmann (PB) theory. In this approach, the protein is represented with multiple copies of its side chains. Each copy is assigned a weight that is refined iteratively based on the mean field energy generated by the rest of the protein, until self-consistency is reached. At each cycle, the variational free energy of the multi-copy system is computed; this free energy includes the internal energy of the protein that accounts for vdW and electrostatics interactions and a solvation free energy term that is computed using the PB equation. The method converges in only a few cycles and takes only minutes of central processing unit time on a commodity personal computer. The predicted conformation of each residue is then set to be its copy with the highest weight after convergence. We have tested this method on a database of hundred highly refined NMR structures to circumvent the problems of crystal packing inherent to x-ray structures. The use of the PB-derived solvation free energy significantly improves prediction accuracy for surface side chains. For example, the prediction accuracies for χ1 for surface cysteine, serine, and threonine residues improve from 68%, 35%, and 43% to 80%, 53%, and 57%, respectively. A comparison with other side-chain prediction algorithms demonstrates that our approach is consistently better in predicting the conformations of exposed side chains. [ABSTRACT FROM AUTHOR]

The Poisson–Boltzmann (PB) formalism is among the most popular approaches to modeling the solvation of molecules. It assumes a continuum model for water, leading to a dielectric permittivity that only depends on position in space. In contrast, the dipolar Poisson–Boltzmann–Langevin (DPBL) formalism represents the solvent as a collection of orientable dipoles with nonuniform concentration; this leads to a nonlinear permittivity function that depends both on the position and on the local electric field at that position. The differences in the assumptions underlying these two models lead to significant differences in the equations they generate. The PB equation is a second order, elliptic, nonlinear partial differential equation (PDE). Its response coefficients correspond to the dielectric permittivity and are therefore constant within each subdomain of the system considered (i.e., inside and outside of the molecules considered). While the DPBL equation is also a second order, elliptic, nonlinear PDE, its response coefficients are nonlinear functions of the electrostatic potential. Many solvers have been developed for the PB equation; to our knowledge, none of these can be directly applied to the DPBL equation. The methods they use may adapt to the difference; their implementations however are PBE specific. We adapted the PBE solver originally developed by Holst and Saied [J. Comput. Chem. 16, 337 (1995)] to the problem of solving the DPBL equation. This solver uses a truncated Newton method with a multigrid preconditioner. Numerical evidences suggest that it converges for the DPBL equation and that the convergence is superlinear. It is found however to be slow and greedy in memory requirement for problems commonly encountered in computational biology and computational chemistry. To circumvent these problems, we propose two variants, a quasi-Newton solver based on a simplified, inexact Jacobian and an iterative self-consistent solver that is based directly on the PBE solver. While both methods are not guaranteed to converge, numerical evidences suggest that they do and that their convergence is also superlinear. Both variants are significantly faster than the solver based on the exact Jacobian, with a much smaller memory footprint. All three methods have been implemented in a new code named AQUASOL, which is freely available. [ABSTRACT FROM AUTHOR]

Clustering large and complex data sets whose partitions may adopt arbitrary shapes remains a difficult challenge. Part of this challenge comes from the difficulty in defining a similarity measure between the data points that captures the underlying geometry of those data points. In this paper, we propose an algorithm, DCG++ that generates such a similarity measure that is data-driven and ultrametric. DCG++ uses Markov Chain Random Walks to capture the intrinsic geometry of data, scans possible scales, and combines all this information using a simple procedure that is shown to generate an ultrametric. We validate the effectiveness of this similarity measure within the context of clustering on synthetic data with complex geometry, on a real-world data set containing segmented audio records of frog calls described by mel-frequency cepstral coefficients, as well as on an image segmentation problem. The experimental results show a significant improvement on performance with the DCG-based ultrametric compared to using an empirical distance measure. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 pKa close to the experimental pH50 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 pKa 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 agonistbound 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Proposes an application of self-consistent mean field theory to modeling proteins on a lattice. Approximation under the usual mean field; Maintenance of connectivity through an additional energetic term; Description of the confrontational space available to the protein.

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. © 1996 American Institute of Physics. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Knowledge-based potentials are energy functions derived from the analysis of databases of protein structures and sequences. They can be divided into two classes. Potentials from the first class are based on a direct conversion of the distributions of some geometric properties observed in native protein structures into energy values, while potentials from the second class are trained to mimic quantitatively the geometric differences between incorrectly folded models and native structures. In this paper, we focus on the relationship between energy and geometry when training the second class of knowledge-based potentials. We assume that the difference in energy between a decoy structure and the corresponding native structure is linearly related to the distance between the two structures. We trained two distance-based knowledge-based potentials accordingly, one based on all inter-residue distances (PPD), while the other had the set of all distances filtered to reflect consistency in an ensemble of decoys (PPE). We tested four types of metric to characterize the distance between the decoy and the native structure, two based on extrinsic geometry (RMSD and GTD-TS*), and two based on intrinsic geometry (Q* and MT). The corresponding eight potentials were tested on a large collection of decoy sets. We found that it is usually better to train a potential using an intrinsic distance measure. We also found that PPE outperforms PPD, emphasizing the benefits of capturing consistent information in an ensemble. The relevance of these results for the design of knowledge-based potentials is discussed. [ABSTRACT FROM AUTHOR]

ABSTRACT 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. Proteins 2014; 82:2000-2017. © 2014 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]