The atom assignment problem in automated de novo drug design. 1. Transferability of molecular fragment properties

Summary This paper is the first of a series which examines the problems of atom assignment in automated de novo drug design. In subsequent papers, a combinatoric optimization method for fragment placement onto 3D molecular graphs is provided. Molecules are built from molecular graphs by placing fragments onto the graph. Here we examine the transferability of atomic residual charge, by fragment placement, with respect to the electrostatic potential. This transferability has been tested on 478 molecular structures extracted from the Cambridge Structural Database. The correlation found between the electrostatic potential computed from composite fragments and that computed for the whole molecule was encouraging, except for extended conjugated systems.     

The atom assignment problem in automated de novo drug design. 4. Tests for site-directed fragment placement based on molecular complementarity

Summary Three previous papers in this series have outlined an optimization method for atom assignment in drug design using fragment placement. In this paper the procedure is rigorously tested on a selection of five ligand-protein co-crystals. The algorithm is presented with the molecular graph of the ligand, and the electrostatic/hydrophobic potential of the site, with the aim of creating a placement on the molecular graph which is as electrostatically complementary or hydrophobically similar to the site as possible. Various designer options were tested, including, where appropriate, hydrogen bonding and a restricted number of halogens. In most cases, the placement obtained was at least as good as the native ligand, if not significantly better.     

The atom assignment problem in automated de novo drug design. 2. A method for molecular graph and fragment perception

Summary If atom assignment onto 3D molecular graphs is to be optimized, an efficient scheme for placement must be developed. The strategy adopted in this paper is to analyze the molecular graphs in terms of cyclical and non-cyclical nodes; the latter are further divided into terminal and non-terminal nodes. Molecular fragments, from a fragments database, are described in a similar way. A canonical numbering scheme for the fragments and the local subgraph of the molecular graph enables fragments to be placed efficiently onto the molecular graph. Further optimization is achieved by placing similar fragments into bins using a hashing scheme based on the canonical numbering. The graph perception algorithm is illustrated in detail.     

The atom assignment problem in automated de novo drug design. 5. Tests for envelope-directed fragment placement based on molecular similarity

Summary The fragment placement method has been successfully extended to the problem of envelope-directed design. The atom assignment paradigm was based on molecular similarity between two molecular structures. A composite supersurface is defined to form the surface onto which the molecular fields are projected. The assignment process is then determined by using molecular similarity in the objective function to be optimized. In principle, this procedure is closely similar to that outlined in the previous paper for site-directed design. The rationale has been extensively tested on two benzodiazepine antagonists believed to bind to the same site.     

Placement of medium-sized molecular fragments into active sites of proteins

Summary We present an algorithm for placing molecular fragments into the active site of a receptor. A molecular fragment is defined as a connected part of a molecule containing only complete ring systems. The algorithm is part of a docking tool, called FlexX, which is currently under development at GMD. The overall goal is to provide means of automatically computing low-energy conformations of the ligand within the active site, with an accuracy approaching the limitations of experimental methods for resolving molecular structures and within a run time that allows for docking large sets of ligands. The methods by which we plan to achieve this goal are the explicit exploitation of molecular flexibility of the ligand and the incorporation of physicochemical properties of the molecules. The algorithm for fragment placement, which is the topic of this paper, is based on pattern recognition techniques and is able to predict a small set of possible positions of a molecular fragment with low flexibility within seconds on a workstation. In most cases, a placement with rms deviation below 1.0 Å with respect to the X-ray structure is found among the 10 highest ranking solutions, assuming that the receptor is given in the bound conformation.     

Molecular structure matching by simulated annealing. I. A comparison between different cooling schedules

Summary This paper outlines an application of the theory of simulated annealing to molecular matching problems. Three cooling schedules are examined: linear, exponential and dynamic cooling. The objective function is the sum of the elements of the difference distance matrix between the two molecules generated by continual reordering of one molecule. Extensive tests of the algorithms have been performed on random coordinate data together with two related protein structures. Combinatorial problems, inherent in the assignment of atom correspondences, are effectively overcome by simulated annealing. The algorithms outlined here can readily optimize molecular matching problems with 150 atoms.     

