Search

Motivation: When proteins mutate or bind to ligands, their backbones often move significantly, especially in loop regions. Computational protein design algorithms must model these motions in order to accurately optimize protein stability and binding affinity. However, methods for backbone conformational search in design have been much more limited than for sidechain conformational search. This is especially true for combinatorial protein design algorithms, which aim to search a large sequence space efficiently and thus cannot rely on temporal simulation of each candidate sequence. Results: We alleviate this difficulty with a new parameterization of backbone conformational space, which represents all degrees of freedom of a specified segment of protein chain that maintain valid bonding geometry (by maintaining the original bond lengths and angles and ω dihedrals). In order to search this space, we present an efficient algorithm, CATS, for computing atomic coordinates as a function of our new continuous backbone internal coordinates. CATS generalizes the iMinDEE and EPIC protein design algorithms, which model continuous flexibility in sidechain dihedrals, to model continuous, appropriately localized flexibility in the backbone dihedrals φ and ψ as well. We show using 81 test cases based on 29 different protein structures that CATS finds sequences and conformations that are significantly lower in energy than methods with less or no backbone flexibility do. In particular, we show that CATS can model the viability of an antibody mutation known experimentally to increase affinity, but that appears sterically infeasible when modeled with less or no backbone flexibility. [ABSTRACT FROM AUTHOR]

Practical protein design problems require designing sequences with a combination of affinity, stability, and specificity requirements. Multistate protein design algorithms model multiple structural or binding 'states' of a protein to address these requirements. comets provides a new level of versatile, efficient, and provable multistate design. It provably returns the minimum with respect to sequence of any desired linear combination of the energies of multiple protein states, subject to constraints on other linear combinations. Thus, it can target nearly any combination of affinity (to one or multiple ligands), specificity, and stability (for multiple states if needed). Empirical calculations on 52 protein design problems showed comets is far more efficient than the previous state of the art for provable multistate design (exhaustive search over sequences). comets can handle a very wide range of protein flexibility and can enumerate a gap-free list of the best constraint-satisfying sequences in order of objective function value. [ABSTRACT FROM AUTHOR]

Computational, in silico prediction of resistance-conferring escape mutations could accelerate the design of therapeutics less prone to resistance. This article describes how to use the Resistor algorithm to predict escape mutations. Resistor employs Pareto optimization on four resistance-conferring criteria—positive and negative design, mutational probability, and hotspot cardinality—to assign a Pareto rank to each prospective mutant. It also predicts the mechanism of resistance, that is, whether a mutant ablates binding to a drug, strengthens binding to the endogenous ligand, or a combination of these two factors, and provides structural models of the mutants. Resistor is part of the free and open-source computational protein design software OSPREY. [ABSTRACT FROM AUTHOR]

We present control strategies that implement planar microassembly using groups of stress-engineered MEMS microrobots (MicroStressBots) controlled through a single global control signal. The global control signal couples the motion of the devices, causing the system to be highly underactuated. In order for the robots to assemble into arbitrary planar shapes despite the high degree of underactuation, it is desirable that each robot be independently maneuverable (independently controllable). To achieve independent control, we fabricated robots that behave (move) differently from one another in response to the same global control signal. We harnessed this differentiation to develop assembly control strategies, where the assembly goal is a desired geometric shape that can be obtained by connecting the chassis of individual robots. We derived and experimentally tested assembly plans that command some of the robots to make progress toward the goal, while other robots are constrained to remain in small circular trajectories (orbits) until it is their turn to move into the goal shape.Our control strategies were tested on systems of fabricated MicroStressBots. The robots are 240–280 µm × 60 µm × 7–20 µm in size and move simultaneously within a single operating environment. We demonstrated the feasibility of our control scheme by accurately assembling five different types of planar microstructures. [ABSTRACT FROM AUTHOR]

We present designs, theory, and results of fabrication and testing for a novel parallel microrobotic assembly scheme using stress-engineered MEMS microrobots. The robots are 240-280 μm x 60 μm x 7-20 μm in size and can be controlled to dock compliantly together, forming planar structures several times this size. The devices are classified into species based on the design of their steering arm actuators, and the species are further classified as independent if they can be maneuvered independently using a single global control signal. In this paper, we show that microrobot species are independent if the two transition voltages of their steering arms, i.e., the voltages at which the arms are raised or lowered, form a unique pair. We present control algorithms that can be applied to groups of independent microrobot species to direct their motion from arbitrary nondeadlock configurations to desired planar microassemblies. We present designs and fabrication for four independent microrobot species, each with a unique transition voltage. The fabricated microrobots are used to demonstrate directed assembly of five types of planar structures from two classes of initial conditions. We demonstrate an average docking accuracy of 5 μm and use self-aligning compliant interaction between the microrobots to further align and stabilize the intermediate assemblies. The final assemblies match their target shapes on average 96%, by area. [ABSTRACT FROM AUTHOR]

