Neue Algorithmen zur Bestimmung maximaler gemeinsamer Subgraphen in chemischen Mustern und Räumen

Abstract

Im Anwendungsgebiet der Chemie und auch in der Chemieinformatik gibt es verschiedene Konzepte von Ähnlichkeit. Substanzen können ein ähnliches Aussehen haben, sie können aus den gleichen Ausgangsstoffen bestehen, zu einer Stoffgruppe gehören oder ähnliche physikalische und sonstige Eigenschaften aufweisen. Mit Blick auf die Chemieinformatik werden Ähnlichkeitsmaße bevorzugt, die es einem Computerprogramm ermöglichen, einfach einen Ähnlichkeitswert zu berechnen. In diesem Kontext werden dreidimensionale Strukturen und Oberflächen, Anordnungen funktioneller Gruppen im Zwei- und Dreidimensionalen oder das Vorhandensein von Substrukturen für die Ähnlichkeitsberechnung verwendet. Im Promotionsprojekt dieser Arbeit wird der Fokus auf Ähnlichkeitsmaße gelegt, die sich aus maximalen gemeinsamen Teilstrukturen (MCS) zwischen einer Anfrage- und einem Zielmolekül errechnen. Es wird ein neuer Algorithmus vorgestellt, der das Problem generisch und in diversen Anwendungsszenarien lösen kann. Zusätzlich werden zwei neue Anwendungsszenarien für die MCS Methodik erschlossen. Der Fokus liegt dabei auf einer schlanken und einfachen Struktur, die es zusätzlich ermöglicht, zusammenhängende und nicht zusammenhängende Teilstrukturen gezielt und mit weiteren Einschränkungen zu berechnen. Die initiale Algorithmusentwicklung schließt mit einer Demonstration der Effzienz im Vergleich zu anderen Methoden ab. Daraufhin wird der vorgestellte Algorithmus genutzt, um mit dem MCS-Ähnlichkeitsmaß nicht nur einzelne Vergleiche durchzuführen, sondern kombinatorische Substanzbibliotheken, die mehrere Milliarden Moleküle repräsentieren, gezielt zu durchsuchen. Dazu wird das Problem an die Struktur der Räume angepasst und der entwickelte MCS-Algorithmus in einem mehrstufigen Ablauf integriert. Das ermöglicht es, ähnlichste Moleküle zielgerichtet zu enumerieren. Mit dem zum Algorithmus gehörenden Computerprogramm wird sowohl die Effzienz der Methode gezeigt, als auch die Einfachheit demonstriert, den das Durchsuchen kommerzieller Fragmenträume für Wirkstoffentwicklung hat. Abschließend werden die methodischen Adaptionen am MCS genutzt, um aus dem Ähnlichkeitsmaß für Moleküle ein Ähnlichkeitsmaß auf molekularen Mustern zu entwickeln. In der Chemieinformatik gibt es verschiedene Konzepte, molekulare Muster über Substrukturen darzustellen. Über ein neuartiges Konzept allgemeiner chemischer Muster wird es ermöglicht, mit dem MCS molekulare Muster unabhängig von der textuellen Repräsentation zu vergleichen. Diese Vergleiche umfassen das Feststellen von Identität, Teilmengenrelationen und allgemeiner Ähnlichkeit. Aus dem Algorithmus entstehen mehrere Anwendungen rund um den Vergleich einzelner Muster und ganzer Sammlungen chemischer Muster. Sie können ohne weiteres Expertenwissen über einen Webserver benutzt werden.

In the context of chemistry and cheminformatics, there are different concepts of similarity. Substances can look similar, they can belong to the same class of compounds, they can be made from the same set of source reagents or have similar properties. Focusing on cheminformatics, those similarity measures are preferred that are easy to compute for a computer program. There, three dimensional surfaces, relative positions of functional groups in two and three dimensions, or the existence of certain substructures are used for similarity calculations. The project of this thesis is focused on similarity measures using maximum common substructures (MCS) which is integrated in two novel application scenarios. These substructures are calculated between a query and a target molecule. Therefore, a novel algorithm is introduced which is capable of solving the MCS problem in a variety of scenarios. The algorithm is designed for a lightweight, effcient and simple structure. Its further properties enable additional control of the computation of connected and disconnected common substructures and the application of additional constraints. As Final point of the initial development, the effciency of the method is shown in comparison to other state of the art algorithms. Afterwards the developed algorithm is used to scale up the MCS similarity concept from single comparisons on graphs or molecules into combinatorial compound libraries describing several billions of compounds. This requires adaptions to the problem solved and results in an integration of the previously developed algorithm into a larger workflow. This enables a focused enumeration of the most similar compounds in combinatorial compound libraries. Using the correspondingly developed computer program, the effciency of the concept and algorithm is demonstrated. Furthermore, its application shows the ease of using an MCS similarity search in commercial make-on-demand compound libraries for drug development endeavors. Finally the adaptions to the MCS method are used to transform the molecular similarity measure into a similarity concept for molecular patterns. There are a few concepts for molecular patterns in cheminformatics which all have in common that they represent molecular substructures. The introduction of a novel concept of generic molecular patterns enables comparisons of molecular patterns independent of their textual representation for the first time. These comparisons are based on an MCS calculation and cover determination of identical patterns, subset relations and similarity on those patterns in general. The applications derived from the developed algorithm cover single pattern comparisons and searching whole pattern collections. They are integrated into an easy to use webserver.