Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion

Nearly reducible finite Markov chains: Theory and algorithms

Finite Markov chains, memoryless random walks on complex networks, appear commonly as models for stochastic dynamics in condensed matter physics, biophysics, ecology, epidemiology, economics, and elsewhere. Here, we review exact numerical methods for the analysis of arbitrary discrete- and continuous-time Markovian networks. We focus on numerically stable methods that are required to treat nearly reducible Markov chains, which exhibit a separation of characteristic timescales and are therefore ill-conditioned. In this metastable regime, dense linear algebra methods are afflicted by propagation of error in the finite precision arithmetic, and the kinetic Monte Carlo algorithm to simulate paths is unfeasibly inefficient. Furthermore, iterative eigendecomposition methods fail to converge without the use of nontrivial and system-specific preconditioning techniques. An alternative approach is provided by state reduction procedures, which do not require additional a priori knowledge of the Markov chain. Macroscopic dynamical quantities, such as moments of the first passage time distribution for a transition to an absorbing state, and microscopic properties, such as the stationary, committor, and visitation probabilities for nodes, can be computed robustly using state reduction algorithms. The related kinetic path sampling algorithm allows for efficient sampling of trajectories on a nearly reducible Markov chain. Thus, all of the information required to determine the kinetically relevant transition mechanisms, and to identify the states that have a dominant effect on the global dynamics, can be computed reliably even for computationally challenging models. Rare events are a ubiquitous feature of realistic dynamical systems, and so the methods described herein are valuable in many practical applications.

ART-RRT: As-Rigid-As-Possible search for protein conformational transition paths

The possible functions of a protein are strongly related to its structural rearrangements in the presence of other molecules or environmental changes. Hence, the evaluation of transition paths of proteins, which encodes conformational changes between stable states, is important since it may reveal the underlying mechanisms of the biochemical processes related to these motions. During the last few decades, different geometry-based methods have been proposed to predict such transition paths. However, in the cases where the solution requires complex motions, these methods, which typically constrain only locally the molecular structures, could produce physically irrelevant solutions involving self-intersection. Recently, we have proposed ART-RRT, an efficient method for finding ligand-unbinding pathways. It relies on the exploration of energy valleys in low-dimensional spaces, taking advantage of some mechanisms inspired from computer graphics to ensure the consistency of molecular structures. This article extends ART-RRT to the problem of finding probable conformational transition between two stable states for proteins. It relies on a bidirectional exploration rooted on the two end states and introduces an original strategy to attempt connections between the explored regions. The resulting method is able to produce at low computational cost biologically realistic paths free from self-intersection. These paths can serve as valuable input to other advanced methods for the study of proteins. A better understanding of conformational changes of proteins is important since it may reveal the underlying mechanisms of the biochemical processes related to such motions. Recently, the ART-RRT method has been introduced for finding ligand-unbinding pathways. This article presents an adaptation of the method for finding probable conformational transition between two stable states of a protein. The method is not only computationally cost-effective but also able to produce biologically realistic paths which are free from self-intersection.

The Role of the Active Site Flap in Streptavidin/Biotin Complex Formation

Obtaining a detailed description of how active site flap motion affects substrate or ligand binding will advance structure-based drug design (SBDD) efforts on systems including the kinases, HSP90, HIV protease, ureases, etc. Through this understanding, we will be able to design better inhibitors and better proteins that have desired functions. Herein we address this issue by generating the relevant configurational states of a protein flap on the molecular energy landscape using an approach we call MT_Flex-b and then following this with a procedure to estimate the free energy associated with the motion of the flap region. To illustrate our overall workflow, we explored the free energy changes in the streptavidin/biotin system upon introducing conformational flexibility in loop_3-4 in the biotin unbound ( apo) and bound ( holo) state. The free energy surfaces were created using the Movable Type free energy method, and for further validation, we compared them to potential of mean force (PMF) generated free energy surfaces using MD simulations employing the FF99SBILDN and FF14SB force fields. We also estimated the free energy thermodynamic cycle using an ensemble of closed-like and open-like end states for the ligand unbound and bound states and estimated the binding free energy to be approximately -16.2 kcal/mol (experimental -18.3 kcal/mol). The good agreement between MT_Flex-b in combination with the MT method with experiment and MD simulations supports the effectiveness of our strategy in obtaining unique insights into the motions in proteins that can then be used in a range of biological and biomedical applications.

