Optimization in bioinformatics

References

Cite

Share

Abstract

In this work, we present novel optimization approaches for important bioinformatical problems. The rst part deals mainly with the local optimization of molecular structures and its applications to molecular docking, while the second part discusses discrete global optimization. In the rst part, we present a novel algorithm to an old task: nd the next local optimum into a given direction on a molecular potential energy function (line search). We show that replacing a standard line search method with the new algorithm reduced the number of function/gradient evaluations in our test runs down to 47.7% (down to 85% on average) . Then, we include this method into our novel approach for locally optimizing exible ligands in the presence of their receptors, which we describe in detail, avoiding the singularity problem of orientational parameters. We extend this approach to a full ligand-receptor docking program using a Lamarckian genetic algorithm. Our validation runs show that we gained an up to tenfold speedup in comparison to other tested methods. Then, we further incorporate side chain exibility of the receptor into our approach and introduce limited backbone exibility by interpolating between known extremal conformations using spherical linear extrapolation. Our results show that this approach is very promising for exible ligand-receptor docking. However, the drawback is that we need known extremal backbone conformations for the interpolation. In the last section of the rst part, we allow a loop region to be fully exible. We present a new method to nd all possible conformations using the Go-Scheraga ring closure equations and interval arithmetic. Our results show that this algorithm reliably nds alternative conformations and is able to identify promising loop/ligand complexes of the studied example. In the second part of this work, we describe the bond order assignment problem for molecular structures. We present our novel linear 0-1-programming formulation for the very efficient computation of all optimal and suboptimal bond order assignments and show that our approach does not only outperform the original heuristic approach of Wang et al. but also commonly used software for determining bond orders on our test set considering all optimal results. This test set consists of 761 thoroughly prepared drug like molecules that were originally used for the validation of the Merck Molecular Force Field. Then, we present our lter method for feature subset selection that is based on mutual information and uses second order information. We show our mathematically well motivated criterion and, in contrast to other methods, solve the resulting optimization problem exactly by quadratic 0-1-programming. In the validation runs, our method could achieve in 18 out of 21 test scenarios the best classification accuracies. In the last section, we give our integer linear programming formulation for the detection of deregulated subgraphs in regulatory networks using expression pro les. Our approach identi es the subnetwork of a certain size of the regulatory network with the highest sum of node scores. To demonstrate the capabilities of our algorithm, we analyzed expression pro les from nonmalignant primary mammary epithelial cells derived from BRCA1 mutation carriers and epithelial cells without BRCA1 mutation. Our results suggest that oxidative stress plays an important role in epithelial cells with BRCA1 mutations that may contribute to the later development of breast cancer. The application of our algorithm to already published data can yield new insights. As expression data and network data are still growing, methods as our algorithm will be valuable to detect deregulated subgraphs in dierent conditions and help contribute to a better understanding of diseases. In der vorliegenden Arbeit prasentieren wir neue Optimierungsansatze fur wichtige Probleme der Bioinformatik. Der erste Teil behandelt vorwiegend die lokale Optimierung von Molekulen und die Anwendung beim molekularen Docking. Der zweite Teil diskutiert diskrete globale Optimierung. Im ersten Teil prasentieren wir einen neuartigen Algorithmus fur ein altes Problem: fi nde das nachste lokale Optimum in einer gegebenen Richtung auf einer Energiefunktion (Liniensuche, "line search"). Wir zeigen, dass die Ersetzung einer Standardliniensuche mit unserer neuen Methode die Anzahl der Funktions- und Gradientauswertungen in unseren Testlaufen auf bis zu 47.7% reduzierte (85% im Mittel). Danach nehmen wir diese Methode in unseren neuen Ansatz zur lokalen Optimierung von flexiblen Liganden im Beisein ihres Rezeptors auf, den wir im Detail beschreiben. Unser Verfahren vermeidet das Singularitatsproblem von Orientierungsparametern. Wir erweitern diese Methode zu einem vollstandigen Liganden-Rezeptor-Dockingprogramm, indem wir einen Lamarck'schen genetischen Algorithmus einsetzen. Unsere Validierungslaufe zeigen, dass wir im Vergleich zu anderen getesteten Methoden einen bis zu zehnfachen Geschwindigkeitszuwachs erreichen. Danach arbeiten wir in unseren Ansatz Seitenketten- und begrenzte Backbone exibilitat ein, indem wir zwischen bekannten Extremkonformationen mittels spharischer linearer Extrapolation interpolieren. Unsere Resultate zeigen, dass unsere Methode sehr viel versprechend fur flexibles Liganden-Rezeptor-Docking ist. Dennoch hat dieser Ansatz den Nachteil, dass man bekannte Extremkonformationen des Backbones fur die Interpolation benotigt. Im letzten Abschnitt des ersten Teils behandeln wir eine Loopregion voll flexibel. Wir zeigen eine neue Methode, die die Go-Scheraga Ringschlussgleichungen und Intervalarithmetik nutzt, um alle moglichen Konformationen zu nden. Unsere Resultate zeigen, dass dieser Algorithmus zuverlassig in der Lage ist, alternative Konformationen zu nden. Er identi ziert sehr vielversprechende Loop-Ligandenkomplexe unseres Testbeispiels. Im zweiten Teil dieser Arbeit beschreiben wir das Bindungsordnungszuweisungsproblem von Molekulen. Wir prasentieren unsere neuartige Formulierung, die auf linearer 0-1-Programmierung basiert. Dieser Ansatz ist in der Lage sehr effizient alle optimalen und suboptimalen Bindngsordnungszuweisungen zu berechnen. Unsere Methode ist nicht nur besser als der ursprungliche Ansatz von Wang et al., sondern auch weitverbreiteter Software zur Bindungszuordnung auf unserem Testdatensatz uberlegen. Dieser Datensatz besteht aus 761 sorgfaltig praparierten, arzneimittelahnlichen Molekulen, die ursprunglich zur Validierung des Merck-Kraftfeldes eingesetzt wurden. Danach prasentieren wir unsere Filtermethode zur "Feature Subset Selection", die auf "Mutual Information" basiert und Informationen zweiter Ordnung nutzt. Wir geben unser mathematisch motiviertes Kriterium an und losen das resultierende Optimierungsproblem global optimal im Gegensatz zu anderen Ansatzen. In unseren Validierungslaufen konnte unsere Methode in 18 von 21 Testszenarien die beste Klassi zierungsrate erreichen. Im letzten Abschnitt geben wir unsere, auf linearer 0-1-Programmierung basierende Formulierung zur Berechnung von deregulierten Untergraphen in regulatorischen Netzwerken an. Die Basisdaten fur diese Methode sind Expressionspro le. Unser Ansatz identi ziert die Unternetze einer gewissen Grose mit der hochsten Summe der Knotenscores. Wir analysierten Expressionspro le von nicht bosartigen Brustepithelzellen von BRCA1 Mutationstragern und Epithelzellen ohne BRCA1 Mutation, um die Fahigkeiten unseres Algorithmuses zu demonstrieren. Unsere Resultate legen nahe, dass oxidativer Stress eine wichtige Rolle bei Epithelzellen mit BRCA1 Mutation spielt, der zur spateren Entwicklung von Brustkrebs beitragen konnte. Die Anwendung unseres Ansatzes auf bereits publizierte Daten kann zu neuen Erkenntnissen fuhren. Da sowohl Expressions- wie auch Netzwerkdaten standig anwachsen, sind es Methoden wie unser Algorithmus die wertvoll sein werden, um deregulierte Subgraphen in verschiedenen Situationen zu entdecken. Damit tragt unser Ansatz zu einem besseren Verstandnis von Krankheiten und deren Verlauf bei.