PLUG (Pruning of Local Unrealistic Geometries) removes restrictions on biophysical modeling for protein design.

Protein design algorithms must search an enormous conformational space to identify favorable conformations. As a result, those that perform this search with guarantees of accuracy generally start with a conformational pruning step, such as dead-end elimination (DEE). However, the mathematical assumptions of DEE-based pruning algorithms have up to now severely restricted the biophysical model that can feasibly be used in protein design. To lift these restrictions, I propose to prune local unrealistic geometries (PLUG) using a linear programming-based method. PLUG's biophysical model consists only of well-known lower bounds on interatomic distances. PLUG is intended as preprocessing for energy-based protein design calculations, whose biophysical model need not support DEE pruning. Based on 96 test cases, PLUG is at least as effective at pruning as DEE for larger protein designs-the type that most require pruning. When combined with the LUTE protein design algorithm, PLUG greatly facilitates designs that account for continuous entropy, large multistate designs with continuous flexibility, and designs with extensive continuous backbone flexibility and advanced nonpairwise energy functions. Many of these designs are tractable only with PLUG, either for empirical reasons (LUTE's machine learning step achieves an accurate fit only after PLUG pruning), or for theoretical reasons (many energy functions are fundamentally incompatible with DEE).

OSPREY 3.0: Open-source protein redesign for you, with powerful new features.

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.

CATS (Coordinates of Atoms by Taylor Series): protein design with backbone flexibility in all locally feasible directions.

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. AVAILABILITY AND IMPLEMENTATION: Our code is available as free software at https://github.com/donaldlab/OSPREY_refactor . CONTACT: mhallen@ttic.edu or brd+ismb17@cs.duke.edu. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

LUTE (Local Unpruned Tuple Expansion): Accurate Continuously Flexible Protein Design with General Energy Functions and Rigid Rotamer-Like Efficiency.

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.

cOSPREY: A Cloud-Based Distributed Algorithm for Large-Scale Computational Protein Design.

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.

comets (Constrained Optimization of Multistate Energies by Tree Search): A Provable and Efficient Protein Design Algorithm to Optimize Binding Affinity and Specificity with Respect to Sequence.

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.

Fast gap-free enumeration of conformations and sequences for protein design.

Despite significant successes in structure-based computational protein design in recent years, protein design algorithms must be improved to increase the biological accuracy of new designs. Protein design algorithms search through an exponential number of protein conformations, protein ensembles, and amino acid sequences in an attempt to find globally optimal structures with a desired biological function. To improve the biological accuracy of protein designs, it is necessary to increase both the amount of protein flexibility allowed during the search and the overall size of the design, while guaranteeing that the lowest-energy structures and sequences are found. DEE/A*-based algorithms are the most prevalent provable algorithms in the field of protein design and can provably enumerate a gap-free list of low-energy protein conformations, which is necessary for ensemble-based algorithms that predict protein binding. We present two classes of algorithmic improvements to the A* algorithm that greatly increase the efficiency of A*. First, we analyze the effect of ordering the expansion of mutable residue positions within the A* tree and present a dynamic residue ordering that reduces the number of A* nodes that must be visited during the search. Second, we propose new methods to improve the conformational bounds used to estimate the energies of partial conformations during the A* search. The residue ordering techniques and improved bounds can be combined for additional increases in A* efficiency. Our enhancements enable all A*-based methods to more fully search protein conformation space, which will ultimately improve the accuracy of complex biomedically relevant designs.

Crystal structure, conformational fixation and entry-related interactions of mature ligand-free HIV-1 Env.

As the sole viral antigen on the HIV-1-virion surface, trimeric Env is a focus of vaccine efforts. Here we present the structure of the ligand-free HIV-1-Env trimer, fix its conformation and determine its receptor interactions. Epitope analyses revealed trimeric ligand-free Env to be structurally compatible with broadly neutralizing antibodies but not poorly neutralizing ones. We coupled these compatibility considerations with binding antigenicity to engineer conformationally fixed Envs, including a 201C 433C (DS) variant specifically recognized by broadly neutralizing antibodies. DS-Env retained nanomolar affinity for the CD4 receptor, with which it formed an asymmetric intermediate: a closed trimer bound by a single CD4 without the typical antigenic hallmarks of CD4 induction. Antigenicity-guided structural design can thus be used both to delineate mechanism and to fix conformation, with DS-Env trimers in virus-like-particle and soluble formats providing a new generation of vaccine antigens.