Adaptive local learning in sampling based motion planning for protein folding

BACKGROUND

Simulating protein folding motions is an important problem in computational biology. Motion planning algorithms, such as Probabilistic Roadmap Methods, have been successful in modeling the folding landscape. Probabilistic Roadmap Methods and variants contain several phases (i.e., sampling, connection, and path extraction). Most of the time is spent in the connection phase and selecting which variant to employ is a difficult task. Global machine learning has been applied to the connection phase but is inefficient in situations with varying topology, such as those typical of folding landscapes.

RESULTS

We develop a local learning algorithm that exploits the past performance of methods within the neighborhood of the current connection attempts as a basis for learning. It is sensitive not only to different types of landscapes but also to differing regions in the landscape itself, removing the need to explicitly partition the landscape. We perform experiments on 23 proteins of varying secondary structure makeup with 52-114 residues. We compare the success rate when using our methods and other methods. We demonstrate a clear need for learning (i.e., only learning methods were able to validate against all available experimental data) and show that local learning is superior to global learning producing, in many cases, significantly higher quality results than the other methods.

CONCLUSIONS

We present an algorithm that uses local learning to select appropriate connection methods in the context of roadmap construction for protein folding. Our method removes the burden of deciding which method to use, leverages the strengths of the individual input methods, and it is extendable to include other future connection methods.

A stochastic roadmap method to model protein structural transitions

Evidence is emerging that the role of protein structure in disease needs to be rethought. Sequence mutations in proteins are often found to affect the rate at which a protein switches between structures. Modeling structural transitions in wildtype and variant proteins is central to understanding the molecular basis of disease. This paper investigates an efficient algorithmic realization of the stochastic roadmap simulation framework to model structural transitions in wildtype and variants of proteins implicated in human disorders. Our results indicate that the algorithm is able to extract useful information on the impact of mutations on protein structure and function.

Transition Networks for the Comprehensive Characterization of Complex Conformational Change in Proteins

Functionally relevant transitions between native conformations of a protein can be complex, involving, for example, the reorganization of parts of the backbone fold, and may occur via a multitude of pathways. Such transitions can be characterized by a transition network (TN), in which the experimentally determined end state structures are connected by a dense network of subtransitions via low-energy intermediates. We show here how the computation of a TN can be achieved for a complex protein transition. First, an efficient hierarchical procedure is used to uniformly sample the conformational subspace relevant to the transition. Then, the best path which connects the end states is determined as well as the rate-limiting ridge on the energy surface which separates them. Graph-theoretical algorithms permit this to be achived by computing the barriers of only a small number out of the many subtransitions in the TN. These barriers are computed using the Conjugate Peak Refinement method. The approach is illustrated on the conformational switch of Ras p21. The best and the 12 next-best transition pathways, having rate-limiting barriers within a range of 10 kcal/mol, were identified. Two main energy ridges, which respectively involve rearrangements of the switch I and switch II loops, show that switch I must rearrange by threading Tyr32 underneath the protein backbone before the rate-limiting switch II rearrangement can occur, while the details of the switch II rearrangement differ significantly among the low-energy pathways.

Sparse roadmap spanners for asymptotically near-optimal motion planning

Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as the number of iterations increases. Roadmaps with this property, however, may grow too large for storing on resource-constrained robots and for achieving efficient online query resolution. By relaxing optimality, asymptotically near-optimal planners produce sparser graphs by not including all edges. The idea stems from graph spanners, which produce sparse subgraphs that guarantee near-optimality. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes, meaning only infinite-size graphs have the desired properties. To address this limitation, this work describes SPARS, an algorithm that returns a sparse roadmap spanner. The method provides the following properties: (a) probabilistic completeness, (b) asymptotic near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. The last point suggests that finite-size data structures with asymptotic near-optimality in continuous spaces may indeed exist. The approach builds simultaneously a dense graph similar to PRM* and its roadmap spanner, meaning that upon construction an infinite-size graph is still needed asymptotically. An extension of SPARS is also presented, termed SPARS2, which removes the dependency on building a dense graph for constructing the sparse roadmap spanner and for which it is shown that the same desirable properties hold. Simulations for rigid-body motion planning show that algorithms for constructing sparse roadmap spanners indeed provide small data structures and result in faster query resolution. The rate of node addition is shown to decrease over time and practically the quality of solutions is considerably better than the theoretical bounds. Upon construction, the memory requirements of SPARS2 are significantly smaller but there is a small sacrifice in the size of the final spanner relative to SPARS.

