Biomedical subjects

T Lengauer

Publications and source records attributed to T Lengauer.

31 records · Page 2Linked to original sources

PubMed1999

Application of parameter optimization to molecular comparison problems.

Various bioinformatics comparison problems require optimizing several different properties simultaneously. Often linear objective functions combine the values for different properties of solution candidates into a single score to allow for multivariate optimization. In this context, an essential question is how each property should be weighted. Frequently, no apparent measure is available to serve as a model for the score. However, if preferences of certain solution candidates over others in a training set are available, the implied partial ordering may be used to best possibly adjust the weights. We apply different strategies to optimize the parameterization of empirical scoring functions used for two molecular comparison problems, protein threading and small molecule superposition. Using well established evaluation methods, it can be shown that the results of both comparison methods are significantly improved by systematically choosing appropriate weights for the scoring function contributions.

Algorithms↗

PubMed1998

FLEXS: a method for fast flexible ligand superposition.

If no structural information about a particular target protein is available, methods of rational drug design try to superimpose putative ligands with a given reference, e.g., an endogenous ligand. The goal of such structural alignments is, on the one hand, to approximate the binding geometry and, on the other hand, to provide a relative ranking of the ligands with respect to their similarity. An accurate superposition is the prerequisite of subsequent exploitation of ligand data by either 3D QSAR analyses, pharmacophore hypotheses, or receptor modeling. We present the automatic method FLEXS for structurally superimposing pairs of ligands, approximating their putative binding site geometry. One of the ligands is treated as flexible, while the other one, used as a reference, is kept rigid. FLEXS is an incremental construction procedure. The molecules to be superimposed are partitioned into fragments. Starting with placements of a selected anchor fragment, computed by two alternative approaches, the remaining fragments are added iteratively. At each step, flexibility is considered by allowing the respective added fragment to adopt a discrete set of conformations. The mean computing time per test case is about 1:30 min on a common-day workstation. FLEXS is fast enough to be used as a tool for virtual ligand screening. A database of typical drug molecules has been screened for potential fibrinogen receptor antagonists. FLEXS is capable of retrieving all ligands assigned to platelet aggregation properties among the first 20 hits. Furthermore, the program suggests additional interesting candidates, likely to be active at the same receptor. FLEXS proves to be superior to commonly used retrieval techniques based on 2D fingerprint similarities. The accuracy of computed superpositions determines the relevance of subsequently performed ligand analyses. In order to validate the quality of FLEXS alignments, we attempted to reproduce a set of 284 mutual superpositions derived from experimental data on 76 protein-ligand complexes of 14 proteins. The ligands considered cover the whole range of drug-size molecules from 18 to 158 atoms (PDB codes: 3ptb, 2er7). The performance of the algorithm critically depends on the sizes of the molecules to be superimposed. The limitations are clearly demonstrated with large peptidic inhibitors in the HIV and the endothiapepsin data set. Problems also occur in the presence of multiple binding modes (e.g., elastase and human rhinovirus). The most convincing results are achieved with small- and medium-sized molecules (as, e.g., the ligands of trypsin, thrombin, and dihydrofolate reductase). In more than half of the entire test set, we achieve rms deviations between computed and observed alignment of below 1.5 A. This underlines the reliability of FLEXS-generated alignments.

Algorithms↗

PubMed1998

RigFit: a new approach to superimposing ligand molecules.

If structural knowledge of a receptor under consideration is lacking, drug design approaches focus on similarity or dissimilarity analysis of putative ligands. In this context the mutual ligand superposition is of utmost importance. Methods that are rapid enough to facilitate interactive usage, that allow to process sets of conformers and that enable database screening are of special interest here. The ability to superpose molecular fragments instead of entire molecules has proven to be helpful too. The RIGFIT approach meets these requirements and has several additional advantages. In three distinct test applications, we evaluated how closely we can approximate the observed relative orientation for a set of known crystal structures, we employed RIGFIT as a fragment placement procedure, and we performed a fragment-based database screening. The run time of RIGFIT can be traded off against its accuracy. To be competitive in accuracy with another state-of-the-art alignment tool, with which we compare our method explicitly, computing times of about 6 s per superposition on a common day workstation are required. If longer run times can be afforded the accuracy increases significantly. RIGFIT is part of the flexible superposition software FLEXS which can be accessed on the WWW [http:/(/)cartan.gmd.de/FlexS].