A novel conformation optimization model and algorithm for structure-based drug design

In this paper, we present a multi-scale optimization model and an entropy-based genetic algorithm for molecular docking. In this model, we introduce to the refined docking design a concept of residue groups based on induced-fit and adopt a combination of conformations in different scales. A new iteration scheme, in conjunction with multi-population evolution strategy, entropy-based searching technique with narrowing down space and the quasi-exact penalty function, is developed to address the optimization problem for molecular docking. A new docking program that accounts for protein flexibility has also been developed. The docking results indicate that the method can be efficiently employed in structure-based drug design.     

Automated site-directed drug design: The generation of a basic set of fragments to be used for automated structure assembly

Summary If a method is to be developed to assemble putative ligands structures in site-directed drug design, from molecular graphs generated in the site, then basic building blocks are needed. Structure assembly is a combinatoric process that needs to be optimised if it is to be tractable. What has to be determined is whether small molecular fragments can have transferable properties from one molecule to another. In this paper we determine all possible combinations of 3-, 4- and 5-atom aliphatic fragments from a small set of atoms H, C, N, O, F or Cl. The frequency of occurrence of these candidate fragments is searched for in the Cambridge Structural Database. A similar analysis is performed on charged fragments. A more restricted search is carried out for P and S and aromatic structures. A basic set of fragments can be derived that have a significant frequency in known crystal structures. The transferability of fragment properties is discussed in subsequent papers.     

Step-by-step calculation of all maximum common substructures through a constraint satisfaction based algorithm

In this paper we propose a new algorithm for subgraph isomorphism based on the representation of molecular structures as colored graphs and the representation of these graphs as vectors in n-dimensional spaces. The presented process that obtains all maximum common substructures is based on the solution of a constraint satisfaction problem defined as the common m-dimensional space (m< or =n) in which the vectors representing the matched graphs can be defined.     

Local elevation: A method for improving the searching properties of molecular dynamics simulation

Summary The concept of memory has been introduced into a molecular dynamics algorithm. This was done so as to persuade a molecular system to visit new areas of conformational space rather than be confined to a small number of low-energy regions. The method is demonstrated on a simple model system and the 11-residue cyclic peptide cyclosporin A. For comparison, calculations were also performed using simulated temperature annealing and a potential energy annealing scheme. Although the method can only be applied to systems with a small number of degrees of freedom, it offers the chance to generate a multitude of different low-energy structures, where other methods only give a single one or few. This is clearly important in problems such as drug design, where one is interested in the conformational spread of a system.     

Multiple automatic base selection: Protein–ligand docking based on incremental construction without manual intervention

A possible way of tackling the molecular docking problem arising in computer- aided drug design is the use of the incremental construction method. This method consists of three steps: the selection of a part of a molecule, a so- called base fragment, the placement of the base fragment into the active site of a protein, and the subsequent reconstruction of the complete drug molecule. Assuming that a part of a drug molecule is known, which is specific enough to be a good base fragment, the method is proven to be successful for a large set of docking examples. In addition, it leads to the fastest algorithms for flexible docking published so far. In most real-world applications of docking, large sets of ligands have to be tested for affinity to a given protein. Thus, manual selection of a base fragment is not practical. On the other hand, the selection of a base fragment is critical in that only few selections lead to a low-energy structure. We overcome this limitation by selecting a representative set of base fragments instead of a single one. In this paper, we present a set of rules and algorithms to automate this selection. In addition, we extend the incremental construction method to deal with multiple fragmentations of the drug molecule. Our results show that with multiple automated base selection, the quality of the docking predictions is almost as good as with one manually preselected base fragment. In addition, the set of solutions is more diverse and alternative binding modes with low scores are found. Although the run time of the overall algorithm increases, the method remains fast enough to search through large ligand data sets.     