A Markov-chain model description of binding funnels to enhance the ranking of docked solutions

Within the crowded, seemingly chaotic environment of the cell, proteins are still able to find their binding partners. This is achieved via an ensemble of trajectories, which funnel them towards their functional binding sites, the binding funnel. Here, we characterize funnel-like energy structures on the global energy landscape using time-homogeneous finite state Markov chain models. These models are based on the idea that transitions can occur between structurally similar docking solutions, with transition probabilities determined by their difference in binding energy. Funnel-like energy structures are those containing solutions with very high equilibrium populations. Although these are found surrounding both near-native and false positive binding sites, we show that the removal of nonfunnel-like energy structures, by filtering away solutions with low maximum equilibrium population, can significantly improve the ranking of docked poses.

SIMS: a hybrid method for rapid conformational analysis

Proteins are at the root of many biological functions, often performing complex tasks as the result of large changes in their structure. Describing the exact details of these conformational changes, however, remains a central challenge for computational biology due the enormous computational requirements of the problem. This has engendered the development of a rich variety of useful methods designed to answer specific questions at different levels of spatial, temporal, and energetic resolution. These methods fall largely into two classes: physically accurate, but computationally demanding methods and fast, approximate methods. We introduce here a new hybrid modeling tool, the Structured Intuitive Move Selector (sims), designed to bridge the divide between these two classes, while allowing the benefits of both to be seamlessly integrated into a single framework. This is achieved by applying a modern motion planning algorithm, borrowed from the field of robotics, in tandem with a well-established protein modeling library. sims can combine precise energy calculations with approximate or specialized conformational sampling routines to produce rapid, yet accurate, analysis of the large-scale conformational variability of protein systems. Several key advancements are shown, including the abstract use of generically defined moves (conformational sampling methods) and an expansive probabilistic conformational exploration. We present three example problems that sims is applied to and demonstrate a rapid solution for each. These include the automatic determination of “active” residues for the hinge-based system Cyanovirin-N, exploring conformational changes involving long-range coordinated motion between non-sequential residues in Ribose-Binding Protein, and the rapid discovery of a transient conformational state of Maltose-Binding Protein, previously only determined by Molecular Dynamics. For all cases we provide energetic validations using well-established energy fields, demonstrating this framework as a fast and accurate tool for the analysis of a wide range of protein flexibility problems.

MORPH-PRO: a novel algorithm and web server for protein morphing

Background

Proteins are known to be dynamic in nature, changing from one conformation to another while performing vital cellular tasks. It is important to understand these movements in order to better understand protein function. At the same time, experimental techniques provide us with only single snapshots of the whole ensemble of available conformations. Computational protein morphing provides a visualization of a protein structure transitioning from one conformation to another by producing a series of intermediate conformations.

Results

We present a novel, efficient morphing algorithm, Morph-Pro based on linear interpolation. We also show that apart from visualization, morphing can be used to provide plausible intermediate structures. We test this by using the intermediate structures of a c-Jun N-terminal kinase (JNK1) conformational change in a virtual docking experiment. The structures are shown to dock with higher score to known JNK1-binding ligands than structures solved using X-Ray crystallography. This experiment demonstrates the potential applications of the intermediate structures in modeling or virtual screening efforts.

Conclusions

Visualization of protein conformational changes is important for characterization of protein function. Furthermore, the intermediate structures produced by our algorithm are good approximations to true structures. We believe there is great potential for these computationally predicted structures in protein-ligand docking experiments and virtual screening. The Morph-Pro web server can be accessed at http://morph-pro.bioinf.spbau.ru.

Free Energy Guided Sampling

A free energy-guided sampling (FEGS) method is proposed for accelerating exploration of conformational space in unbiased molecular dynamics. Using the cut-based free energy profile and Markov state models, FEGS speeds up sampling of the canonical ensemble by iteratively restarting multiple short simulations in parallel from regions of the free energy surface visited rarely. This exploration stage is followed by a refinement stage in which multiple independent runs are initiated from Boltzmann distributed conformations. Notably, FEGS does not require either collective variables or reaction coordinates and can control the kinetic distance from the starting conformation. We applied FEGS to the alanine dipeptide, which has a human-comprehensible two-dimensional free energy landscape, and a three-stranded antiparallel β-sheet peptide of 20 residues whose folding/unfolding process is governed by a delicate interplay of enthalpy and entropy. For these two systems, FEGS speeds up the exploration of conformational space by 1 to 2 orders of magnitude with respect to conventional sampling and preserves the basins and barriers on the free energy profile.