Compact Representation of Continuous Energy Surfaces for More Efficient Protein Design.

In macromolecular design, conformational energies are sensitive to small changes in atom coordinates; thus, modeling the small, continuous motions of atoms around low-energy wells confers a substantial advantage in structural accuracy. However, modeling these motions comes at the cost of a very large number of energy function calls, which form the bottleneck in the design calculations. In this work, we remove this bottleneck by consolidating all conformational energy evaluations into the pre-computation of a local polynomial expansion of the energy about the "ideal" conformation for each low-energy, "rotameric" state of each residue pair. This expansion is called "energy as polynomials in internal coordinates" (EPIC), where the internal coordinates can be side-chain dihedrals, backrub angles, and/or any other continuous degrees of freedom of a macromolecule, and any energy function can be used without adding any asymptotic complexity to the design. We demonstrate that EPIC efficiently represents the energy surface for both molecular-mechanics and quantum-mechanical energy functions, and apply it specifically to protein design for modeling both side chain and backbone degrees of freedom.

Dead-end elimination with perturbations (DEEPer): a provable protein design algorithm with continuous sidechain and backbone flexibility.

Computational protein and drug design generally require accurate modeling of protein conformations. This modeling typically starts with an experimentally determined protein structure and considers possible conformational changes due to mutations or new ligands. The DEE/A* algorithm provably finds the global minimum-energy conformation (GMEC) of a protein assuming that the backbone does not move and the sidechains take on conformations from a set of discrete, experimentally observed conformations called rotamers. DEE/A* can efficiently find the overall GMEC for exponentially many mutant sequences. Previous improvements to DEE/A* include modeling ensembles of sidechain conformations and either continuous sidechain or backbone flexibility. We present a new algorithm, DEEPer (Dead-End Elimination with Perturbations), that combines these advantages and can also handle much more extensive backbone flexibility and backbone ensembles. DEEPer provably finds the GMEC or, if desired by the user, all conformations and sequences within a specified energy window of the GMEC. It includes the new abilities to handle arbitrarily large backbone perturbations and to generate ensembles of backbone conformations. It also incorporates the shear, an experimentally observed local backbone motion never before used in design. Additionally, we derive a new method to accelerate DEE/A*-based calculations, indirect pruning, that is particularly useful for DEEPer. In 67 benchmark tests on 64 proteins, DEEPer consistently identified lower-energy conformations than previous methods did, indicating more accurate modeling. Additional tests demonstrated its ability to incorporate larger, experimentally observed backbone conformational changes and to model realistic conformational ensembles. These capabilities provide significant advantages for modeling protein mutations and protein-ligand interactions.

Altered nucleotide-microtubule coupling and increased mechanical output by a kinesin mutant.

Kinesin motors hydrolyze ATP to produce force and do work in the cell--how the motors do this is not fully understood, but is thought to depend on the coupling of ATP hydrolysis to microtubule binding by the motor. Transmittal of conformational changes from the microtubule- to the nucleotide-binding site has been proposed to involve the central ß-sheet, which could undergo large structural changes important for force production. We show here that mutation of an invariant residue in loop L7 of the central ß-sheet of the Drosophila kinesin-14 Ncd motor alters both nucleotide and microtubule binding, although the mutated residue is not present in either site. Mutants show weak-ADP/tight-microtubule binding, instead of tight-ADP/weak-microtubule binding like wild type--they hydrolyze ATP faster than wild type, move faster in motility assays, and assemble long spindles with greatly elongated poles, which are also produced by simulations of assembly with tighter microtubule binding and faster sliding. The mutated residue acts like a mechanochemical coupling element--it transmits changes between the microtubule-binding and active sites, and can switch the state of the motor, increasing mechanical output by the motor. One possibility, based on our findings, is that movements by the residue and the loop that contains it could bend or distort the central ß-sheet, mediating free energy changes that lead to force production.

Computation of steady-state probability distributions in stochastic models of cellular networks.