GARANT-a general algorithm for resonance assignment of multidimensional nuclear magnetic resonance spectra

A new program for automatic resonance assignment of nuclear magnetic resonance (NMR) spectra of proteins, GARANT (General Algorithm for Resonance AssignmeNT), is introduced. Three principal elements used in this approach are: (a) representation of resonance assignments as an optimal match of two graphs describing, respectively, peaks expected from combined knowledge of the primary structure and the magnetization transfer pathways in the spectra used, and experimentally observed peaks; (b) a scoring scheme able to distinguish between correct and incorrect resonance assignments; and (c) combination of an evolutionary algorithm with a local optimization routine. The score that evaluates the match of expected peaks to observed peaks relies on the agreement of the information available about these peaks, most prominently, but not exclusively, the chemical shifts. Tests show that the combination of an evolutionary algorithm and a local optimization routine yields results that are clearly superior to those obtained when using either of the two techniques separately in the search for the correct assignments. GARANT is laid out for assignment problems involving peaks observed in two- and three-dimensional homonuclear and heteronuclear NMR spectra of proteins. © 1997 by John Wiley & Sons, Inc.     

De novo analysis of electron impact mass spectra using fragmentation trees

The automated fragmentation analysis of high resolution EI mass spectra based on a fragmentation tree algorithm is introduced. Fragmentation trees are constructed from EI spectra by automated signal extraction and evaluation. These trees explain relevant fragmentation reactions and assign molecular formulas to fragments. The method enables the identification of the molecular ion and the molecular formula of a metabolite if the molecular ion is present in the spectrum. These identifications are independent of existing library knowledge and, thus, support assignment and structural elucidation of unknown compounds. The method works even if the molecular ion is of very low abundance or hidden under contaminants with higher masses. We apply the algorithm to a selection of 50 derivatized and underivatized metabolites and demonstrate that in 78% of cases the molecular ion can be correctly assigned. The automatically constructed fragmentation trees correspond very well to published mechanisms and allow the assignment of specific relevant fragments and fragmentation pathways even in the most complex EI-spectra in our dataset. This method will be very helpful in the automated analysis of metabolites that are not included in common libraries and it thus has the potential to support the explorative character of metabolomics studies.     

GALAHAD: 1. Pharmacophore identification by hypermolecular alignment of ligands in 3D

Alignment of multiple ligands based on shared pharmacophoric and pharmacosteric features is a long-recognized challenge in drug discovery and development. This is particularly true when the spatial overlap between structures is incomplete, in which case no good template molecule is likely to exist. Pair-wise rigid ligand alignment based on linear assignment (the LAMDA algorithm) has the potential to address this problem (Richmond et al. in J Mol Graph Model 23:199-209, 2004). Here we present the version of LAMDA embodied in the GALAHAD program, which carries out multi-way alignments by iterative construction of hypermolecules that retain the aggregate as well as the individual attributes of the ligands. We have also generalized the cost function from being purely atom-based to being one that operates on ionic, hydrogen bonding, hydrophobic and steric features. Finally, we have added the ability to generate useful partial-match 3D search queries from the hypermolecules obtained. By running frozen conformations through the GALAHAD program, one can utilize the extended version of LAMDA to generate pharmacophores and pharmacosteres that agree well with crystal structure alignments for a range of literature datasets, with minor adjustments of the default parameters generating even better models. Allowing for inclusion of partial match constraints in the queries yields pharmacophores that are consistently a superset of full-match pharmacophores identified in previous analyses, with the additional features representing points of potentially beneficial interaction with the target.     

Molecular topology. VIII: Centricities in molecular graphs. The mollen algorithm

Local and global centricities and corresponding complexity centricities are derived on the basis of matricesB (layer matrix of vertex degrees) by using appropriate distance operators. The MOLCEN algorithm computes these centricities by means of line derivatives (L _n) of graphs. It provides reliable centric ordering of subgraphs of various length in molecular graphs. The algorithm is implemented on a TURBO-PASCAL, TOPIND program and is exemplified within a set of molecular graphs.     