Computational models of protein kinematics and dynamics: beyond simulation

Physics-based simulation represents a powerful method for investigating the time-varying behavior of dynamic protein systems at high spatial and temporal resolution. Such simulations, however, can be prohibitively difficult or lengthy for large proteins or when probing the lower-resolution, long-timescale behaviors of proteins generally. Importantly, not all questions about a protein system require full space and time resolution to produce an informative answer. For instance, by avoiding the simulation of uncorrelated, high-frequency atomic movements, a larger, domain-level picture of protein dynamics can be revealed. The purpose of this review is to highlight the growing body of complementary work that goes beyond simulation. In particular, this review focuses on methods that address kinematics and dynamics, as well as those that address larger organizational questions and can quickly yield useful information about the long-timescale behavior of a protein.

Rigid-CLL: avoiding constant-distance computations in cell linked-lists algorithms

Many of the existing molecular simulation tools require the efficient identification of the set of nonbonded interacting atoms. This is necessary, for instance, to compute the energy values or the steric contacts between atoms. Cell linked-lists can be used to determine the pairs of atoms closer than a given cutoff distance in asymptotically optimal time. Despite this long-term optimality, many spurious distances are anyway computed with this method. Therefore, several improvements have been proposed, most of them aiming to refine the volume of influence for each atom. Here, we suggest a different improvement strategy based on avoiding to fill cells with those atoms that are always at a constant distance of a given atom. This technique is particularly effective when large groups of the particles in the simulation behave as rigid bodies as it is the case in simplified models considering only few of the degrees of freedom of the molecule. In these cases, the proposed technique can reduce the number of distance computations by more than one order of magnitude, as compared with the standard cell linked-list technique. The benefits of this technique are obtained without incurring in additional computation costs, because it carries out the same operations as the standard cell linked-list algorithm, although in a different order. Since the focus of the technique is the order of the operations, it might be combined with existing improvements based on bounding the volume of influence for each atom.

Validating clustering of molecular dynamics simulations using polymer models

Background

Molecular dynamics (MD) simulation is a powerful technique for sampling the meta-stable and transitional conformations of proteins and other biomolecules. Computational data clustering has emerged as a useful, automated technique for extracting conformational states from MD simulation data. Despite extensive application, relatively little work has been done to determine if the clustering algorithms are actually extracting useful information. A primary goal of this paper therefore is to provide such an understanding through a detailed analysis of data clustering applied to a series of increasingly complex biopolymer models.

Results

We develop a novel series of models using basic polymer theory that have intuitive, clearly-defined dynamics and exhibit the essential properties that we are seeking to identify in MD simulations of real biomolecules. We then apply spectral clustering, an algorithm particularly well-suited for clustering polymer structures, to our models and MD simulations of several intrinsically disordered proteins. Clustering results for the polymer models provide clear evidence that the meta-stable and transitional conformations are detected by the algorithm. The results for the polymer models also help guide the analysis of the disordered protein simulations by comparing and contrasting the statistical properties of the extracted clusters.

Conclusions

We have developed a framework for validating the performance and utility of clustering algorithms for studying molecular biopolymer simulations that utilizes several analytic and dynamic polymer models which exhibit well-behaved dynamics including: meta-stable states, transition states, helical structures, and stochastic dynamics. We show that spectral clustering is robust to anomalies introduced by structural alignment and that different structural classes of intrinsically disordered proteins can be reliably discriminated from the clustering results. To our knowledge, our framework is the first to utilize model polymers to rigorously test the utility of clustering algorithms for studying biopolymers.

Encoding molecular motions in voxel maps

This paper builds on the combination of robotic path planning algorithms and molecular modeling methods for computing large-amplitude molecular motions, and introduces voxel maps as a computational tool to encode and to represent such motions. We investigate several applications and show results that illustrate the interest of such representation.

The free energy landscape of small molecule unbinding