We present an untethered, electrostatic, MEMS micro-robot, with dimensions of 60 µm by 250 µm by 10 µm. The device consists of a curved, cantilevered steering arm, mounted on an untethered scratch drive actuator (USDA). These two components are fabricated monolithically from the same sheet of conductive polysilicon, and receive a common power and control signal through a capacitive coupling with an underlying electrical grid. All locations on the grid receive the same power and control signal, so that the devices can be operated without knowledge of their position on the substrate. Individual control of the component actuators provides two distinct motion gaits (forward motion and turning), which together allow full coverage of a planar workspace. These MEMS micro-robots demonstrate turning error of less than 3.7°/mm during forward motion, turn with radii as small as 176 µm, and achieve speeds of over 200 µm/sec with an average step size as small as 12 nm. They have been shown to operate open-loop for distances exceeding 35 cm without failure, and can be controlled through teleoperation to navigate complex paths. The devices were fabricated through a multiuser surface micromachining process, and were postprocessed to add a patterned layer of tensile chromium, which curls the steering arms upward. After sacrificial release, the devices were transferred with a vacuum microprobe to the electrical grid for testing. This grid consists of a silicon substrate coated with 13-µm microfabricated electrodes, arranged in an interdigitated fashion with 2-µm spaces. The electrodes are insulated by a layer of electron-beam-evaporated zirconium dioxide, so that devices placed on top of the electrodes will experience an electrostatic force in response to an applied voltage. Control waveforms are broadcast to the device through the capacitive power coupling, and are decoded by the electromechanical response of the device body. Hysteresis in the system allows on-board storage of ii = 2 bits of state information in response to these electrical signals. The presence of on-board state information within the device itself allows each of the two device subsystems (USDA and steering arm) to be individually addressed and controlled. We describe this communication and control strategy and show necessary and sufficient conditions for voltage-selective actuation of all 2n system states, both for our devices (n = 2), and for the more general case (where n is larger.) [ABSTRACT FROM AUTHOR]

We consider the problem of planning and predicting the motion of a flexible object amid obstacles in the plane. We model the flexible object as a rigid "root" body attached to compliant members by torsional springs. The root's position may be controlled, but the compliant members move in response to forces from contact with the environment. Such a model encompasses several important and complicated mechanisms in mechanical design and automated assembly: snap-fasteners, latches, ratchet-and-pawl mechanisms, and escapements. The problem is to predict the motion of such a mechanism amid fixed obstacles. For example, our algorithm could be used to determine whether a snap-fastener design can be assembled with a certain plan. In this article we analyze the physics of these flexible devices and develop combinatorially precise algorithms for predicting their movement under a motion plan. Our algorithms determine when and where the motion will terminate and also. compute the time history of contacts and mating forces. In addition to providing the first known exact algorithm that addresses flexibility in motion planning, we also note that our approach to compliance permits an exact algorithm for predicting motions under rotational compliance, which was not possible in earlier work. We discuss the following issues: the relevance of our approach to engineering (which we illustrate through examples we ran using our system), the computational methods employed, the algebraic techniques for predicting motions in contact with rotational compliance, and issues of robustness and stability of our geometric and algebraic algorithms. Our computational viewpoint lies in the interface between differential theories of mechanics and combinatorial collision detection algorithms. From this viewpoint, subtle mathematical difficulties arise' in predicting motions under rotational compliance, such as the forced nongenericity of the intersection problems encountered in configuration spa... [ABSTRACT FROM AUTHOR]

Robots must plan and execute tasks in the presence of uncertainty. Uncertainty arises from sensing errors, control errors, and the geometry of the environment. By employing a combined strategy of force and position control, a robot programmer can often guarantee reaching the desired final configuration from all the likely initial configurations. Such motion strategies permit robots to carry out tasks in the presence of significant uncertainty. However, compliant motion strategies are very difficult for humans to specify. For this reason we have been working on the automatic synthesis of motion strategies for robots. In previous work (Donald 1988b; 1989), we presented a framework for computing one-step motion strategies that are guaranteed to succeed in the presence of all three kinds of uncertainty. The motion strategies comprise sensor-based gross motions, compliant motions, and simple pushing motions. However, it is not always possible to find plans that are guaranteed to succeed. For example, if tolerancing errors render an assembly infeasible, the plan executor should stop and signal failure. In such cases the insistence on guaranteed success is too restrictive. For this reason we investigate error detection and recovery (EDR) strategies. EDR plans will succeed or fail recognizably: in these more general strategies, there is no possibility that the plan will fail without the executor realizing it. The EDR framework fills a gap when guaranteed plans cannot be found or do not exist; it provides a technology for constructing plans that might work, but fail in a "reasonable" way when they cannot. We describe techniques for planning multi-step EDR strategies in the presence of uncertainty. Multi-step strategies are considerably more difficult to generate, and we introduce three approaches for their synthesis: these are the Push-forward Algorithm, Failure Mode Analysis, and the Weak EDR Theory. We have implemented the theory in the form of a planner, called ... [ABSTRACT FROM AUTHOR]

Computational protein design (CPD) algorithms that compute binding affinity, Ka, search for sequences with an energetically favorable free energy of binding. Recent work shows that three principles improve the biological accuracy of CPD: ensemble-based design , continuous flexibility of backbone and side-chain conformations, and provable guarantees of accuracy with respect to the input. However, previous methods that use all three design principles are single-sequence (SS) algorithms, which are very costly: linear in the number of sequences and thus exponential in the number of simultaneously mutable residues. To address this computational challenge, we introduce BBK* , a new CPD algorithm whose key innovation is the multisequence (MS) bound: BBK* efficiently computes a single provable upper bound to approximate Ka for a combinatorial number of sequences , and avoids SS computation for all provably suboptimal sequences. Thus, to our knowledge, BBK* is the first provable, ensemble-based CPD algorithm to run in time sublinear in the number of sequences. Computational experiments on 204 protein design problems show that BBK* finds the tightest binding sequences while approximating Ka for up to 105-fold fewer sequences than the previous state-of-the-art algorithms, which require exhaustive enumeration of sequences. Furthermore, for 51 protein–ligand design problems, BBK* provably approximates Ka up to 1982-fold faster than the previous state-of-the-art iMinDEE/ \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\curr A^*}$$ \end{document} / \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\curr K^*}$$ \end{document} algorithm. Therefore, BBK* not only accelerates protein designs that are possible with previous provable algorithms, but also efficiently performs designs that are too large for previous methods. [ABSTRACT FROM AUTHOR]

