Efficient a priori identification of drug resistant mutations using Dead-End Elimination and MM-PBSA.

Active site mutations that disrupt drug binding are an important mechanism of drug resistance. Computational methods capable of predicting resistance a priori are poised to become extremely useful tools in the fields of drug discovery and treatment design. In this paper, we describe an approach to predicting drug resistance on the basis of Dead-End Elimination and MM-PBSA that requires no prior knowledge of resistance. Our method utilizes a two-pass search to identify mutations that impair drug binding while maintaining affinity for the native substrate. We use our method to probe resistance in four drug-target systems: isoniazid-enoyl-ACP reductase (tuberculosis), ritonavir-HIV protease (HIV), methotrexate-dihydrofolate reductase (breast cancer and leukemia), and gleevec-ABL kinase (leukemia). We validate our model using clinically known resistance mutations for all four test systems. In all cases, the model correctly predicts the majority of known resistance mutations.

A Bayesian method for 3D macromolecular structure inference using class average images from single particle electron microscopy.

MOTIVATION: Electron cryo-microscopy can be used to infer 3D structures of large macromolecules with high resolution, but the large amounts of data captured necessitate the development of appropriate statistical models to describe the data generation process, and to perform structure inference. We present a new method for performing ab initio inference of the 3D structures of macromolecules from single particle electron cryo-microscopy experiments using class average images. RESULTS: We demonstrate this algorithm on one phantom, one synthetic dataset and three real (experimental) datasets (ATP synthase, V-type ATPase and GroEL). Structures consistent with the known structures were inferred for all datasets. AVAILABILITY: The software and source code for this method is available for download from our website: http://compbio.cs.toronto.edu/cryoem/.

Virtual decoy sets for molecular docking benchmarks.

Virtual docking algorithms are often evaluated on their ability to separate active ligands from decoy molecules. The current state-of-the-art benchmark, the Directory of Useful Decoys (DUD), minimizes bias by including decoys from a library of synthetically feasible molecules that are physically similar yet chemically dissimilar to the active ligands. We show that by ignoring synthetic feasibility, we can compile a benchmark that is comparable to the DUD and less biased with respect to physical similarity.

Normalizing molecular docking rankings using virtually generated decoys.

Drug discovery research often relies on the use of virtual screening via molecular docking to identify active hits in compound libraries. An area for improvement among many state-of-the-art docking methods is the accuracy of the scoring functions used to differentiate active from nonactive ligands. Many contemporary scoring functions are influenced by the physical properties of the docked molecule. This bias can cause molecules with certain physical properties to incorrectly score better than others. Since variation in physical properties is inevitable in large screening libraries, it is desirable to account for this bias. In this paper, we present a method of normalizing docking scores using virtually generated decoy sets with matched physical properties. First, our method generates a set of property-matched decoys for every molecule in the screening library. Each library molecule and its decoy set are docked using a state-of-the-art method, producing a set of raw docking scores. Next, the raw docking score of each library molecule is normalized against the scores of its decoys. The normalized score represents the probability that the raw docking score was drawn from the background distribution of nonactive property-matched decoys. Assuming that the distribution of scores of active molecules differs from the nonactive score distribution, we expect that the score of an active compound will have a low probability of having been drawn from the nonactive score distribution. In addition to the use of decoys in normalizing docking scores, we suggest that decoy sets may be a useful tool to evaluate, improve, or develop scoring functions. We show that by analyzing docking scores of library molecules with respect to the docking scores of their virtually generated property-matched decoys, one can gain insight into the advantages, limitations, and reliability of scoring functions.

Applying medicinal chemistry transformations and multiparameter optimization to guide the search for high-quality leads and candidates.

In this article we describe a computational method that automatically generates chemically relevant compound ideas from an initial molecule, closely integrated with in silico models, and a probabilistic scoring algorithm to highlight the compound ideas most likely to satisfy a user-defined profile of required properties. The new compound ideas are generated using medicinal chemistry 'transformation rules' taken from examples in the literature. We demonstrate that the set of 206 transformations employed is generally applicable, produces a wide range of new compounds, and is representative of the types of modifications previously made to move from lead-like to drug-like compounds. Furthermore, we show that more than 94% of the compounds generated by transformation of typical drug-like molecules are acceptable to experienced medicinal chemists. Finally, we illustrate an application of our approach to the lead that ultimately led to the discovery of duloxetine, a marketed serotonin reuptake inhibitor.