Algorithms↗

PubMed1997

CASP2 experiences with docking flexible ligands using FlexX.

We have applied our docking program FlexX to all eight CASP2 targets involving protein complexes with small ligands. Of the seven targets that were kept in the CASP2 experiment, we could solve two. We found important parts of the solution in four other examples, and were unsuccessful on the remaining example. This paper discusses all predictions in detail. Each of our prediction runs took just a few minutes of computer time on a standard workstation and could thus be demonstrated in real time at the CASP meeting. We believe that this speed is the prime strength of our program FlexX. In quality, our predictions are competitive with those produced by other predictors. The experiment showed that possible objectives of improvement of the FlexX program are to incorporate relevant aspects of receptor flexibility, deal with water molecules in the receptor pocket, allow for a postoptimization to refine favorable complexes, and improve the scoring function.

Amiloride↗

PubMed1997

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.

Automation↗

PubMed1997

Time-efficient flexible superposition of medium-sized molecules.

We present an efficient algorithm for the structural alignment of medium-sized organic molecules. The algorithm has been developed for applications in 3D QSAR and in receptor modeling. The method assumes one of the molecules, the reference ligand, to be presented in the conformation that it adopts inside the receptor pocket. The second molecule, the test ligand, is considered to be flexible, and is assumed to be given in an arbitrary low-energy conformation. Ligand flexibility is modeled by decomposing the test ligand into molecular fragments, such that ring systems are completely contained in a single fragment. Conformations of fragments and torsional angles of single bonds are taken from a small finite set, which depends on the fragment and bond, respectively. The algorithm superimposes a distinguished base fragment of the test ligand onto a suitable region of the reference ligand and then attaches the remaining fragments of the test ligand in a step-by-step fashion. During this process, a scoring function is optimized that encompasses bonding terms and terms accounting for steric overlap as well as for similarity of chemical properties of both ligands. The algorithm has been implemented in the FLEXS system. To validate the quality of the produced results, we have selected a number of examples for which the mutual superposition of two ligands is experimentally given by the comparison of the binding geometries known from the crystal structures of their corresponding protein-ligand complexes. On more than two-thirds of the test examples the algorithm produces rms deviations of the predicted versus the observed conformation of the test ligand below 1.5 A. The run time of the algorithm on a single problem instance is a few minutes on a common-day workstation. The overall goal of this research is to drastically reduce run times, while limiting the inaccuracies of the model and the computation to a tolerable level.

Algorithms↗

PubMed1997

Detection of distant structural similarities in a set of proteins using a fast graph-based method.

We introduce a method for finding weak structural similarities in a set of protein structures. Proteins are considered at their secondary structure level. The method uses a rigorous graph-theoretical algorithm which finds all structural similarities. Protein structures are modelled as undirected labelled graphs, the so-called protein graphs. We suggest that for detecting the similarities between two protein structures it is sufficient to find similarities in the protein core which consists of tightly packed secondary structure elements. Therefore, we can restrict ourselves to solving the maximal common connected subgraph problem instead of the maximal common subgraph problem. We have modified the algorithm by Bron and Kerbosch for solving that problem. The speed of the algorithm increases drastically. After calculating all maximal common connected substructures for all pairwise comparisons in a set of protein graphs the common substructure in all proteins can be calculated by intersecting them. In this paper we characterize the method briefly and explain the modelling of the protein structure in detail. For the pairwise alignment the similarity of porin (1OMF) with bacteriochlorophyll a (3BCL) and BirA protein (1BIB) with DNA polymerase III (2POL) will be discussed. In the case of the multiple structure alignment the similarity in variants of four phosphatases and in subtilisin Carlsberg, carboxypeptidase, elongation factor Tu, and flavodoxin will be represented. Our first experiments show that the method works correctly and fast. The method can be used for arbitrary graphs. Thus, different graph-theoretical models of protein structures can be examined.

Algorithms↗

PubMed1996

A fast flexible docking method using an incremental construction algorithm.