Genetic algorithm for the design of molecules with desired properties

The design of molecules with desired properties is still a challenge because of the largely unpredictable end results. Computational methods can be used to assist and speed up this process. In particular, genetic algorithms have proved to be powerful tools with a wide range of applications, e.g. in the field of drug development. Here, we propose a new genetic algorithm that has been tailored to meet the demands of de novo drug design, i.e. efficient optimization based on small training sets that are analyzed in only a small number of design cycles. The efficiency of the design algorithm was demonstrated in the context of several different applications. First, RNA molecules were optimized with respect to folding energy. Second, a spinglass was optimized as a model system for the optimization of multiletter alphabet biopolymers such as peptides. Finally, the feasibility of the computer-assisted molecular design approach was demonstrated for the de novo construction of peptidic thrombin inhibitors using an iterative process of 4 design cycles of computer-guided optimization. Synthesis and experimental fitness determination of only 600 different compounds from a virtual library of more than 10¹⁷ molecules was necessary to achieve this goal.These authors contributed equally to the results presentedThese authors contributed equally to the results presentedThese authors contributed equally to the results presentedThese authors contributed equally to the results presented     

Scaffold topologies. 1. Exhaustive enumeration up to eight rings

Mapping the chemical space of small organic molecules is approached from a theoretical graph theory viewpoint, in an effort to begin the systematic exploration of molecular topologies. We present an algorithm for exhaustive generation of scaffold topologies with up to eight rings and an efficient comparison method for graphs within this class. This method uses the return index, a topological invariant derived from the adjacency matrix of the graph. Furthermore, we describe an algorithm that verifies the adequacy of the comparison method. Applications of this method for chemical space exploration in the context of drug discovery are discussed. The key result is a unique characterization of scaffold topologies, which may lead to more efficient ways to query large chemical databases.     

Evaluation of Multi-Objective Optimization Algorithms for NMR Chemical Shift Assignment

An automated NMR chemical shift assignment algorithm was developed using multi-objective optimization techniques. The problem is modeled as a combinatorial optimization problem and its objective parameters are defined separately in different score functions. Some of the heuristic approaches of evolutionary optimization are employed in this problem model. Both, a conventional genetic algorithm and multi-objective methods, i.e., the non-dominated sorting genetic algorithms II and III (NSGA2 and NSGA3), are applied to the problem. The multi-objective approaches consider each objective parameter separately, whereas the genetic algorithm followed a conventional way, where all objectives are combined in one score function. Several improvement steps and repetitions on these algorithms are performed and their combinations are also created as a hyper-heuristic approach to the problem. Additionally, a hill-climbing algorithm is also applied after the evolutionary algorithm steps. The algorithms are tested on several different datasets with a set of 11 commonly used spectra. The test results showed that our algorithm could assign both sidechain and backbone atoms fully automatically without any manual interactions. Our approaches could provide around a 65% success rate and could assign some of the atoms that could not be assigned by other methods.     

噻吩并嘧啶类FLT3抑制剂结合模式预测与分析

FLT3(FMS样酪氨酸酶III)是酪氨酸激酶受体(RTKIII)成员之一,其异常超表达或突变与急性髓细胞白血病(AML)呈现非常大的相关性,成为治疗AML的重要靶位点。本文采用不同的方法对FLT3活性位点进行了预测,利用分子对接、分子动力学以及药效团分析研究了新型嘧啶类化合物与FLT3的相互作用与结合模式。分子对接得到的结合模式与分子动力学模拟得到的结果一致,结合药效团分析表明该嘧啶类化合物主要通过疏水相互作用和氢键与FLT3激活位点结合,从而起到抑制作用。本研究对以FLT3为靶点的嘧啶类抑制剂的开发提供了理论和实验依据。