Most protein design algorithms search over discrete conformations and an energy function that is residue-pairwise, that is, a sum of terms that depend on the sequence and conformation of at most two residues. Although modeling of continuous flexibility and of non-residue-pairwise energies significantly increases the accuracy of protein design, previous methods to model these phenomena add a significant asymptotic cost to design calculations. We now remove this cost by modeling continuous flexibility and non-residue-pairwise energies in a form suitable for direct input to highly efficient, discrete combinatorial optimization algorithms such as DEE/A* or branch-width minimization. Our novel algorithm performs a local unpruned tuple expansion (LUTE), which can efficiently represent both continuous flexibility and general, possibly nonpairwise energy functions to an arbitrary level of accuracy using a discrete energy matrix. We show using 47 design calculation test cases that LUTE provides a dramatic speedup in both single-state and multistate continuously flexible designs. [ABSTRACT FROM AUTHOR]

Computational structure-based protein design programs are becoming an increasingly important tool in molecular biology. These programs compute protein sequences that are predicted to fold to a target structure and perform a desired function. The success of a program's predictions largely relies on two components: first, the input biophysical model, and second, the algorithm that computes the best sequence(s) and structure(s) according to the biophysical model. Improving both the model and the algorithm in tandem is essential to improving the success rate of current programs, and here we review recent developments in algorithms for protein design, emphasizing how novel algorithms enable the use of more accurate biophysical models. We conclude with a list of algorithmic challenges in computational protein design that we believe will be especially important for the design of therapeutic proteins and protein assemblies. [ABSTRACT FROM AUTHOR]

Antimicrobial resistance presents a significant health care crisis. The mutation F98Y in Staphylococcus aureus dihydrofolate reductase (SaDHFR) confers resistance to the clinically important antifolate trimethoprim (TMP). Propargyl-linked antifolates (PLAs), next generation DHFR inhibitors, are much more resilient than TMP against this F98Y variant, yet this F98Y substitution still reduces efficacy of these agents. Surprisingly, differences in the enantiomeric configuration at the stereogenic center of PLAs influence the isomeric state of the NADPH cofactor. To understand the molecular basis of F98Y-mediated resistance and how PLAs' inhibition drives NADPH isomeric states, we used protein design algorithms in the osprey protein design software suite to analyze a comprehensive suite of structural, biophysical, biochemical, and computational data. Here, we present a model showing how F98Y SaDHFR exploits a different anomeric configuration of NADPH to evade certain PLAs' inhibition, while other PLAs remain unaffected by this resistance mechanism. Author summary: Antimicrobial resistance is a major healthcare crisis. While we were developing novel enzyme inhibitors to combat methicillin-resistant Staphylococcus aureus (MRSA), we found that the chirality of both inhibitor and cofactor can have a large influence on inhibitor potency. Our detailed study of enantiomeric propargyl-linked antifolates (PLAs) shows that the chiral state of inhibitors can affect the chiral state of the cofactor. Moreover, the bacterial enzyme target can exploit cooperative chirality to evade inhibitor binding. We call this phenomenon chiral evasion. Using crystal structures, biochemical assays, computational protein design algorithms, and statistical mechanics, a detailed mechanism for chiral evasion is proposed. While the concept that different enantiomers have different biology is well known, MRSA is unique: we do not know of any other cases where a single mutation (F98Y) flips the chirality preference for cofactor binding and induces stereospecificity for drug binding. Thus, we illuminate the effect of this clinically relevant resistance mutation on the obligate cofactor binding site. These new insights will be useful to develop more durable antibiotics that are resilient to resistance. [ABSTRACT FROM AUTHOR]

Optimizing amino acid conformation and identity is a central problem in computational protein design. Protein design algorithms must allow realistic protein flexibility to occur during this optimization, or they may fail to find the best sequence with the lowest energy. Most design algorithms implement side-chain flexibility by allowing the side chains to move between a small set of discrete, low-energy states, which we call rigid rotamers. In this work we show that allowing continuous side-chain flexibility (which we call continuous rotamers) greatly improves protein flexibility modeling. We present a large-scale study that compares the sequences and best energy conformations in 69 protein-core redesigns using a rigid-rotamer model versus a continuous-rotamer model. We show that in nearly all of our redesigns the sequence found by the continuous-rotamer model is different and has a lower energy than the one found by the rigid-rotamer model. Moreover, the sequences found by the continuous-rotamer model are more similar to the native sequences. We then show that the seemingly easy solution of sampling more rigid rotamers within the continuous region is not a practical alternative to a continuous-rotamer model: at computationally feasible resolutions, using more rigid rotamers was never better than a continuous-rotamer model and almost always resulted in higher energies. Finally, we present a new protein design algorithm based on the dead-end elimination (DEE) algorithm, which we call iMinDEE, that makes the use of continuous rotamers feasible in larger systems. iMinDEE guarantees finding the optimal answer while pruning the search space with close to the same efficiency of DEE. Availability: Software is available under the Lesser GNU Public License v3. Contact the authors for source code [ABSTRACT FROM AUTHOR]

One of the main challenges for protein redesign is the efficient evaluation of a combinatorial number of candidate structures. The modeling of protein flexibility, typically by using a rotamer library of commonly-observed low-energy side-chain conformations, further increases the complexity of the redesign problem. A dominant algorithm for protein redesign is dead-end elimination (DEE), which prunes the majority of candidate conformations by eliminating rigid rotamers that provably are not part of the global minimum energy conformation (GMEC). The identified GMEC consists of rigid rotamers (i.e., rotamers that have not been energy-minimized) and is thus referred to as the rigid-GMEC. As a postprocessing step, the conformations that survive DEE may be energy-minimized. When energy minimization is performed after pruning with DEE, the combined protein design process becomes heuristic, and is no longer provably accurate: a conformation that is pruned using rigid-rotamer energies may subsequently minimize to a lower energy than the rigid-GMEC. That is, the rigid-GMEC and the conformation with the lowest energy among all energy-minimized conformations (the minimized-GMEC) are likely to be different. While the traditional DEE algorithm succeeds in not pruning rotamers that are part of the rigid-GMEC, it makes no guarantees regarding the identification of the minimized-GMEC. In this paper we derive a novel, provable, and efficient DEE-like algorithm, called minimized-DEE (MinDEE), that guarantees that rotamers belonging to the minimized-GMEC will not be pruned, while still pruning a combinatorial number of conformations. We show that MinDEE is useful not only in identifying the minimized-GMEC, but also as a filter in an ensemble-based scoring and search algorithm for protein redesign that exploits energy-minimized conformations. We compare our results both to our previous computational predictions of protein designs and to biological activity assays of predicted protein mutants. Our provable and efficient minimized-DEE algorithm is applicable in protein redesign, protein-ligand binding prediction, and computer-aided drug design. © 2008 Wiley Periodicals, Inc. J Comput Chem, 2008 [ABSTRACT FROM AUTHOR]