We present an automatic method for docking organic ligands into protein binding sites. The method can be used in the design process of specific protein ligands. It combines an appropriate model of the physico-chemical properties of the docked molecules with efficient methods for sampling the conformational space of the ligand. If the ligand is flexible, it can adopt a large variety of different conformations. Each such minimum in conformational space presents a potential candidate for the conformation of the ligand in the complexed state. Our docking method samples the conformation space of the ligand on the basis of a discrete model and uses a tree-search technique for placing the ligand incrementally into the active site. For placing the first fragment of the ligand into the protein, we use hashing techniques adapted from computer vision. The incremental construction algorithm is based on a greedy strategy combined with efficient methods for overlap detection and for the search of new interactions. We present results on 19 complexes of which the binding geometry has been crystallographically determined. All considered ligands are docked in at most three minutes on a current workstation. The experimentally observed binding mode of the ligand is reproduced with 0.5 to 1.2 A rms deviation. It is almost always found among the highest-ranking conformations computed.

Algorithms↗

PubMed1996

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

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 A 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.

Algorithms↗

PubMed1996

Computational methods for biomolecular docking.

With the rapidly increasing amount of molecular biological data available, the computer-based analysis of molecular interactions becomes more and more feasible. Methods for computer-aided molecular docking have to include a reasonably accurate model of energy and must be able to deal with the combinatorial complexity incurred by the molecular flexibility of the docking partners. In both respects, recent years have seen substantial progress.

Databases, Factual↗

PubMed1996

An algorithm for finding maximal common subtopologies in a set of protein structures.

For the comparison and analysis of protein structures, it is of interest to find maximal common substructures in a given set of proteins. This question is also relevant for motif definition and structure classification. In this paper we describe first a new suitable representation of the secondary structure topology of a protein by an undirected labeled graph. Based on this representation we developed a new fast algorithm that finds all common subtopologies in a set of protein structures. Our method is based on the algorithm by Bron and Kerbosch (1973), which enumerates all maximal cliques in a graph. The main improvement of our algorithm is to restrict the search process to cliques that represent connected substructures. This restriction reduces the number of cliques to be considered during the search process and the size of the search tree drastically. Thus we are able to handle large proteins. Experiments show the efficiency and superiority of our algorithm in comparison with other existing algorithms basing on graph-theoretical methods.

Algorithms↗

PubMed1995

Time-efficient docking of flexible ligands into active sites of proteins.

We present an algorithm for placing flexible molecules in active sites of proteins. The two major goals in the development of our docking program, called FLEXX, are the explicit exploitation of molecular flexibility of the ligand and the development of a model of the docking process that includes the physico-chemical properties of the molecules. The algorithm consists of three phases: The selection of a base fragment, the placement of the base fragment in the active site, and the incremental construction of the ligand inside the active site. Except for the selection of the base fragment, the algorithm runs without manual intervention. The algorithm is tested by reproducing 11 receptor-ligand complexes known from X-ray crystallography. In all cases, the algorithm predicts a placement of the ligand which is similar to the crystal structure (about 1.5 A RMS deviation or less) in a few minutes on a workstation, assuming that the receptor is given in the bound conformation.

Algorithms↗

PubMed1995

Recursive dynamic programming for adaptive sequence and structure alignment.

We propose a new alignment procedure that is capable of aligning protein sequences and structures in a unified manner. Recursive dynamic programming (RDP) is a hierarchical method which, on each level of the hierarchy, identifies locally optimal solutions and assembles them into partial alignments of sequences and/or structures. In contrast to classical dynamic programming, RDP can also handle alignment problems that use objective functions not obeying the principle of prefix optimality, e.g. scoring schemes derived from energy potentials of mean force. For such alignment problems, RDP aims at computing solutions that are near-optimal with respect to the involved cost function and biologically meaningful at the same time. Towards this goal, RDP maintains a dynamic balance between different factors governing alignment fitness such as evolutionary relationships and structural preferences. As in the RDP method gaps are not scored explicitly, the problematic assignment of gap cost parameters is circumvented. In order to evaluate the RDP approach we analyse whether known and accepted multiple alignments based on structural information can be reproduced with the RDP method. For this purpose, we consider the family of ferredoxins as our prime example. Our experiments show that, if properly tuned, the RDP method can outperform methods based on classical sequence alignment algorithms as well as methods that take purely structural information into account.

Amino Acid Sequence↗