Results of the 3D Virtual Comparison Microscopy Error Rate (VCMER) Study for firearm forensics.

The digital examination of scanned or measured 3D surface topography is referred to as Virtual Comparison Microscopy (VCM). Within the discipline of firearm and toolmark examination, VCM enables review and comparison of microscopic toolmarks on fired ammunition components. In the coming years, this technique may supplement and potentially replace the light comparison microscope as the primary instrument used for firearm and toolmark examination. This paper describes a VCM error rate and validation study involving 107 participants. The study included 40 test sets of fired cartridge cases from firearms with a variety of makes, models, and calibers. Participants used commercially available VCM software which allowed digital data distribution, specimen visualization, and submission of conclusions. The software also allowed participants to annotate areas of similarity and dissimilarity to support their conclusions. The primary cohort of 76 qualified United States and Canadian examiners that completed the study had an overall false-positive error rate of 3 errors from 693 comparisons (0.43%) and a false-negative error rate of 0 errors from 491 comparisons (0.0%). This accuracy is supplemented by the participant's provided surface annotations which provide insight into the cause of errors and the overall consistency across the independent examinations conducted in the study. The ability to obtain highly accurate conclusions on test fires from a wide range of firearms supports the hypothesis that VCM is a useful tool within the crime laboratory.

Restricted dead-end elimination: protein redesign with a bounded number of residue mutations.

Dead-end elimination (DEE) has emerged as a powerful structure-based, conformational search technique enabling computational protein redesign. Given a protein with n mutable residues, the DEE criteria guide the search toward identifying the sequence of amino acids with the global minimum energy conformation (GMEC). This approach does not restrict the number of permitted mutations and allows the identified GMEC to differ from the original sequence in up to n residues. In practice, redesigns containing a large number of mutations are often problematic when taken into the wet-lab for creation via site-directed mutagenesis. The large number of point mutations required for the redesigns makes the process difficult, and increases the risk of major unpredicted and undesirable conformational changes. Preselecting a limited subset of mutable residues is not a satisfactory solution because it is unclear how to select this set before the search has been performed. Therefore, the ideal approach is what we define as the kappa-restricted redesign problem in which any kappa of the n residues are allowed to mutate. We introduce restricted dead-end elimination (rDEE) as a solution of choice to efficiently identify the GMEC of the restricted redesign (the kappaGMEC). Whereas existing approaches require n-choose-kappa individual runs to identify the kappaGMEC, the rDEE criteria can perform the redesign in a single search. We derive a number of extensions to rDEE and present a restricted form of the A* conformation search. We also demonstrate a 10-fold speed-up of rDEE over traditional DEE approaches on three different experimental systems.

Prediction of sub-cavity binding preferences using an adaptive physicochemical structure representation.

MOTIVATION: The ability to predict binding profiles for an arbitrary protein can significantly improve the areas of drug discovery, lead optimization and protein function prediction. At present, there are no successful algorithms capable of predicting binding profiles for novel proteins. Existing methods typically rely on manually curated templates or entire active site comparison. Consequently, they perform best when analyzing proteins sharing significant structural similarity with known proteins (i.e. proteins resulting from divergent evolution). These methods fall short when used to characterize the binding profile of a novel active site or one for which a template is not available. In contrast to previous approaches, our method characterizes the binding preferences of sub-cavities within the active site by exploiting a large set of known protein-ligand complexes. The uniqueness of our approach lies not only in the consideration of sub-cavities, but also in the more complete structural representation of these sub-cavities, their parametrization and the method by which they are compared. By only requiring local structural similarity, we are able to leverage previously unused structural information and perform binding inference for proteins that do not share significant structural similarity with known systems. RESULTS: Our algorithm demonstrates the ability to accurately cluster similar sub-cavities and to predict binding patterns across a diverse set of protein-ligand complexes. When applied to two high-profile drug targets, our algorithm successfully generates a binding profile that is consistent with known inhibitors. The results suggest that our algorithm should be useful in structure-based drug discovery and lead optimization.

The protein-small-molecule database, a non-redundant structural resource for the analysis of protein-ligand binding.