The K* algorithm provably approximates partition functions for a set of states (e.g., protein, ligand, and protein-ligand complex) to a user-specified accuracy ε. Often, reaching an ε-approximation for a particular set of partition functions takes a prohibitive amount of time and space. To alleviate some of this cost, we introduce two new algorithms into the osprey suite for protein design: fries, a Fast Removal of Inadequately Energied Sequences, and EWAK*, an Energy Window Approximation to K*. fries pre-processes the sequence space to limit a design to only the most stable, energetically favorable sequence possibilities. EWAK* then takes this pruned sequence space as input and, using a user-specified energy window, calculates K* scores using the lowest energy conformations. We expect fries/EWAK* to be most useful in cases where there are many unstable sequences in the design sequence space and when users are satisfied with enumerating the low-energy ensemble of conformations. In combination, these algorithms provably retain calculational accuracy while limiting the input sequence space and the conformations included in each partition function calculation to only the most energetically favorable, effectively reducing runtime while still enriching for desirable sequences. This combined approach led to significant speed-ups compared to the previous state-of-the-art multi-sequence algorithm, BBK*, while maintaining its efficiency and accuracy, which we show across 40 different protein systems and a total of 2,826 protein design problems. Additionally, as a proof of concept, we used these new algorithms to redesign the protein-protein interface (PPI) of the c-Raf-RBD:KRas complex. The Ras-binding domain of the protein kinase c-Raf (c-Raf-RBD) is the tightest known binder of KRas, a protein implicated in difficult-to-treat cancers. fries/EWAK* accurately retrospectively predicted the effect of 41 different sets of mutations in the PPI of the c-Raf-RBD:KRas complex. Notably, these mutations include mutations whose effect had previously been incorrectly predicted using other computational methods. Next, we used fries/EWAK* for prospective design and discovered a novel point mutation that improves binding of c-Raf-RBD to KRas in its active, GTP-bound state (KRasGTP). We combined this new mutation with two previously reported mutations (which were highly-ranked by osprey) to create a new variant of c-Raf-RBD, c-Raf-RBD(RKY). fries/EWAK* in osprey computationally predicted that this new variant binds even more tightly than the previous best-binding variant, c-Raf-RBD(RK). We measured the binding affinity of c-Raf-RBD(RKY) using a bio-layer interferometry (BLI) assay, and found that this new variant exhibits single-digit nanomolar affinity for KRasGTP, confirming the computational predictions made with fries/EWAK*. This new variant binds roughly five times more tightly than the previous best known binder and roughly 36 times more tightly than the design starting point (wild-type c-Raf-RBD). This study steps through the advancement and development of computational protein design by presenting theory, new algorithms, accurate retrospective designs, new prospective designs, and biochemical validation. Author summary: Computational structure-based protein design is an innovative tool for redesigning proteins to introduce a particular or novel function. One such function is improving the binding of one protein to another, which can increase our understanding of important protein systems. Herein we introduce two novel, provable algorithms, fries and EWAK*, for more efficient computational structure-based protein design as well as their application to the redesign of the c-Raf-RBD:KRas protein-protein interface. These new algorithms speed-up computational structure-based protein design while maintaining accurate calculations, allowing for larger, previously infeasible protein designs. Additionally, using fries and EWAK* within the osprey suite, we designed the tightest known binder of KRas, a heavily studied cancer target that interacts with a number of different proteins. This previously undiscovered variant of a KRas-binding domain, c-Raf-RBD, has potential to serve as a tool to further probe the protein-protein interface of KRas with its effectors and its discovery alone emphasizes the potential for more successful applications of computational structure-based protein design. [ABSTRACT FROM AUTHOR]

Protein design algorithms that model continuous sidechain flexibility and conformational ensembles better approximate the in vitro and in vivo behavior of proteins. The previous state of the art, iMinDEE-A*-K*, computes provable ɛ-approximations to partition functions of protein states (e.g., bound vs. unbound) by computing provable, admissible pairwise-minimized energy lower bounds on protein conformations, and using the A* enumeration algorithm to return a gap-free list of lowest-energy conformations. iMinDEE-A*-K* runs in time sublinear in the number of conformations, but can be trapped in loosely-bounded, low-energy conformational wells containing many conformations with highly similar energies. That is, iMinDEE-A*-K* is unable to exploit the correlation between protein conformation and energy: similar conformations often have similar energy. We introduce two new concepts that exploit this correlation: Minimization-Aware Enumeration and Recursive K*. We combine these two insights into a novel algorithm, Minimization-Aware Recursive K* (MARK*), which tightens bounds not on single conformations, but instead on distinct regions of the conformation space. We compare the performance of iMinDEE-A*-K* versus MARK* by running the Branch and Bound over K* (BBK*) algorithm, which provably returns sequences in order of decreasing K* score, using either iMinDEE-A*-K* or MARK* to approximate partition functions. We show on 200 design problems that MARK* not only enumerates and minimizes vastly fewer conformations than the previous state of the art, but also runs up to 2 orders of magnitude faster. Finally, we show that MARK* not only efficiently approximates the partition function, but also provably approximates the energy landscape. To our knowledge, MARK* is the first algorithm to do so. We use MARK* to analyze the change in energy landscape of the bound and unbound states of an HIV-1 capsid protein C-terminal domain in complex with a camelid VHH, and measure the change in conformational entropy induced by binding. Thus, MARK* both accelerates existing designs and offers new capabilities not possible with previous algorithms. [ABSTRACT FROM AUTHOR]

