Search

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 [micro]m x 60 [micro]m x 7-20 [micro]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 [micro]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. Index Terms--Microactuators, microassembly, microelectromechanical systems (MEMS), microrobots, scratch-drive actuators.

A novel protein redesign algorithm, [K.sup.}, is used to predict mutations in PheA that displays improved binding for tyrosine. The pre-steady-state experiments have indicated that PheA-ATP and phenylalanine initially collide and then undergo a second event, possibly a conformational change.

We present an untethered, electrostatic, MEMS micro-robot, with dimensions of 60 [micro]m by 250 [micro]m by 10 [micro]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[degrees]/mm during forward motion, turn with radii as small as 176 [micro]m, and achieve speeds of over 200 [micro]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-[micro]m microfabricated electrodes, arranged in an interdigitated fashion with 2-[micro]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 n = 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 [2.sup.n] system states, both for our devices (n = 2), and for the more general case (where n is larger.) [1586] Index Terms--Actuator, control, electrostatic, fabrication, locomotion, MEMS, micro-robot, PolyMUMPS, robotics, scrath-drive, steering, untethered.

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]

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]

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 first micromachined bimorph organic ciliary array with on-chip CMOS circuitry is presented. This ciliary array is composed of an 8 x 8 array of cells each having four orthogonally oriented actuators in an overall die size of 9.4 x 9.4 mm. The polyimide-based actuators were fabricated directly above the selection and drive circuitry. Selection and activation of actuators in this array shows that integration was successful. The array was programmed to do simple linear and diagonal translations and squeeze-, centering-, and rotating-field manipulations. All three tasks were demonstrated using silicon pieces of various shapes and either 0.55 mm or 0.10 mm thick. [365] Index Terms--Actuator, array, CMOS, integration, micromanipulation, polyimide.

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]

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]

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]

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]

ABSTRACT 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. Proteins 2015; 83:1859-1877. © 2015 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

ABSTRACT Flexibility and dynamics are important for protein function and a protein's ability to accommodate amino acid substitutions. However, when computational protein design algorithms search over protein structures, the allowed flexibility is often reduced to a relatively small set of discrete side-chain and backbone conformations. While simplifications in scoring functions and protein flexibility are currently necessary to computationally search the vast protein sequence and conformational space, a rigid representation of a protein causes the search to become brittle and miss low-energy structures. Continuous rotamers more closely represent the allowed movement of a side chain within its torsional well and have been successfully incorporated into the protein design framework to design biomedically relevant protein systems. The use of continuous rotamers in protein design enables algorithms to search a larger conformational space than previously possible, but adds additional complexity to the design search. To design large, complex systems with continuous rotamers, new algorithms are needed to increase the efficiency of the search. We present two methods, PartCR and HOT, that greatly increase the speed and efficiency of protein design with continuous rotamers. These methods specifically target the large errors in energetic terms that are used to bound pairwise energies during the design search. By tightening the energy bounds, additional pruning of the conformation space can be achieved, and the number of conformations that must be enumerated to find the global minimum energy conformation is greatly reduced. Proteins 2015; 83:1151-1164. © 2015 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

ABSTRACT Protein structure determination by NMR has predominantly relied on simulated annealing-based conformational search for a converged fold using primarily distance constraints, including constraints derived from nuclear Overhauser effects, paramagnetic relaxation enhancement, and cysteine crosslinkings. Although there is no guarantee that the converged fold represents the global minimum of the conformational space, it is generally accepted that good convergence is synonymous to the global minimum. Here, we show such a criterion breaks down in the presence of large numbers of ambiguous constraints from NMR experiments on homo-oligomeric protein complexes. A systematic evaluation of the conformational solutions that satisfy the NMR constraints of a trimeric membrane protein, DAGK, reveals 9 distinct folds, including the reported NMR and crystal structures. This result highlights the fundamental limitation of global fold determination for homo-oligomeric proteins using ambiguous distance constraints and provides a systematic solution for exhaustive enumeration of all satisfying solutions. Proteins 2015; 83:651-661. © 2015 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

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]

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]

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. Proteins 2013. © 2012 Wiley Periodicals, Inc. [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]

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]

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]

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]

Structural studies of symmetric homo-oligomers provide mechanistic insights into their roles in essential biological processes, including cell signaling and cellular regulation. This paper presents a novel algorithm for homo-oligomeric structure determination, given the subunit structure, that is both complete, in that it evaluates all possible conformations, and data-driven, in that it evaluates conformations separately for consistency with experimental data and for quality of packing. Completeness ensures that the algorithm does not miss the native conformation, and being data-driven enables it to assess the structural precision possible from data alone. Our algorithm performs a branch-and-bound search in the symmetry configuration space, the space of symmetry axis parameters (positions and orientations) defining all possible Cn homo-oligomeric complexes for a given subunit structure. It eliminates those symmetry axes inconsistent with intersubunit nuclear Overhauser effect (NOE) distance restraints and then identifies conformations representing any consistent, well-packed structure to within a user-defined similarity level. For the human phospholamban pentamer in dodecylphosphocholine micelles, using the structure of one subunit determined from a subset of the experimental NMR data, our algorithm identifies a diverse set of complex structures consistent with the nine intersubunit NOE restraints. The distribution of determined structures provides an objective characterization of structural uncertainty: backbone RMSD to the previously determined structure ranges from 1.07 to 8.85 Å, and variance in backbone atomic coordinates is an average of 12.32 Å2. Incorporating vdW packing reduces structural diversity to a maximum backbone RMSD of 6.24 Å and an average backbone variance of 6.80 Å2. By comparing data consistency and packing quality under different assumptions of oligomeric number, our algorithm identifies the pentamer as the most likely oligomeric state of phospholamban, demonstrating that it is possible to determine the oligomeric number directly from NMR data. Additional tests on a number of homo-oligomers, from dimer to heptamer, similarly demonstrate the power of our method to provide unbiased determination and evaluation of homo-oligomeric complex structures. Proteins 2006. © 2006 Wiley-Liss, Inc. [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]

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]