The spontaneous dissociation of six small ligands from the active site of FKBP (the FK506 binding protein) is investigated by explicit water molecular dynamics simulations and network analysis. The ligands have between four (dimethylsulphoxide) and eleven (5-diethylamino-2-pentanone) non-hydrogen atoms, and an affinity for FKBP ranging from 20 to 0.2 mM. The conformations of the FKBP/ligand complex saved along multiple trajectories (50 runs at 310 K for each ligand) are grouped according to a set of intermolecular distances into nodes of a network, and the direct transitions between them are the links. The network analysis reveals that the bound state consists of several subbasins, i.e., binding modes characterized by distinct intermolecular hydrogen bonds and hydrophobic contacts. The dissociation kinetics show a simple (i.e., single-exponential) time dependence because the unbinding barrier is much higher than the barriers between subbasins in the bound state. The unbinding transition state is made up of heterogeneous positions and orientations of the ligand in the FKBP active site, which correspond to multiple pathways of dissociation. For the six small ligands of FKBP, the weaker the binding affinity the closer to the bound state (along the intermolecular distance) are the transition state structures, which is a new manifestation of Hammond behavior. Experimental approaches to the study of fragment binding to proteins have limitations in temporal and spatial resolution. Our network analysis of the unbinding simulations of small inhibitors from an enzyme paints a clear picture of the free energy landscape (both thermodynamics and kinetics) of ligand unbinding.

Exploring the landscape of protein-ligand interaction energy using probabilistic approach

Analysis of protein/small molecule interactions is crucial in the discovery of new drug candidates and lead structure optimization. Small biomolecules (ligands) are highly flexible and may adopt numerous conformations upon binding to the protein. Using computer simulations instead of sophisticated laboratory procedures may significantly reduce cost of some stages of drug development. Inspired by probabilistic path planning in robotics, stochastic roadmap methodology can be regarded as a very interesting approach to effective sampling of ligand conformational space around a protein molecule. Protein-ligand interactions are divided into two parts: electrostatics, modeled by the Poisson-Boltzmann equation, and van der Waals interactions, represented by the Lennard-Jones potential. The results are promising; it can be shown that locations of binding sites predicted by the simulation are in agreement with those revealed by experimental x-ray crystallography of protein-ligand complexes. We wanted to extend our knowledge beyond the current molecular modeling tools to arrive at a better understanding of the ligand-binding process. To this end, we investigated a two-level model of protein-ligand interaction and sampling of ligand conformational space covering the entire surface of protein target.

Markov dynamic models for long-timescale protein motion

Molecular dynamics (MD) simulation is a well-established method for studying protein motion at the atomic scale. However, it is computationally intensive and generates massive amounts of data. One way of addressing the dual challenges of computation efficiency and data analysis is to construct simplified models of long-timescale protein motion from MD simulation data. In this direction, we propose to use Markov models with hidden states, in which the Markovian states represent potentially overlapping probabilistic distributions over protein conformations. We also propose a principled criterion for evaluating the quality of a model by its ability to predict long-timescale protein motions. Our method was tested on 2D synthetic energy landscapes and two extensively studied peptides, alanine dipeptide and the villin headpiece subdomain (HP-35 NleNle). One interesting finding is that although a widely accepted model of alanine dipeptide contains six states, a simpler model with only three states is equally good for predicting long-timescale motions. We also used the constructed Markov models to estimate important kinetic and dynamic quantities for protein folding, in particular, mean first-passage time. The results are consistent with available experimental measurements.

Guiding the Search for Native-like Protein Conformations with an Ab-initio Tree-based Exploration

In this paper we propose a robotics-inspired method to enhance sampling of native-like conformations when employing only aminoacid sequence information for a protein at hand. Computing such conformations, essential to associating structural and functional information with gene sequences, is challenging due to the high-dimensionality and the rugged energy surface of the protein conformational space. The contribution of this paper is a novel two-layered method to enhance the sampling of geometrically distinct low-energy conformations at a coarse-grained level of detail. The method grows a tree in conformational space reconciling two goals: (i) guiding the tree towards lower energies; and (ii) not oversampling geometrically similar conformations. Discretizations of the energy surface and a low-dimensional projection space are employed to select more often for expansion low-energy conformations in under-explored regions of the conformational space. The tree is expanded with low-energy conformations through a Metropolis Monte Carlo framework that uses a move set of physical fragment configurations. Testing on sequences of eight small-to-medium structurally diverse proteins shows that the method rapidly samples native-like conformations in a few hours on a single CPU. Analysis shows that computed conformations are good candidates for further detailed energetic refinements by larger studies in protein engineering and design.

Control of lipase enantioselectivity by engineering the substrate binding site and access channel