We present osprey 3.0, a new and greatly improved release of the osprey protein design software. Osprey 3.0 features a convenient new Python interface, which greatly improves its ease of use. It is over two orders of magnitude faster than previous versions of osprey when running the same algorithms on the same hardware. Moreover, osprey 3.0 includes several new algorithms, which introduce substantial speedups as well as improved biophysical modeling. It also includes GPU support, which provides an additional speedup of over an order of magnitude. Like previous versions of osprey, osprey 3.0 offers a unique package of advantages over other design software, including provable design algorithms that account for continuous flexibility during design and model conformational entropy. Finally, we show here empirically that osprey 3.0 accurately predicts the effect of mutations on protein–protein binding. Osprey 3.0 is available at http://www.cs.duke.edu/donaldlab/osprey.php as free and open‐source software. © 2018 Wiley Periodicals, Inc. We present the third major release of the OSPREY protein design software, along with comparisons to experimental data that confirm its ability to optimize protein mutants for desired functions. Osprey 3.0 has significant efficiency, ease‐of‐use, and algorithmic improvements over previous versions, including GPU acceleration and a new Python interface. [ABSTRACT FROM AUTHOR]

The flexibility of biological macromolecules is an important structural determinant of function. Unfortunately, the correlations between different motional modes are poorly captured by discrete ensemble representations. Here, we present new ways to both represent and visualize correlated interdomain motions. Interdomain motions are determined directly from residual dipolar couplings, represented as a continuous conformational distribution, and visualized using the disk-on-sphere representation. Using the disk-on-sphere representation, features of interdomain motions, including correlations, are intuitively visualized. The representation works especially well for multidomain systems with broad conformational distributions.This analysis also can be extended to multiple probability density modes, using a Bingham mixture model. We use this new paradigm to study the interdomain motions of staphylococcal protein A, which is a key virulence factor contributing to the pathogenicity of Staphylococcus aureus . We capture the smooth transitions between important states and demonstrate the utility of continuous distribution functions for computing the reorientational components of binding thermodynamics. Such insights allow for the dissection of the dynamic structural components of functionally important intermolecular interactions. [ABSTRACT FROM AUTHOR]

Protein design algorithms enumerate a combinatorial number of candidate structures to compute the Global Minimum Energy Conformation (GMEC). To efficiently find the GMEC, protein design algorithms must methodically reduce the conformational search space. By applying distance and energy cutoffs, the protein system to be designed can thus be represented using a sparse residue interaction graph, where the number of interacting residue pairs is less than all pairs of mutable residues, and the corresponding GMEC is called the sparse GMEC. However, ignoring some pairwise residue interactions can lead to a change in the energy, conformation, or sequence of the sparse GMEC vs. the original or the full GMEC. Despite the widespread use of sparse residue interaction graphs in protein design, the above mentioned effects of their use have not been previously analyzed. To analyze the costs and benefits of designing with sparse residue interaction graphs, we computed the GMECs for 136 different protein design problems both with and without distance and energy cutoffs, and compared their energies, conformations, and sequences. Our analysis shows that the differences between the GMECs depend critically on whether or not the design includes core, boundary, or surface residues. Moreover, neglecting long-range interactions can alter local interactions and introduce large sequence differences, both of which can result in significant structural and functional changes. Designs on proteins with experimentally measured thermostability show it is beneficial to compute both the full and the sparse GMEC accurately and efficiently. To this end, we show that a provable, ensemble-based algorithm can efficiently compute both GMECs by enumerating a small number of conformations, usually fewer than 1000. This provides a novel way to combine sparse residue interaction graphs with provable, ensemble-based algorithms to reap the benefits of sparse residue interaction graphs while avoiding their potential inaccuracies. [ABSTRACT FROM AUTHOR]

Finding the global minimum energy conformation (GMEC) of a huge combinatorial search space is the key challenge in computational protein design (CPD) problems. Traditional algorithms lack a scalable and efficient distributed design scheme, preventing researchers from taking full advantage of current cloud infrastructures. We design cloud OSPREY (cOSPREY), an extension to a widely used protein design software OSPREY, to allow the original design framework to scale to the commercial cloud infrastructures. We propose several novel designs to integrate both algorithm and system optimizations, such as GMEC-specific pruning, state search partitioning, asynchronous algorithm state sharing, and fault tolerance. We evaluate cOSPREY on three different cloud platforms using different technologies and show that it can solve a number of large-scale protein design problems that have not been possible with previous approaches. [ABSTRACT FROM AUTHOR]