Cellular processes are "noisy". In each cell, concentrations of molecules are subject to random fluctuations due to the small numbers of these molecules and to environmental perturbations. While noise varies with time, it is often measured at steady state, for example by flow cytometry. When interrogating aspects of a cellular network by such steady-state measurements of network components, a key need is to develop efficient methods to simulate and compute these distributions. We describe innovations in stochastic modeling coupled with approaches to this computational challenge: first, an approach to modeling intrinsic noise via solution of the chemical master equation, and second, a convolution technique to account for contributions of extrinsic noise. We show how these techniques can be combined in a streamlined procedure for evaluation of different sources of variability in a biochemical network. Evaluation and illustrations are given in analysis of two well-characterized synthetic gene circuits, as well as a signaling network underlying the mammalian cell cycle entry.

Mass spectrometry- and lysine amidination-based protocol for thermodynamic analysis of protein folding and ligand binding interactions.

Described here is a mass spectrometry-based covalent labeling protocol that utilizes the amine reactive reagent, s-methyl thioacetimidate (SMTA), to study the chemical denaturant-induced equilibrium unfolding/refolding properties of proteins and protein-ligand complexes in solution. The protocol, which involves evaluating the rate at which globally protected amine groups in a protein are modified with SMTA as a function of chemical denaturant concentration, is developed and applied to the analysis of eight protein samples including six purified protein samples (ubiquitin, BCAII, RNaseA, 4OT, and lysozyme with, and without GlcNAc), a five-protein mixture comprised of ubiquitin, BCAII, RNaseA, Cytochrome C, and lysozyme, and a yeast cell lysate. In ideal cases the folding free energies of proteins and the dissociation constants of protein-ligand complexes can be accurately evaluated using the protocol. A direct MALDI-TOF readout is demonstrated for analysis of purified protein samples. Bottom-up proteomic strategies involving gel-based and/or LC-MS-based shotgun proteomic platforms are also demonstrated for the analyses of complex protein samples. Analysis of proteins in a yeast cell lysate suggests the SMTA-labeling protocol expands the peptide and protein coverage in chemical modification- and shotgun proteomics-based strategies for making thermodynamic measurements of protein folding and stability on the proteomic scale.

Two-state displacement by the kinesin-14 Ncd stalk.

The nonprocessive kinesin-14 Ncd motor binds to microtubules and hydrolyzes ATP, undergoing a single displacement before releasing the microtubule. A lever-like rotation of the coiled-coil stalk is thought to drive Ncd displacements or steps along microtubules. Crystal structures and cryoelectron microscopy reconstructions imply that stalk rotation is correlated with ADP release and microtubule binding by the motor. Here we report FRET assays showing that the end of the stalk is more than ~9nm from the microtubule when wild-type Ncd binds microtubules without added nucleotide, but the stalk is within ~6nm of the microtubule surface when the microtubule-bound motor binds an ATP analogue, matching the rotated state observed in crystal structures. We propose that the stalk rotation is initiated when the motor binds to microtubules and releases ADP, and is completed when ATP binds.

Anastral spindle assembly and γ-tubulin in Drosophila oocytes.

BACKGROUND: Anastral spindles assemble by a mechanism that involves microtubule nucleation and growth from chromatin. It is still uncertain whether γ-tubulin, a microtubule nucleator essential for mitotic spindle assembly and maintenance, plays a role. Not only is the requirement for γ-tubulin to form anastral Drosophila oocyte meiosis I spindles controversial, but its presence in oocyte meiosis I spindles has not been demonstrated and is uncertain. RESULTS: We show, for the first time, using a bright GFP fusion protein and live imaging, that the Drosophila maternally-expressed γTub37C is present at low levels in oocyte meiosis I spindles. Despite this, we find that formation of bipolar meiosis I spindles does not require functional γTub37C, extending previous findings by others. Fluorescence photobleaching assays show rapid recovery of γTub37C in the meiosis I spindle, similar to the cytoplasm, indicating weak binding by γTub37C to spindles, and fits of a new, potentially more accurate model for fluorescence recovery yield kinetic parameters consistent with transient, diffusional binding. CONCLUSIONS: The FRAP results, together with its mutant effects late in meiosis I, indicate that γTub37C may perform a role subsequent to metaphase I, rather than nucleating microtubules for meiosis I spindle formation. Weak binding to the meiosis I spindle could stabilize pre-existing microtubules or position γ-tubulin for function during meiosis II spindle assembly, which follows rapidly upon oocyte activation and completion of the meiosis I division.