MOTIVATION: An enabling resource for drug discovery and protein function prediction is a large, accurate and actively maintained collection of protein/small-molecule complex structures. Models of binding are typically constructed from these structural libraries by generalizing the observed interaction patterns. Consequently, the quality of the model is dependent on the quality of the structural library. An ideal library should be non-biased and comprehensive, contain high-resolution structures and be actively maintained. RESULTS: We present a new protein/small-molecule database (the PSMDB) that offers a non-redundant set of holo PDB complexes. The database was designed to allow frequent updates through a fully automated process without manual annotation or filtering. Our method of database construction addresses redundancy at both the protein and the small-molecule level. By efficiently handling structures with covalently bound ligands, we allow our database to include a larger number of structures than previous methods. Multiple versions of the database are available at our web site, including structures of split complexes--the proteins without their binding ligands and the non-covalently bound ligands within their native coordinate frame. AVAILABILITY: http://compbio.cs.toronto.edu/psmdb

Predicting multiple ligand binding modes using self-consistent pharmacophore hypotheses.

The ability to predict ligand binding modes without the aid of wet-lab experiments may accelerate and reduce the cost of drug discovery research. Despite significant recent progress, virtual screening has not yet eliminated the need for wet-lab experiments. For example, after a lead compound has been identified, the precise binding mode is still typically determined by experimental structural biology. This structural knowledge is then employed to guide lead optimization. We present a step toward improving protein-ligand binding mode prediction for a set of ligands known to interact with a common protein. There is thus an important distinction between this work and traditional virtual screening algorithms. Whereas traditional approaches attempt to identify binding ligands from a large database of available compounds, our approach aims to more accurately predict the binding mode for a set of ligands which are already known to bind the target protein. The approach is based on the hypothesis that each active site contains a set of interaction points which binding ligands tend to exploit. In a more traditional context, these interaction points make up a pharmacophoric map. Our algorithm first performs traditional protein-ligand docking for each known binder. The ranked lists of candidate binding modes are then evaluated to identify a set of poses maximally self-consistent with respect to a pharmacophoric map generated from the same poses. We have extensively demonstrated the application of the algorithm to four protein systems (thrombin, cyclin-dependent kinase 2, dihydrofolate reductase, and HIV-1 protease) and attained predictions with an average RMSD < 2.5 A for all tested systems. This represents a typical improvement of 0.5-1.0 A (up to 25%) RMSD over the naive virtual docking predictions. Our algorithm is independent of the docking method and may significantly improve binding mode prediction of virtual docking experiments.

The minimized dead-end elimination criterion and its application to protein redesign in a hybrid scoring and search algorithm for computing partition functions over molecular ensembles.

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.

Allosteric inhibition of the protein-protein interaction between the leukemia-associated proteins Runx1 and CBFbeta.

The two subunits of core binding factor (Runx1 and CBFbeta) play critical roles in hematopoiesis and are frequent targets of chromosomal translocations found in leukemia. The binding of the CBFbeta-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 CBFbeta. NMR-based docking shows that these compounds bind to CBFbeta 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.

Development and Validation of a Virtual Examination Tool for Firearm Forensics,.

The transition from 2D imaging to 3D scanning in the discipline of firearms and toolmark analysis is likely to provide examiners an unprecedented view of microscopic surface topography. The digital examination of measured 3D surface topographies has been referred to as virtual microscopy (VM). The approach offers several potential advantages over traditional comparison microscopy. Like any new analytic method, VM must be validated prior to its use in a crime laboratory. This paper describes one of the first validation studies of virtual microscopy. Fifty-six participants at fifteen laboratories used virtual microscopic tools to complete two proficiency-style tests for cartridge case identification. All participating trained examiners correctly reported 100% of the identifications (known matches) while reporting no false positives. The VM tools also allowed examiners to annotate compared surfaces. These annotations provide insight into the types of marked utilized in comparative analysis. Overall, the results of the study demonstrate that trained examiners can successfully use virtual microscopy to conduct firearms toolmark examination and support the use of the technology in the crime laboratory.

Improved Pruning algorithms and Divide-and-Conquer strategies for Dead-End Elimination, with application to protein design.