Sparse energy functions that ignore long range interactions between residue pairs are frequently used by protein design algorithms to reduce computational cost. Current dynamic programming algorithms that fully exploit the optimal substructure produced by these energy functions only compute the GMEC. This disproportionately favors the sequence of a single, static conformation and overlooks better binding sequences with multiple low-energy conformations. Provable, ensemble-based algorithms such as A* avoid this problem, but A* cannot guarantee better performance than exhaustive enumeration. We propose a novel, provable, dynamic programming algorithm called Branch-Width Minimization* (BWM*) to enumerate a gap-free ensemble of conformations in order of increasing energy. Given a branch-decomposition of branch-width w for an n-residue protein design with at most q discrete side-chain conformations per residue, BWM* returns the sparse GMEC in O(nw²q3/2w) time and enumerates each additional conformation in merely O(n log q) time. We define a new measure, Total Effective Search Space (TESS), which can be computed efficiently a priori before BWM* or A* is run. We ran BWM* on 67 protein design problems and found that TESS discriminated between BWM*-efficient and A*- efficient cases with 100% accuracy. As predicted by TESS and validated experimentally, BWM* outperforms A* in 73% of the cases and computes the full ensemble or a close approximation faster than A*, enumerating each additional conformation in milliseconds. Unlike A*, the performance of BWM* can be predicted in polynomial time before running the algorithm, which gives protein designers the power to choose the most efficient algorithm for their particular design problem. [ABSTRACT FROM AUTHOR]

One of the main challenges in computational protein design (CPD) is the huge size of the protein sequence and conformational space that has to be computationally explored. Recently, we showed that state-of-the-art combinatorial optimization technologies based on Cost Function Network (CFN) processing allow speeding up provable rigid backbone protein design methods by several orders of magnitudes. Building up on this, we improved and injected CFN technology into the well-established CPD package Osprey to allow all Osprey CPD algorithms to benefit from associated speedups. Because Osprey fundamentally relies on the ability of [ABSTRACT FROM AUTHOR]

Examines the crystal structure of dihydrofolate reductase-thymidylate synthase (DHFR-TS) from Cryptosporidium hominis. Association between DHFR and TS domains; Importance of the linker polypeptide between the structural interaction of DHFR and TS; Residue substitutions between DHFR-TS of C. homonis and C. parvum.

The membrane proximal external region (MPER) of HIV-1 glycoprotein (gp) 41 is involved in viral-host cell membrane fusion. It contains short amino acid sequences that are binding sites for the HIV-1 broadly neutralizing antibodies 2F5, 4E10, and 10E8, making these binding sites important targets for HIV-1 vaccine development. We report a high-resolution structure of a designed MPER trimer assembled on a detergent micelle. The NMR solution structure of this trimeric domain, designated gp41-M-MAT, shows that the three MPER peptides each adopt symmetric a-helical conformations exposing the amino acid side chains of the antibody binding sites. The helices are closely associated at their N termini, bend between the 2F5 and 4E10 epitopes, and gradually separate toward the C termini, where they associate with the membrane. The mAbs 2F5 and 4E10 bind gp41-M-MAT with nanomolar affinities, consistent with the substantial exposure of their respective epitopes in the trimer structure. The traditional structure determination of gp41-M-MAT using the Xplor-NIH protocol was validated by independently determining the structure using the DISCO sparse-data protocol, which exploits geometric arrangement algorithms that guarantee to compute all structures and assignments that satisfy the data. [ABSTRACT FROM AUTHOR]

Motivation: Structure-based computational protein design (SCPR) is an important topic in protein engineering. Under the assumption of a rigid backbone and a finite set of discrete conformations of side-chains, various methods have been proposed to address this problem. A popular method is to combine the dead-end elimination (DEE) and A* tree search algorithms, which provably finds the global minimum energy conformation (GMEC) solution.Results: In this article, we improve the efficiency of computing A* heuristic functions for protein design and propose a variant of A* algorithm in which the search process can be performed on a single GPU in a massively parallel fashion. In addition, we make some efforts to address the memory exceeding problem in A* search. As a result, our enhancements can achieve a significant speedup of the A*-based protein design algorithm by four orders of magnitude on large-scale test data through pre-computation and parallelization, while still maintaining an acceptable memory overhead. We also show that our parallel A* search algorithm could be successfully combined with iMinDEE, a state-of-the-art DEE criterion, for rotamer pruning to further improve SCPR with the consideration of continuous side-chain flexibility.Availability: Our software is available and distributed open-source under the GNU Lesser General License Version 2.1 (GNU, February 1999). The source code can be downloaded from http://www.cs.duke.edu/donaldlab/osprey.php or http://iiis.tsinghua.edu.cn/∼compbio/software.html.Contact: zengjy321@tsinghua.edu.cnSupplementary information: Supplementary data are available at Bioinformatics online. [ABSTRACT FROM PUBLISHER]

The computational complexity of the brain depends in part on a neuron’s capacity to integrate electrochemical information from vast numbers of synaptic inputs. The measurements of synaptic activity that are crucial for mechanistic understanding of brain function are also challenging, because they require intracellular recording methods to detect and resolve millivolt- scale synaptic potentials. Although glass electrodes are widely used for intracellular recordings, novel electrodes with superior mechanical and electrical properties are desirable, because they could extend intracellular recording methods to challenging environments, including long term recordings in freely behaving animals. Carbon nanotubes (CNTs) can theoretically deliver this advance, but the difficulty of assembling CNTs has limited their application to a coating layer or assembly on a planar substrate, resulting in electrodes that are more suitable for in vivo extracellular recording or extracellular recording from isolated cells. Here we show that a novel, yet remarkably simple, millimeter-long electrode with a sub-micron tip, fabricated from self-entangled pure CNTs can be used to obtain intracellular and extracellular recordings from vertebrate neurons in vitro and in vivo. This fabrication technology provides a new method for assembling intracellular electrodes from CNTs, affording a promising opportunity to harness nanotechnology for neuroscience applications. [ABSTRACT FROM AUTHOR]