Lipase from Burkholderia cepacia (BCL) has proven to be a very useful biocatalyst for the resolution of 2-substituted racemic acid derivatives, which are important chiral building blocks. Our previous work showed that enantioselectivity of the wild-type BCL could be improved by chemical engineering of the substrate's molecular structure. From this earlier study, three amino acids (L17, V266 and L287) were proposed as targets for mutagenesis aimed at tailoring enzyme enantioselectivity. In the present work, a small library of 57 BCL single mutants targeted on these three residues was constructed and screened for enantioselectivity towards (R,S)-2-chloro ethyl 2-bromophenylacetate. This led to the fast isolation of three single mutants with a remarkable tenfold enhanced or reversed enantioselectivity. Analysis of substrate docking and access trajectories in the active site was then performed. From this analysis, the construction of 13 double mutants was proposed. Among them, an outstanding improved mutant of BCL was isolated that showed an E value of 178 and a 15-fold enhanced specific activity compared to the parental enzyme; thus, this study demonstrates the efficiency of the semirational engineering strategy.

Discrimination of near-native structures in protein-protein docking by testing the stability of local minima

Fast Fourier transform (FFT) correlation methods of protein-protein docking, combined with the clustering of low energy conformations, can find a number of local minima on the energy surface. For most complexes, the locations of the near-native structures can be constrained to the 30 largest clusters, each surrounding a local minimum. However, no reliable further discrimination can be obtained by energy measures because the differences in the energy levels between the minima are comparable with the errors in the energy evaluation. In fact, no current scoring function accounts for the entropic contributions that relate to the width rather than the depth of the minima. Since structures at narrow minima loose more entropy, some of the nonnative states can be detected by determining whether or not a local minimum is surrounded by a broad region of attraction on the energy surface. The analysis is based on starting Monte Carlo Minimization (MCM) runs from random points around each minimum, and observing whether a certain fraction of trajectories converge to a small region within the cluster. The cluster is considered stable if such a strong attractor exists, has at least 10 convergent trajectories, is relatively close to the original cluster center, and contains a low energy structure. We studied the stability of clusters for enzyme-inhibitor and antibody-antigen complexes in the Protein Docking Benchmark. The analysis yields three main results. First, all clusters that are close to the native structure are stable. Second, restricting considerations to stable clusters eliminates around half of the false positives, that is, solutions that are low in energy but far from the native structure of the complex. Third, dividing the conformational space into clusters and determining the stability of each cluster, the combined approach is less dependent on a priori information than exploring the potential conformational space by Monte Carlo minimizations.

An NMA-guided path planning approach for computing large-amplitude conformational changes in proteins

This paper presents a new method for computing macromolecular motions based on the combination of path planning algorithms, originating from robotics research, and elastic network normal mode analysis. The low-frequency normal modes are regarded as the collective degrees of freedom of the molecule. Geometric path planning algorithms are used to explore these collective degrees of freedom in order to find possible large-amplitude conformational changes. To overcome the limits of the harmonic approximation, which is valid in the vicinity of the minimum energy structure, and to get larger conformational changes, normal mode calculations are iterated during the exploration. Initial results show the efficiency of our method, which requires a small number of normal mode calculations to compute large-amplitude conformational transitions in proteins. A detailed analysis is presented for the computed transition between the open and closed structures of adenylate kinase. This transition, important for its biological function, involves large-amplitude domain motions. The obtained motion correlates well with results presented in related works.

Roadmap methods for protein folding

Protein folding refers to the process whereby a protein assumes its intricate three-dimensional shape. This chapter reviews a class of methods for studying the folding process called roadmap methods. The goal of these methods is not to predict the folded structure of a protein, but rather to analyze the folding kinetics. It is assumed that the folded state is known. Roadmap methods maintain a graph representation of sampled conformations. By analyzing this graph one can predict structure formation order, the probability of folding, and get a coarse view of the energy landscape.

Distributed Computation of the knn Graph for Large High-Dimensional Point Sets

High-dimensional problems arising from robot motion planning, biology, data mining, and geographic information systems often require the computation of k nearest neighbor (knn) graphs. The knn graph of a data set is obtained by connecting each point to its k closest points. As the research in the above-mentioned fields progressively addresses problems of unprecedented complexity, the demand for computing knn graphs based on arbitrary distance metrics and large high-dimensional data sets increases, exceeding resources available to a single machine. In this work we efficiently distribute the computation of knn graphs for clusters of processors with message passing. Extensions to our distributed framework include the computation of graphs based on other proximity queries, such as approximate knn or range queries. Our experiments show nearly linear speedup with over one hundred processors and indicate that similar speedup can be obtained with several hundred processors.