MOTIVATION: Structure-based protein redesign can help engineer proteins with desired novel function. Improving computational efficiency while still maintaining the accuracy of the design predictions has been a major goal for protein design algorithms. The combinatorial nature of protein design results both from allowing residue mutations and from the incorporation of protein side-chain flexibility. Under the assumption that a single conformation can model protein folding and binding, the goal of many algorithms is the identification of the Global Minimum Energy Conformation (GMEC). A dominant theorem for the identification of the GMEC is Dead-End Elimination (DEE). DEE-based algorithms have proven capable of eliminating the majority of candidate conformations, while guaranteeing that only rotamers not belonging to the GMEC are pruned. However, when the protein design process incorporates rotameric energy minimization, DEE is no longer provably-accurate. Hence, with energy minimization, the minimized-DEE (MinDEE) criterion must be used instead. RESULTS: In this paper, we present provably-accurate improvements to both the DEE and MinDEE criteria. We show that our novel enhancements result in a speedup of up to a factor of more than 1000 when applied in redesign for three different proteins: Gramicidin Synthetase A, plastocyanin, and protein G. AVAILABILITY: Contact authors for source code.

Redesigning the PheA domain of gramicidin synthetase leads to a new understanding of the enzyme's mechanism and selectivity.

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.

A novel ensemble-based scoring and search algorithm for protein redesign and its application to modify the substrate specificity of the gramicidin synthetase a phenylalanine adenylation enzyme.

Realization of novel molecular function requires the ability to alter molecular complex formation. Enzymatic function can be altered by changing enzyme-substrate interactions via modification of an enzyme's active site. A redesigned enzyme may either perform a novel reaction on its native substrates or its native reaction on novel substrates. A number of computational approaches have been developed to address the combinatorial nature of the protein redesign problem. These approaches typically search for the global minimum energy conformation among an exponential number of protein conformations. We present a novel algorithm for protein redesign, which combines a statistical mechanics-derived ensemble-based approach to computing the binding constant with the speed and completeness of a branch-and-bound pruning algorithm. In addition, we developed an efficient deterministic approximation algorithm, capable of approximating our scoring function to arbitrary precision. In practice, the approximation algorithm decreases the execution time of the mutation search by a factor of ten. To test our method, we examined the Phe-specific adenylation domain of the nonribosomal peptide synthetase gramicidin synthetase A (GrsA-PheA). Ensemble scoring, using a rotameric approximation to the partition functions of the bound and unbound states for GrsA-PheA, is first used to predict binding of the wildtype protein and a previously described mutant (selective for leucine), and second, to switch the enzyme specificity toward leucine, using two novel active site sequences computationally predicted by searching through the space of possible active site mutations. The top scoring in silico mutants were created in the wetlab and dissociation/binding constants were determined by fluorescence quenching. These tested mutations exhibit the desired change in specificity from Phe to Leu. Our ensemble-based algorithm, which flexibly models both protein and ligand using rotamer-based partition functions, has application in enzyme redesign, the prediction of protein-ligand binding, and computer-aided drug design.

Clinical Prediction Rule for Patient Outcome after In-Hospital CPR: A New Model, Using Characteristics Present at Hospital Admission, to Identify Patients Unlikely to Benefit from CPR after In-Hospital Cardiac Arrest.

BACKGROUND: Physicians and patients frequently overestimate likelihood of survival after in-hospital cardiopulmonary resuscitation. Discussions and decisions around resuscitation after in-hospital cardiopulmonary arrest often take place without adequate or accurate information. METHODS: We conducted a retrospective chart review of 470 instances of resuscitation after in-hospital cardiopulmonary arrest. Individuals were randomly assigned to a derivation cohort and a validation cohort. Logistic Regression and Linear Discriminant Analysis were used to perform multivariate analysis of the data. The resultant best performing rule was converted to a weighted integer tool, and thresholds of survival and nonsurvival were determined with an attempt to optimize sensitivity and specificity for survival. RESULTS: A 10-feature rule, using thresholds for survival and nonsurvival, was created; the sensitivity of the rule on the validation cohort was 42.7% and specificity was 82.4%. In the Dartmouth Score (DS), the features of age (greater than 70 years of age), history of cancer, previous cardiovascular accident, and presence of coma, hypotension, abnormal PaO2, and abnormal bicarbonate were identified as the best predictors of nonsurvival. Angina, dementia, and chronic respiratory insufficiency were selected as protective features. CONCLUSIONS: Utilizing information easily obtainable on admission, our clinical prediction tool, the DS, provides physicians individualized information about their patients' probability of survival after in-hospital cardiopulmonary arrest. The DS may become a useful addition to medical expertise and clinical judgment in evaluating and communicating an individual's probability of survival after in-hospital cardiopulmonary arrest after it is validated by other cohorts.