Amino acid substitutions in protein structures often require subtle backbone adjustments that are difficult to model in atomic detail. An improved ability to predict realistic backbone changes in response to engineered mutations would be of great utility for the blossoming field of rational protein design. One model that has recently grown in acceptance is the backrub motion, a low-energy dipeptide rotation with single-peptide counter-rotations, that is coupled to dynamic twostate sidechain rotamer jumps, as evidenced by alternate conformations in very high-resolution crystal structures. It has been speculated that backrubs may facilitate sequence changes equally well as rotamer changes. However, backrubinduced shifts and experimental uncertainty are of similar magnitude for backbone atoms in even high-resolution structures, so comparison of wildtype-vs.-mutant crystal structure pairs is not sufficient to directly link backrubs to mutations. In this study, we use two alternative approaches that bypass this limitation. First, we use a quality-filtered structure database to aggregate many examples for precisely defined motifs with single amino acid differences, and find that the effectively amplified backbone differences closely resemble backrubs. Second, we directly apply a provablyaccurate, backrub-enabled protein design algorithm to idealized versions of these motifs, and discover that the lowestenergy computed models match the average-coordinate experimental structures. These results support the hypothesis that backrubs participate in natural protein evolution and validate their continued use for design of synthetic proteins. [ABSTRACT FROM AUTHOR]

The cystic fibrosis transmembrane conductance regulator (CFTR) is an epithelial chloride channel mutated in patients with cystic fibrosis (CF). The most prevalent CFTR mutation, DF508, blocks folding in the endoplasmic reticulum. Recent work has shown that some DF508-CFTR channel activity can be recovered by pharmaceutical modulators (''potentiators'' and ''correctors''), but DF508-CFTR can still be rapidly degraded via a lysosomal pathway involving the CFTR-associated ligand (CAL), which binds CFTR via a PDZ interaction domain. We present a study that goes from theory, to new structure-based computational design algorithms, to computational predictions, to biochemical testing and ultimately to epithelial-cell validation of novel, effective CAL PDZ inhibitors (called ''stabilizers'') that rescue DF508-CFTR activity. To design the ''stabilizers'', we extended our structural ensemble-based computational protein redesign algorithm K to encompass protein-protein and protein-peptide interactions. The computational predictions achieved high accuracy: all of the toppredicted peptide inhibitors bound well to CAL. Furthermore, when compared to state-of-the-art CAL inhibitors, our design methodology achieved higher affinity and increased binding efficiency. The designed inhibitor with the highest affinity for CAL (kCAL01) binds six-fold more tightly than the previous best hexamer (iCAL35), and 170-fold more tightly than the CFTR C-terminus. We show that kCAL01 has physiological activity and can rescue chloride efflux in CF patient-derived airway epithelial cells. Since stabilizers address a different cellular CF defect from potentiators and correctors, our inhibitors provide an additional therapeutic pathway that can be used in conjunction with current methods. [ABSTRACT FROM AUTHOR]

Symmetric homo-oligomers represent a majority of proteins, and determining their structures helps elucidate important biological processes, including ion transport, signal transduction, and transcriptional regulation. In order to account for the noise and sparsity in the distance restraints used in Nuclear Magnetic Resonance (NMR) structure determination of cyclic (C n) symmetric homo-oligomers, and the resulting uncertainty in the determined structures, we develop a Bayesian structural inference approach. In contrast to traditional NMR structure determination methods, which identify a small set of low-energy conformations, the inferential approach characterizes the entire posterior distribution of conformations. Unfortunately, traditional stochastic techniques for inference may under-sample the rugged landscape of the posterior, missing important contributions from high-quality individual conformations and not accounting for the possible aggregate effects on inferred quantities from numerous unsampled conformations. However, by exploiting the geometry of symmetric homo-oligomers, we develop an algorithm that provides provable guarantees for the posterior distribution and the inferred mean atomic coordinates. Using experimental restraints for three proteins, we demonstrate that our approach is able to objectively characterize the structural diversity supported by the data. By simulating spurious and missing restraints, we further demonstrate that our approach is robust, degrading smoothly with noise and sparsity. [ABSTRACT FROM AUTHOR]

Nuclear magnetic resonance (NMR) spectroscopy is a primary tool to perform structural studies of proteins in physiologically-relevant solution conditions. Restraints on distances between pairs of nuclei in the protein, derived from the nuclear Overhauser effect (NOE), provide information about the structure of the protein in its folded state. NMR studies of symmetric protein homo-oligomers present a unique challenge. Using X-filtered NOESY experiments, it is possible to determine whether an NOE restrains a pair of protons across different subunits or within a single subunit, but current experimental techniques are unable to determine in which subunits the restrained protons lie. Consequently, it is difficult to assign NOEs to particular pairs of subunits with certainty, thus hindering the structural analysis of the oligomeric state. Computational approaches are needed to address this subunit ambiguity, but traditional solutions often rely on stochastic search coupled with simulated annealing and simulations of simplified molecular dynamics, which have many tunable parameters that must be chosen carefully and can also fail to report structures consistent with the experimental restraints. In addition, these traditional approaches rarely provide guarantees on running time or solution quality. We reduce the structure determination of homo-oligomers with cyclic symmetry to computing geometric arrangements of unions of annuli in a plane. Our algorithm, disco, runs in expected O( n2) time, where n is the number of distance restraints, potentially assigned ambiguously. disco is guaranteed to report the exact set of oligomer structures consistent with the distance restraints and also with orientational restraints from residual dipolar couplings (RDCs). We demonstrate our method using two symmetric protein complexes: the trimeric E. coli diacylglycerol kinase (DAGK) and a dimeric mutant of the immunoglobulin-binding domain B1 of streptococcal protein G (GB1). In both cases, disco computes oligomer structures with high precision and also finds distance restraints that are either mutually inconsistent or inconsistent with the RDCs. The entire protocol DISCO has been completely automated in a software package that is freely available and open-source at . [ABSTRACT FROM AUTHOR]