Modeling protein conformational ensembles: From missing loops to equilibrium fluctuations

Characterizing protein flexibility is an important goal for understanding the physical-chemical principles governing biological function. This paper presents a Fragment Ensemble Method to capture the mobility of a protein fragment such as a missing loop and its extension into a Protein Ensemble Method to characterize the mobility of an entire protein at equilibrium. The underlying approach in both methods is to combine a geometric exploration of conformational space with a statistical mechanics formulation to generate an ensemble of physical conformations on which thermodynamic quantities can be measured as ensemble averages. The Fragment Ensemble Method is validated by applying it to characterize loop mobility in both instances of strongly stable and disordered loop fragments. In each instance, fluctuations measured over generated ensembles are consistent with data from experiment and simulation. The Protein Ensemble Method captures the mobility of an entire protein by generating and combining ensembles of conformations for consecutive overlapping fragments defined over the protein sequence. This method is validated by applying it to characterize flexibility in ubiquitin and protein G. Thermodynamic quantities measured over the ensembles generated for both proteins are fully consistent with available experimental data. On these proteins, the method recovers nontrivial data such as order parameters, residual dipolar couplings, and scalar couplings. Results presented in this work suggest that the proposed methods can provide insight into the interplay between protein flexibility and function.

Framework models of ion permeation through membrane channels and the generalized King-Altman method

A modern approach to studying the detailed dynamics of biomolecules is to simulate them on computers. Framework models have been developed to incorporate information from these simulations in order to calculate properties of the biomolecules on much longer time scales than can be achieved by the simulations. They also provide a simple way to think about the simulated dynamics. This article develops a method for the solution of framework models, which generalizes the King-Altman method of enzyme kinetics. The generalized method is used to construct solutions of two framework models which have been introduced previously, the single-particle and Grotthuss (proton conduction) models. The solution of the Grotthuss model is greatly simplified in comparison with direct integration. In addition, a new framework model is introduced, generalizing the shaking stack model of ion conduction through the potassium channel.

One-Dimensional Free-Energy Profiles of Complex Systems: Progress Variables that Preserve the Barriers

We show that the balanced minimum-cut procedure introduced in PNAS 2004, 101, 14766 can be reinterpreted as a method for solving the constrained optimization problem of finding the minimum cut among the cuts with a particular value of an additive function of the nodes on either side of the cut. Such an additive function (e.g., the partition function of the reactant region) can be used as a progress coordinate to determine a one-dimensional profile (FEP) of the free-energy surface of the protein-folding reaction as well as other complex reactions. The algorithm is based on the network (obtained from an equilibrium molecular dynamics simulation) that represents the calculated reaction behavior. The resulting FEP gives the exact values of the free energy as a function of the progress coordinate; i.e., at each value of the progress coordinate, the profile is obtained from the surface with the minimal partition function among the surfaces that divide the full free-energy surface between two chosen end points. In many cases, the balanced minimum-cut procedure gives results for only a limited set of points. An approximate method based on p(fold) is shown to provide the profile for a more complete set of values of the progress coordinate. Applications of the approach to model problems and to realistic systems (beta-hairpin of protein G, LJ38 cluster) are presented.

Approximation of Protein Structure for Fast Similarity Measures

The structural comparison of two proteins comes up in many applications in structural biology where it is often necessary to find similarities in very large conformation sets. This work describes techniques to achieve significant speedup in the computation of structural similarity between two given conformations, at the expense of introducing a small error in the similarity measure. Furthermore, the proposed computational scheme allows for a tradeoff between speedup and error. This scheme exploits the fact that the Calpha representation of a protein conformation contains redundant information, due to the chain topology and limited compactness of proteins. This redundancy can be reduced by approximating subchains of a protein by their centers of mass, resulting in a smaller number of points to describe a conformation. A Haar wavelet analysis of random chains and proteins is used to justify this approximated representation. Similarity measures computed with this representation are highly correlated to the measures computed with the original Calpha representation. Therefore, they can be used in applications where small similarity errors can be tolerated or as fast filters in applications that require exact measures. Computational tests have been conducted on two applications, nearest neighbor search and automatic structural classification.