Probabilistic disease classification of expression-dependent proteomic data from mass spectrometry of human serum.

We have developed an algorithm called Q5 for probabilistic classification of healthy versus disease whole serum samples using mass spectrometry. The algorithm employs principal components analysis (PCA) followed by linear discriminant analysis (LDA) on whole spectrum surface-enhanced laser desorption/ionization time of flight (SELDI-TOF) mass spectrometry (MS) data and is demonstrated on four real datasets from complete, complex SELDI spectra of human blood serum. Q5 is a closed-form, exact solution to the problem of classification of complete mass spectra of a complex protein mixture. Q5 employs a probabilistic classification algorithm built upon a dimension-reduced linear discriminant analysis. Our solution is computationally efficient; it is noniterative and computes the optimal linear discriminant using closed-form equations. The optimal discriminant is computed and verified for datasets of complete, complex SELDI spectra of human blood serum. Replicate experiments of different training/testing splits of each dataset are employed to verify robustness of the algorithm. The probabilistic classification method achieves excellent performance. We achieve sensitivity, specificity, and positive predictive values above 97% on three ovarian cancer datasets and one prostate cancer dataset. The Q5 method outperforms previous full-spectrum complex sample spectral classification techniques and can provide clues as to the molecular identities of differentially expressed proteins and peptides.

A polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments.

High-throughput NMR structural biology can play an important role in structural genomics. We report an automated procedure for high-throughput NMR resonance assignment for a protein of known structure, or of a homologous structure. These assignments are a prerequisite for probing protein-protein interactions, protein-ligand binding, and dynamics by NMR. Assignments are also the starting point for structure determination and refinement. A new algorithm, called Nuclear Vector Replacement (NVR) is introduced to compute assignments that optimally correlate experimentally measured NH residual dipolar couplings (RDCs) to a given a priori whole-protein 3D structural model. The algorithm requires only uniform( 15)N-labeling of the protein and processes unassigned H(N)-(15)N HSQC spectra, H(N)-(15)N RDCs, and sparse H(N)-H(N) NOE's (d(NN)s), all of which can be acquired in a fraction of the time needed to record the traditional suite of experiments used to perform resonance assignments. NVR runs in minutes and efficiently assigns the (H(N),(15)N) backbone resonances as well as the d(NN)s of the 3D (15)N-NOESY spectrum, in O(n(3)) time. The algorithm is demonstrated on NMR data from a 76-residue protein, human ubiquitin, matched to four structures, including one mutant (homolog), determined either by x-ray crystallography or by different NMR experiments (without RDCs). NVR achieves an assignment accuracy of 92-100%. We further demonstrate the feasibility of our algorithm for different and larger proteins, using NMR data for hen lysozyme (129 residues, 97-100% accuracy) and streptococcal protein G (56 residues, 100% accuracy), matched to a variety of 3D structural models. Finally, we extend NVR to a second application, 3D structural homology detection, and demonstrate that NVR is able to identify structural homologies between proteins with remote amino acid sequences using a database of structural models.

OSPREY: protein design with ensembles, flexibility, and provable algorithms.

UNLABELLED: We have developed a suite of protein redesign algorithms that improves realistic in silico modeling of proteins. These algorithms are based on three characteristics that make them unique: (1) improved flexibility of the protein backbone, protein side-chains, and ligand to accurately capture the conformational changes that are induced by mutations to the protein sequence; (2) modeling of proteins and ligands as ensembles of low-energy structures to better approximate binding affinity; and (3) a globally optimal protein design search, guaranteeing that the computational predictions are optimal with respect to the input model. Here, we illustrate the importance of these three characteristics. We then describe OSPREY, a protein redesign suite that implements our protein design algorithms. OSPREY has been used prospectively, with experimental validation, in several biomedically relevant settings. We show in detail how OSPREY has been used to predict resistance mutations and explain why improved flexibility, ensembles, and provability are essential for this application. AVAILABILITY: OSPREY is free and open source under a Lesser GPL license. The latest version is OSPREY 2.0. The program, user manual, and source code are available at www.cs.duke.edu/donaldlab/software.php. CONTACT: osprey@cs.duke.edu.