Nuclear magnetic resonance (NMR) spectroscopy is an important experimental technique that allows one to study protein structure and dynamics in solution. An important bottleneck in NMR protein structure determination is the assignment of NMR peaks to the corresponding nuclei. Structure-based assignment (SBA) aims to solve this problem with the help of a template protein which is homologous to the target and has applications in the study of structure–activity relationship, protein–protein and protein–ligand interactions. We formulate SBA as a linear assignment problem with additional nuclear overhauser effect constraints, which can be solved within nuclear vector replacement's (NVR) framework (Langmead, C., Yan, A., Lilien, R., Wang, L. and Donald, B. (2003) A Polynomial-Time Nuclear Vector Replacement Algorithm for Automated NMR Resonance Assignments. Proc. the 7th Annual Int. Conf. Research in Computational Molecular Biology (RECOMB), Berlin, Germany, April 10–13, pp. 176–187. ACM Press, New York, NY. J. Comp. Bio., (2004), 11, pp. 277–298; Langmead, C. and Donald, B. (2004) An expectation/maximization nuclear vector replacement algorithm for automated NMR resonance assignments. J. Biomol. NMR, 29, 111–138). Our approach uses NVR's scoring function and data types and also gives the option of using CH and NH residual dipolar coupling (RDCs), instead of NH RDCs which NVR requires. We test our technique on NVR's data set as well as on four new proteins. Our results are comparable to NVR's assignment accuracy on NVR's test set, but higher on novel proteins. Our approach allows partial assignments. It is also complete and can return the optimum as well as near-optimum assignments. Furthermore, it allows us to analyze the information content of each data type and is easily extendable to accept new forms of input data, such as additional RDCs. [ABSTRACT FROM AUTHOR]

We report a computational, structure-based redesign of the phenylalanine adenylation domain of the nonribosomal peptide synthetase enzyme gramicidin S synthetase A (GrsA-PheA) for a set of noncognate substrates for which the wild-type enzyme has little or virtually no specificity. Experimental validation of a set of top- ranked computationally predicted enzyme mutants shows significant improvement in the specificity for the target substrates. We further present enhancements to the methodology for computational enzyme redesign that are experimentally shown to result in significant additional improvements in the target substrate specificity. The mutant with the highest activity for a noncognate substrate exhibits 1/6 of the wild-type enzyme/wild-type substrate activity, further confirming the feasibility of our computational approach. Our results suggest that structure-based protein design can identify active mutants different from those selected by evolution. [ABSTRACT FROM AUTHOR]

Summary: The two subunits of core binding factor (Runx1 and CBFβ) play critical roles in hematopoiesis and are frequent targets of chromosomal translocations found in leukemia. The binding of the CBFβ-smooth muscle myosin heavy chain (SMMHC) fusion protein to Runx1 is essential for leukemogenesis, making this a viable target for treatment. We have developed inhibitors with low micromolar affinity which effectively block binding of Runx1 to CBFβ. NMR-based docking shows that these compounds bind to CBFβ at a site displaced from the binding interface for Runx1, that is, these compounds function as allosteric inhibitors of this protein-protein interaction, a potentially generalizable approach. Treatment of the human leukemia cell line ME-1 with these compounds shows decreased proliferation, indicating these are good candidates for further development. [Copyright &y& Elsevier]

The PheA domain of gramicidin synthetase A, a non-ribosomal peptide synthetase, selectively binds phenylalanine along with ATP and Mg2+ and catalyzes the formation of an aminoacyl adenylate. In this study, we have used a novel protein redesign algorithm, K*, to predict mutations in PheA that should exhibit improved binding for tyrosine. Interestingly, the introduction of two predicted mutations to PheA did not significantly improve KD, as measured by equilibrium fluorescence quenching. However, the mutations improved the specificity of the enzyme for tyrosine (as measured by kcat/KM), primarily driven by a 56-fold improvement in KM, although the improvement did not make tyrosine the preferred substrate over phenylalanine. Using stopped-flow fluorometry, we examined binding of different amino acid substrates to the wild-type and mutant enzymes in the pre-steady state in order to understand the improvement in KM. Through these investigations, it became evident that substrate binding to the wild-type enzyme is more complex than previously described. These experiments show that the wild-type enzyme binds phenylalanine in a kinetically selective manner; no other amino acids tested appeared to bind the enzyme in the early time frame examined (500 ms). Furthermore, experiments with PheA, phenylalanine, and ATP reveal a two-step binding process, suggesting that the PheA-ATP-phenylalanine complex may undergo a conformational change toward a catalytically relevant intermediate on the pathway to adenylation; experiments with PheA, phenylalanine, and other nucleotides exhibit only a one-step binding process. The improvement in KM for the mutant enzyme toward tyrosine, as predicted by K*, may indicate that redesigning the side-chain binding pocket allows the substrate backbone to adopt productive conformations for catalysis but that further improvements may be afforded by modeling an enzyme:ATP: substrate complex, which is capable of undergoing conformational change. [ABSTRACT FROM AUTHOR]

Molecular replacement (MR) often plays a prominent role in determining initial phase angles for structure determination by X-ray crystallography. In this paper, an efficient quaternion-based algorithm is presented for analyzing peaks from a cross-rotation function in order to identify model orientations consistent with proper non-crystallographic symmetry (NCS) and to generate proper NCS-consistent orientations missing from the list of cross-rotation peaks. The algorithm, CRANS, analyzes the rotation differences between each pair of cross-rotation peaks to identify finite subgroups. Sets of rotation differences satisfying the subgroup axioms correspond to orientations compatible with the correct proper NCS. The CRANS algorithm was first tested using cross-rotation peaks computed from structure-factor data for three test systems and was then used to assist in the de novo structure determination of dihydrofolate reductase-thymidylate synthase (DHFR-TS) from Cryptosporidium hominis. In every case, the CRANS algorithm runs in seconds to identify orientations consistent with the observed proper NCS and to generate missing orientations not present in the cross-rotation peak list. The CRANS algorithm has application in every molecular-replacement phasing effort with proper NCS. [ABSTRACT FROM AUTHOR]