Expanding the scope of quantitative FRAP analysis.

In this study, new mathematical models were developed for analysis of fluorescence recovery after photobleaching (FRAP) data to account for features not represented in previous analysis: conical photobleaching geometry, spatial variations in binding of fluorescent molecules, and directed transport of fluorescent molecules. To facilitate computations in conical geometry, a fast computational method for calculation of fluorescence recovery is presented. Two approximations are presented to aid in FRAP analysis when binding varies spatially, one applying to cases of relatively fast diffusion and slow binding and the other to binding of molecules to small cellular structures. Numerical results show that using a model that represents the influential physical processes and that is formulated in the appropriate geometry can substantially improve the accuracy of FRAP calculations.

Anastral spindle assembly: a mathematical model.

Assembly of an anastral spindle was modeled as a two-stage process: first, the aggregation of microtubule foci or asters around the chromosomes, and second, the elongation of cross-linked microtubules and onset of bipolarity. Several possibilities involving diffusion and transport were investigated for the first stage, and the most feasible was found to be binding of the asters to cytoskeletal filaments and directed transport toward the chromosomes. For the second stage, a differential-equation model was formulated and solved numerically; it involves cross-linking of microtubules with those aligned with the spindle axis and between microtubules bound to different chromosomes, and sliding of microtubules along the spindle axis to elongate the spindle. Ncd was postulated to perform both functions. The model shows that spindle formation begins with rapid cross-linking of microtubules, followed by elongation, which continues until the population of microtubules aligned with the spindle axis is depleted and microtubules cross-linking different chromosomes dominate. It also shows that when sliding is inhibited, short bipolar spindles still form, and if clustering is enhanced, normal-length spindles can form, although requiring longer assembly time. These findings are consistent with spindle assembly in live wild-type and ncd mutant Drosophila oocytes.

Mature Drosophila meiosis I spindles comprise microtubules of mixed polarity.

New information has been obtained recently regarding microtubule organization in Xenopus extract spindles. These spindles assemble in vitro by chromatin-mediated microtubule nucleation and consist of randomly interspersed long and short microtubules with minus ends distributed throughout the spindle. Fluorescence speckle microscopy has led to the proposal that the Xenopus steady-state spindles contain two overlapping arrays of parallel or antiparallel microtubules with differing poleward-flux velocities. Although some of these features have also been reported for C. elegans female meiotic spindles, it is not clear whether they are representative of microtubule organization and dynamics in oocyte meiotic spindles. Here we examine anastral meiosis I spindles of live Drosophila oocytes expressing the microtubule plus end-tracking protein, EB1, fused to GFP, and find fluorescent particles throughout the spindle and movement toward both the poles and the equator. EB1 particle velocities, corresponding to microtubule growth rates, are similar in both directions, but slower than growth from the poles in mitotic spindles of early embryos. Meiosis I spindles yielded data from photobleaching analysis showing similar microtubule growth rates and dynamics at the poles and the equator, consistent with spindle microtubules of mixed polarity, differing from early-embryo mitotic spindles.

Ncd motor binding and transport in the spindle.

The Ncd kinesin-14 motor is required for meiotic spindle assembly in Drosophila oocytes and produces force in mitotic spindles that opposes other motors. Despite extensive studies, the way the motor binds to the spindle to perform its functions is not well understood. By analyzing Ncd deleted for the conserved head or the positively charged tail, we found that the tail is essential for binding to spindles and centrosomes, but both the head and tail are needed for normal spindle assembly and function. Fluorescence photobleaching assays to analyze binding interactions with the spindle yielded data for headless and full-length Ncd that did not fit well to previous recovery models. We report a new model that accounts for Ncd transport towards the equator revealed by fluorescence flow analysis of early mitotic spindles and gives rate constants that confirm the dominant role the Ncd tail plays in binding to the spindle. By contrast, the head binds weakly to spindles based on analysis of the tailless fluorescence recovery data. Minus-end Ncd thus binds tightly to spindles and is transported in early metaphase towards microtubule plus-ends, the opposite direction to that in which the motor moves, to produce force in the spindle later in mitosis.