Vergleich molekularer Graphen mithilfe des SiDiff ...pi.informatik.uni-siegen.de/Projekte/sidiff/papiere/Grassow2008DA.pdf · Universität Siegen Fachbereich 12 - Elektrotechnik und

Universität Siegen Fachbereich 12 - Elektrotechnik und Informatik

Diplomarbeit

Vergleich molekularer Graphen mit Hilfe des SiDiff-Algorithmus

Oliver Grassow

Erstprüfer: Prof. Dr. Udo Kelter, Universität Siege n Zweitprüfer: Prof. Dr.-Ing. Madjid Fathi Torbaghan, Universität Siegen

Siegen, im November 2008

II

Inhaltsverzeichnis

1 Einleitung ........................................................................................................... 1

1.1 Aufgabenstellung und Motivation .............................................................. 1 1.2 Aufbau der Ausarbeitung ........................................................................... 2

2 Molekulare Graphen ......................................................................................... 4

2.1 Einordnung Wirkstoffentwurf .................................................................... 4 2.2 Aufbau und Eigenschaften molekularer Graphen ...................................... 5 2.3 Notationen und Dateiformate ..................................................................... 7 2.4 Feature Trees ............................................................................................ 10

3 Differenzberechnung mit SiDiff ..................................................................... 14

3.1 Der SiDiff-Algorithmus............................................................................ 14 3.2 Konfigurierbarkeit .................................................................................... 17 3.3 Anpassungserfordernisse .......................................................................... 19

4 Markierungsprozess funktioneller Gruppen ................................................ 23

4.1 Verwendete funktionelle Gruppen ........................................................... 23 4.2 Algorithmus zur Gruppenmarkierung ...................................................... 25

4.2.1 Verfahren zum Pattern Matching ...................................................... 25 4.2.2 Verfahren zur Markierung funktioneller Gruppen ............................ 28 4.2.3 Verwendeter Algorithmus ................................................................. 32

4.3 Dateiformat zur Speicherung .................................................................... 36

5 Integration in die Differenzberechnung ....................................................... 39

5.1 Datenmodell molekularer Graphen .......................................................... 39 5.2 Anpassung der Konfigurationsskripte ...................................................... 42

5.2.1 CandidatesConfig .............................................................................. 42 5.2.2 CompareConfig ................................................................................. 43 5.2.3 MatchingConfig ................................................................................ 49

5.3 Integration der Gruppenmarkierung ......................................................... 51 5.4 Verwendete Ähnlichkeitsmetriken ........................................................... 53

6 Ergebnisse ........................................................................................................ 56

6.1 Testumgebung .......................................................................................... 56 6.2 Testdatenbestand ...................................................................................... 56 6.3 Testläufe ................................................................................................... 58

6.3.1 Markierung funktioneller Gruppen ................................................... 59 6.3.2 Vergleich molekularer Graphen ........................................................ 61

III

6.4 Evaluierung der Ergebnisse ...................................................................... 67

7 Zusammenfassung und Ausblick ................................................................... 70

A Katalog funktioneller Gruppen ...................................................................... 72

Gruppen mit Kohlenstoff .................................................................................... 72 Gruppen mit Halogen ......................................................................................... 72 Gruppen mit Sauerstoff ...................................................................................... 73 Gruppen mit Stickstoff ....................................................................................... 74 Gruppen mit Phosphor ........................................................................................ 76 Gruppen mit Schwefel ........................................................................................ 76 Polyzyklische Kohlenstoffstrukturen ................................................................. 77

B Algorithmus zur Markierung funktioneller Gruppen .. ............................... 78

C Testergebnisse Gruppenmarkierung ............................................................. 80

Testläufe mit speziellen Teststrukturen .............................................................. 80 Testläufe mit Molekülen des Datenbestands ...................................................... 87 Laufzeiten für Gruppenmarkierung .................................................................... 88

D Testergebnisse Molekülvergleich ................................................................... 89

Getestete Konfigurationen .................................................................................. 89 Testläufe mit speziellen Teststrukturen .............................................................. 91 Testläufe mit Molekülen des Datenbestands ...................................................... 93 Laufzeiten für Molekülvergleiche .................................................................... 100

Literaturverzeichnis ........................................................................................... 101

IV

Abbildungsverzeichnis 2.1 Hierarchie der Repräsentationen ........................................................................ 5 2.2 Beispiele SLN und SMILES für einen aromatischen Ring ................................ 8 2.3 Beispiel einer MOL-Datei .................................................................................. 9 2.4 Beispiel CML-Datei aus Testdatenbestand ...................................................... 10 2.5 Beispiel zur Erzeugung eines Feature Tree ...................................................... 11

3.1 Datenmodell des SiDiff-Vergleichsalgorithmus .............................................. 15 3.2 Schematischer Ablauf der Matching-Phase ..................................................... 16 3.3 Korrespondenzbildung für zwei Moleküle ...................................................... 20 3.4 Zuordnungsproblematik bei gespiegelten Strukturen ...................................... 21

4.1 Beispielmuster für die Verbindungsklassen der Alkene und Nitrate ............... 24 4.2 Überblick über den rekursiven Pattern Matching Prozess ............................... 27 4.3 Beispiel verwendeter Datenstrukturen in [IGPM-VVS] .................................. 28 4.4 Beispielstrukturen für Algorithmus zur Markierung funktioneller Gruppen ... 29 4.5 Beispielbelegung Matching Tree bei Mustersuche .......................................... 30 4.6 Beispiel zur Ermittlung der kanonischen Nummerierung ................................ 32 4.7 Klassendiagramm der Molekülstruktur ............................................................ 33 4.8 Klassendiagramm der Verwaltungsstrukturen ................................................. 33 4.9 Beispielsituation bei Markierung eines Imide-Musters ................................... 35 4.10 DTD zur Definition der markierten Moleküle ............................................... 37 4.11 DTD zur Definition der Muster funktioneller Gruppen ................................. 38

5.1 Internes Datenmodell für die Differenzberechnung ......................................... 40 5.2 Molekül-Datenmodell im internen SiDiff-Graphen ......................................... 42 5.3 Auszug der CandidatesConfig zum Vergleich molekularer Graphen .............. 43 5.4 Auszug der CompareConfig ............................................................................. 48 5.5 Auszug aus MatchingConfig ............................................................................ 51 5.6 Markierte Strukturen für Vergleich .................................................................. 54

6.1 Zusammensetzung des Datenbestands ............................................................. 58 6.2 Zeitaufwand zur Markierung des Datenbestands ............................................. 61 6.3 Zeitaufwand zur Markierung einzelner Moleküle ........................................... 61 6.4 Korrespondenzbildung beim Vergleich von Molekül 5 mit Molekül 457 ....... 64 6.5 Aufwand zum Vergleich mit dem Datenbestand ............................................. 66

V

Zusammenfassung

Die Bioinformatik beschäftigt sich unter anderem mit dem medizinischen Teilbereich des Wirkstoffentwurfs. Ein wichtiger Schritt innerhalb dieses Prozesses ist die Ermitt-lung von Molekülstrukturen, die zu einem Anfragemolekül eine möglichst hohe strukturelle Ähnlichkeit aufweisen. Der in der Fachgruppe der Praktischen Informatik der Universität Siegen entwickelte SiDiff-Algorithmus erfüllt die Aufgabe, Differenzen zwischen unterschiedlichen Ver-sionen eines technischen Dokuments zu ermitteln und sehr detailliert anzuzeigen. Zu diesem Zweck werden die Dokumente intern in Graphen umgewandelt, die anschlie-ßend entsprechend des strukturellen Aufbaus sowie der Eigenschaften der Elemente verglichen werden. Aufgrund dieses strukturellen Vergleichsablaufs, der Hochkonfi-gurierbarkeit des Algorithmus und der ausgesprochen detaillierten Differenzermitt-lung wird in der vorliegenden Arbeit untersucht, inwieweit der SiDiff-Algorithmus geeignet ist, um molekulare Graphen effizient miteinander zu vergleichen. Im Rahmen dieser Arbeit wird ein Verfahren vorgestellt, mit dessen Hilfe Substruktu-ren in Form von funktionellen Gruppen in den zu vergleichenden Molekülen markiert werden können, um diese mit zusätzlichen Eigenschaften anzureichern. Ausgelegt auf den Vergleich dieser markierten Moleküle erfolgt anschließend eine Anpassung und Konfiguration des Vergleichswerkzeugs. Anhand eines Testdatenbestands wird die Genauigkeit und Effizienz der eingesetzten Verfahren untersucht.

1

1 Einleitung

1.1 Aufgabenstellung und Motivation

Im Rahmen der Softwareentwicklung, speziell dem Bereich der Softwaremodellie-rung, hat sich im Laufe der letzten Jahre die UML (Unified Modeling Language) mit ihren vielfältigen Diagrammtypen als Modellierungsstandard durchgesetzt. Der Ein-satz von Diagrammen bei der Softwareentwicklung unterstützt die Kommunikation sowohl der Anwender mit den Entwicklern als auch der Entwickler untereinander. Ein weiterer Grund für die Verwendung von Modellen stellt das Entwicklungskon-zept der MDA (Model Driven Architecture) dar, wonach ein Modell ein System auf einer höheren Abstraktionsstufe beschreibt als Code und somit der Code nur eine Ausgestaltung des Modells darstellen sollte (vgl. [Kel05]).

Während der gesamten Entwicklung, besonders jedoch in den frühen Entwick-lungsphasen, entstehen zahlreiche Dokumente, die durch sämtliche Phasen hindurch ständig bearbeitet und weiterentwickelt werden, was eine Versionierung dieser Do-kumente erforderlich macht. Verteilte Entwicklerteams und parallele Bearbeitung machen es häufig erforderlich, dass sich Entwickler die Differenzen zwischen zwei Versionen eines Dokuments ermitteln und anzeigen lassen müssen. Sowohl für die Differenzberechnung auf rein textbasierten Dokumenten, als auch für den Vergleich von Diagrammen, die durch einen hohen Grad an Strukturiertheit gekennzeichnet sind, haben sich mittlerweile mehrere Standards etabliert, die in gängigen Versions-managementsystemen zum Einsatz kommen. Im Fokus dieser Arbeit steht der SiDiff-Algorithmus, der dazu entwickelt wurde, Versionen technischer Dokumente, haupt-sächlich von UML-Diagrammen, zu vergleichen und deren Differenzen zu ermitteln. Zu diesem Zweck werden die Elemente der zu vergleichenden Dokumente zunächst in eine Graph-Darstellung transformiert, so dass der eigentliche Vergleichsvorgang im Folgenden auf diesen Graphen vorgenommen werden kann. Neben den rein struk-turellen Merkmalen werden auch die Eigenschaften der Elemente in diesen Ver-gleichsprozess miteinbezogen. Wie die bisherigen Untersuchungen zeigen, erreicht der SiDiff-Algorithmus gute Laufzeiten für den Vergleich kleiner Dokumente und akzeptable für den Vergleich großer Modelle, bei einer sehr geringen Fehlerrate (vgl. [Kel05]). Eine hohe Konfigurierbarkeit ermöglicht zudem die Anpassung an neue Dokumenttypen.

Im Rahmen zahlreicher Erweiterungen wurde dieser Algorithmus konsequent wei-terentwickelt und mittlerweile an die meisten gängigen Dokumenttypen der UML angepasst. Es stellt sich nun die Frage, inwieweit diese effiziente Umsetzung eines Algorithmus zum Vergleich graphartiger Dokumentstrukturen auch in anderen An-wendungsgebieten zum Einsatz kommen könnte. Ein mögliches Anwendungsfeld liegt dabei im Bereich der Bioinformatik.

1.2 Aufbau der Ausarbeitung

2

Die Bioinformatik, als Anwendungsdisziplin zur computergestützten Bearbeitung von Problemstellungen aus den Bereichen von Biologie und Chemie, beschäftigt sich unter anderem mit dem medizinischen Teilbereich des Wirkstoffentwurfs. Eine aus diesem Bereich stammende Aufgabenstellung ist der Vergleich eines Wirkstoff-Moleküls mit einer Datenbank, in der bereits bekannte Molekülstrukturen abgelegt wurden, um möglichst ähnliche Strukturen zu ermitteln. Ein Verfahren, das neben den rein strukturellen Vergleichen auch die Eigenschaften von Atom-Gruppierungen miteinbezieht, ist das der Feature Trees. Dabei werden in einem molekularen Gra-phen aus Atomknoten und Bindungskanten zunächst die funktionellen Gruppen mar-kiert, bevor im Anschluss der angereicherte Graph mit der Datenbank verglichen wird.

Die vorliegende Arbeit beschäftigt sich mit der Fragestellung, inwieweit der Si-Diff-Algorithmus geeignet ist, um molekulare Graphen strukturell miteinander zu vergleichen.


In Kapitel 2 wird das Anwendungsgebiet im Bereich der Bioinformatik genauer un-tersucht. Darin werden zunächst Art und Beschaffenheit molekularer Graphen erläu-tert und gängige Dateiformate mit dem in ihnen enthaltenen Informationsgehalt dis-kutiert. Das Verfahren der Gruppenmarkierung mithilfe von Feature Trees wird vor-gestellt und es wird gezeigt, inwieweit dieses Verfahren im Rahmen von SiDiff ein-gesetzt werden kann, um den Vergleichsprozess zu unterstützen.

Eine genaue Beschreibung der Funktionsweise des SiDiff-Algorithmus erfolgt in Kapitel 3 . Die Entwicklung des Algorithmus, der Vergleichsablauf sowie die Konfi-gurierbarkeit werden dabei ebenso behandelt wie die sich ergebenden Anpassungser-fordernisse, die vorzunehmen sind, um molekulare Graphen effizient miteinander vergleichen zu können.

Kapitel 4 beschäftigt sich mit dem Markierungsprozess der funktionellen Gruppen in den zu verwendenden Molekülstrukturen. Der gewählte Algorithmus zur Gruppen-identifizierung wird vorgestellt und gegen andere gängige Verfahren abgegrenzt. Die im Rahmen dieser Arbeit zu verwendenden Muster funktioneller Gruppen werden aufgezeigt und das neue Datenformat zur Speicherung der Moleküle, in dem die Gruppenmarkierungen enthalten sind, wird definiert.

Auf den eigentlichen Vergleich der Moleküle wird in Kapitel 5 eingegangen. Zu-nächst wird die Abbildung der Molekülelemente auf die Struktur des internen SiDiff-Graphen definiert, der für die Vergleiche verwendet wird. Dazu werden die anzupas-senden Konfigurationsskripte ermittelt und deren Struktur und Bedeutung aufgezeigt. Die erforderliche Integration der Komponente zur Markierung der funktionellen Gruppen wird abschließend behandelt.


3

Kapitel 6 befasst sich mit den eigentlichen Testläufen. Zunächst werden die Test-umgebung und die zu verwendenden Testdaten spezifiziert, bevor die Ergebnisse der einzelnen Testläufe aufgezeigt und evaluiert werden.

Abschließend wird in Kapitel 7 eine kurze Zusammenfassung der ermittelten Er-gebnisse geliefert und ein Ausblick auf mögliche Erweiterungen gegeben.

4

2 Molekulare Graphen

2.1 Einordnung Wirkstoffentwurf

Die Bioinformatik stellt eine Anwendungsdisziplin dar, in der es um die computerge-stürzte Bearbeitung von Fragestellungen aus den Bereichen Biologie und Chemie geht. Eine genauere Definition liefert ([Hüt06], S.3):

„Bioinformatik ist die Entwicklung und das Betreiben von Datenbanken, Software und mathematischen Werkzeugen zur Analyse, Organisation und Interpretation bio-logischer Daten.“

Eine klare Abgrenzung zu anderen Bereichen, wie beispielsweise der Physik oder

der Medizin, fällt aufgrund des eng miteinander verwobenen Charakters der Natur-wissenschaften ausgesprochen schwer. [Kel07] platziert in seiner Einführung zum Wirkstoffdesign die Bioinformatik zwischen der strukturellen Biologie und der Che-moinformatik, die beide neben vielen anderen Disziplinen wie der Pharmakologie, der Pharmazie und der Wirtschaftswissenschaften ebenso am Prozess des Wirkstoff-entwurfs beteiligt sind wie die Bioinformatik selbst. Im Rahmen der Analyse tritt in der Bioinformatik häufig die Problematik auf, biologische Strukturen miteinander zu vergleichen und eine möglichst gute Überdeckung zu erzielen. [Pol07] nennt als An-wendungsgebiete in diesem Zusammenhang das Sequenzalignment von DNA (deso-xyribonucleic acid) oder RNA (ribonucleic acid), die Interaktionsuntersuchungen von Proteinen im Rahmen der Proteomik und den Aufbau phylogenetischer Bäume ent-sprechend der evolutionären Ähnlichkeit von Organismen, Genen oder Proteinen. Auch im Prozess des Wirkstoffentwurfs stellt sich die Frage nach der Ähnlichkeit von Strukturen, in diesem Falle nach der Ähnlichkeit von Molekülstrukturen.

Beim Wirkstoffentwurf geht es darum, einen Wirkstoff zu entwickeln, der eine be-stimmte Wirkung im Organismus entfaltet. [Koh07] gliedert den Prozess zu dessen Erzeugung in die Schritte der Sammlung biologischer Daten, Ermittlung des Targets1, Identifizierung der Leitstruktur2, Optimierung der Leitstruktur bezüglich Nebenwir-kungen oder der Synthese, dem Prozess der prä-klinischen und klinischen Prüfung und schließlich der Zulassung in den jeweiligen Ländern. Von besonderer Bedeutung im Rahmen dieser Arbeit sind die Schritte der Identifizierung und der Optimierung der Leitstruktur. Als Leitstruktur dienen häufig kleine Moleküle, die an das zuvor identifizierte Target binden können. Beschrieben werden diese Moleküle durch mole-kulare Graphen, die, je nach Abstraktionsebene, einen unterschiedlichen Informati-onsgehalt aufweisen. Gerade im Bereich der Lead-Optimierung stellt sich die Frage,

1 Das Ziel, an dem die Wirkung entfaltet werden soll 2 Engl.: Lead; Substanz, die an das identifizierte Target binden kann

2.2 Aufbau und Eigenschaften molekularer Graphen

5

welche Molekülstrukturen der bereits bekannten und in Datenbanken hinterlegten Moleküle zu einer gefundenen Leitstruktur möglichst ähnlich sind. Ziel ist es ein Mo-lekül zu entdecken, das aufgrund seiner Struktur ebenfalls in der Lage ist, an das Tar-get zu binden und darüber hinaus noch weitere Vorteile mit sich bringt. Beispielswei-se könnte ein strukturähnliches Molekül einfacher zu synthetisieren sein oder im Körper geringere Nebenwirkungen verursachen. Ein wichtiger Schritt in diesem Zu-sammenhang ist also der Vergleich einer Molekülstruktur mit bereits bekannten Mo-lekülstrukturen, um strukturell Ähnliche zu identifizieren.


Moleküle sind Verbindungen aus zwei oder mehr Atomen (vgl. [Int08]). Jedes Atom hat einen spezifischen Elementtyp und verfügt entsprechend seiner Elektronenkonfi-guration über eine bestimmte Anzahl an Bindungen, die es mit anderen Atomen ein-gehen kann. Dabei können manche Atome auch Mehrfachbindungen mit anderen Atomen aufbauen, so dass man, bezogen auf die Bindung, von einer numerischen Ordnung dieser Bindung sprechen kann. Neben den Verbindungsinformationen ver-fügen Atome über weitere Eigenschaften wie die Atommasse, zugehörige Energieni-veaus und die Elektronegativität3.

Abbildung 2.1 Hierarchie der Repräsentationen (Quelle: [Koh07], Foliensatz „Chemoinformatik“, S.21), Rechts: Molekülbeispiel für 2D-Strukturdarstellung

3 Elektronegativität beschreibt Fähigkeit der Atome, Bindungselektronen in kovalenten Bindungen

an sich zu ziehen und stellt somit ein Maß für die Bindungsfähigkeit (nach [Blu06])


6

Molekulare Graphen können auf unterschiedlichen Abstraktionsebenen betrachtet werden, wie in Abbildung 2.1 schematisch dargestellt ist. Auf der untersten Ebene besteht ein Molekül lediglich aus der Summenformel, die angibt, aus welchen Ato-men es zusammengesetzt ist (vgl. [Lat08]). Informationen darüber, welche Atome miteinander verbunden sind, lassen sich häufig nicht eindeutig ableiten. Die nächst-höhere Ebene beinhaltet Informationen darüber, welche Atome miteinander verbun-den sind, so dass sich eine zweidimensionale Struktur ergibt. Diese Ebene wird häu-fig zur Modellierung und zur Verdeutlichung chemischer Reaktionen verwendet. Üb-licherweise werden zur Darstellung Atomknoten mit ihrem Elementtyp beschriftet und Bindungskanten entsprechend ihrer Ordnung durch eine oder mehrere Linien repräsentiert (vgl. [Koh07]). Durch die Kristallographie kann die räumliche Anord-nung von Atomen ermittelt werden, woraus sich Längen und Winkel der Verbindun-gen berechnen lassen. Als Ergebnis dieser Analyse erhält man das geometrische, dreidimensionale Modell eines Moleküls als weitere Stufe der Abstraktionshierarchie. Auf der letzten Stufe werden schließlich Informationen über die Oberflächenstruktur des Moleküls hinzugefügt. Dabei handelt es sich um Charakteristika bestimmter Re-gionen, die entscheidend dafür sind, mit welchen Bereichen anderer Moleküle diese reagieren können. Ähnlich dem Schlüssel-Schloss-Prinzip gibt die Oberflächenstruk-tur darüber Auskunft, ob und wie zwei Stoffe miteinander in Verbindung treten kön-nen, inwieweit sie zusammen „passen“.

Wie in Abbildung 2.1 deutlich wird, werden die betrachteten Strukturen von der untersten zur obersten Ebene hin zunehmend komplexer, was sich auch im Aufwand für erforderliche Vergleiche widerspiegelt. Während ein Summenformelvergleich einem reinen Textvergleich entspricht, sind im dreidimensionalen Raum aufwendige Rotationen und Translationen erforderlich, um Elemente aufeinander abbilden zu können. Aus diesem Grund wurden für jede betrachtete Ebene diverse Verfahren entwickelt, um einen effizienten Vergleich zu ermöglichen. Häufig erfolgt die Suche nach einer ähnlichen Struktur daher gestaffelt, beginnend auf der untersten Ebene. Auf jeder Ebene wird die Restmenge der Elemente, die noch als Kandidaten für eine möglichst hohe Ähnlichkeit in Frage kommen, entsprechend des Informationsgehalts der Stufe ausgewertet und reduziert. Auf diese Weise kann eine, auf der untersten Ebene noch sehr große Kandidatenmenge, Stufe für Stufe reduziert werden, bis schließlich auf der obersten Ebene nur noch wenige Moleküle mit aufwendigen Ver-fahren verglichen werden müssen.

Hauptgegenstand dieser Arbeit ist der Vergleich molekularer Graphen auf der zweidimensionalen Ebene, da der SiDiff-Algorithmus für den strukturellen Vergleich von Graphen ausgelegt ist (vgl. Abbildung 2.1 rechts). Ein Graph G=(V, E) wird durch eine Atom-Knotenmenge V und eine Bindungs-Kantenmenge E beschrieben. Die Bindungskanten sind ungerichtet und aufgrund der Bindungseigenschaften der Atome kann der Graph Zyklen enthalten. Ein weiteres Merkmal molekularer Graphen ist die Eigenschaft, dass die Atom-Knoten einen beschränkten Grad von nicht mehr als acht Kanten haben können. Zudem sind bis auf wenige hundert polyzyklische Mo-

2.3 Notationen und Dateiformate

7

lekülstrukturen alle Graphen planar und somit kreuzungsfrei darstellbar (vgl. [Koh07]).


Insgesamt existieren mehrere Dutzend mögliche Notationsarten und Datenformate zur Repräsentation molekularer Informationen. Gerade im Bereich zur zwei- und dreidi-mensionalen Modellierung haben sich jedoch einige wenige Standards herausgebil-det, auf die im Folgenden genauer eingegangen wird.

Eines der gebräuchlichsten Formate zur zweidimensionalen Repräsentation stellt die SMILES-Notation (Simplified Molecular Input Line Specification) dar. Diese Notation beinhaltet Informationen über die enthaltenen Elemente, die Bindungen zwischen den Elementen, Ringsysteme, Chiralität4 und Ladungen. Es handelt sich dabei um eine Zeilennotation, bei der Atome mit dem Großbuchstaben für ihr Ele-ment dargestellt werden. Einfachbindungen sowie Wasserstoffatome werden implizit angenommen, Doppel- und Dreifachbindungen werden mit den Symbolen „=“ und „#“ dargestellt. Verzweigungen innerhalb der Struktur werden anhand der Klamme-rung deutlich gemacht. Atome, die in einem Ring angeordnet sind (aromatisch), wer-den mit einem kleinen Buchstaben notiert und der Ringschluss mit Ziffern vermerkt. Es existieren weitere Symbole für zusätzliche Informationen. Die wesentlichen Vor-teile dieses Verfahrens liegen in der kompakten Notation und der wohldefinierten Grammatik, die beide eine einfache Lesbarkeit der Ausdrücke ermöglichen. Als prob-lematisch hervorzuheben ist, dass mehrere SMILES für dieselbe Struktur existieren können, sowie die beschränkten Darstellungsmöglichkeiten von im Wirkstoffentwurf sehr häufig auftretenden Aromatizität-Ringstrukturen. Erstgenannte Problematik wird mit einer Erweiterung des SMILES-Standards, den sogenannten USMILES (Unique SMILES), adressiert.

Als eine alternative Zeilennotation zu SMILES kommt SLN (Sybyl Line Notation) zum Einsatz. Im Gegensatz zu SMILES werden Wasserstoffatome hier explizit ange-geben. Verbindungen in Ringstrukturen erhalten einen Index in eckigen Klammern an der Startposition und ein „@“-Symbol als Ringschlusssymbol. Zum Ausdruck der Aromatizität wird bei dieser Notation ein Vermerk bei den Bindungen (mithilfe eines „:“-Symbols), und nicht, wie bei SMILES, bei Atomen und Bindungen angelegt. Ab-bildung 2.2 zeigt exemplarisch den Einsatz beider Notationen zur Darstellung einer aromatischen Ringstruktur.

4 Die Chiralität, oder auch Enantiomorphie (in der Kristallographie) bezeichnet die räumliche

Anordnung von Atomgruppierungen derart, dass diese durch Drehung nicht zur Deckung ge-bracht werden können (vgl. [Lat08, Kapitel 1 ])


8

Abbildung 2.2 Beispiele für SLN und SMILES für einen aromatischen Ring (Quelle Notation: [Koh07], Foliensatz „Chemoinformatik“, S.48)

Beide Verfahren haben die Eigenschaft, dass mit ihnen Informationen über den to-pologischen Aufbau und Inhalt der Moleküle notiert werden können, ohne dabei Koordinaten zu verwenden. Gerade bei großen Molekülen mit komplexen Ringsys-temen wird die Zeilennotation aufgrund der umfangreichen Klammerung jedoch schnell unübersichtlich. Zudem sind häufig dreidimensionale Koordinaten für eine präzisere Beschreibung der Molekülstruktur erforderlich. Im Folgenden werden daher drei gängige Dateiformate im Bereich der dreidimensionalen Modellierung hervorge-hoben.

Als Standard zur dreidimensionalen Notation gilt das von MDL (Molecular Design

Limited) entwickelte MOL-Format (Molecule) für einzelne Strukturen. Eine MOL-Datei besteht aus fünf Blöcken und verwendet ein spaltenbasiertes Speicherformat je Block. Der erste Block entspricht einem Header mit generellen Daten zum verwende-ten Programm, Erstellungsdatum, Molekülnamen und weiteren internen Informatio-nen. Im zweiten Block wird die Anzahl der Atome und Bindungen aufgeführt, die Anzahl zusätzlicher Eigenschaften-Zeilen am Ende der Datei sowie die Notations-Versionsnummer. Im dritten Block werden nun zunächst die Atome spezifiziert. Be-ginnend mit den X-, Y- und Z-Koordinaten folgen der Elementtyp sowie Informatio-nen über die Ladung. Die eigentliche Struktur ergibt sich mithilfe der im darauffol-genden Block festgehaltenen Bindungsinformationen. In den ersten beiden Spalten werden die Nummern der verbundenen Atome angegeben, gefolgt von der Ordnung der Bindung. Mit Hilfe von Atom- und Bindungstabelle lässt sich die dreidimensiona-le Struktur eines Moleküls herleiten. Im letzten Block werden schließlich zusätzliche Eigenschaften sowie das Ende der MOL-Datei deklariert. Neben den genannten In-formationen können noch viele weitere Daten, beispielsweise aus dem Bereich der Stereochemie, in MOL-Dateien gespeichert werden. In Abbildung 2.3 wird beispiel-haft die MOL-Datei einer kleinen molekularen Struktur dargestellt.


9

Abbildung 2.3 Beispiel einer MOL-Datei (Quelle: [Koh07], Foliensatz „Chemoinformatik“, S.51)

Ein weiteres weit verbreitetes Format ist das PDB-Format (Protein Data Bank). Die Protein Data Bank stellt eine der großen im Web frei zugänglichen Datenbanken dar und beinhaltete nach eigenen Angaben im April 2008 bereits 50.000 Strukturen (vgl. [Pro08]). Auch dieses Format verwendet eine Spaltennotation mit Atom- und Bindungstabellen. Für jedes Atom werden die dreidimensionalen Koordinaten festge-halten und es kann vermerkt werden, ob ein Atom ein Heteroatom ist, was in diesem Zusammenhang bedeutet, dass es Teil eines kleinen molekularen Kofaktors ist (vgl. [Ato08]). Verwendung findet dieses Format im Unterschied zu MOL aber hauptsäch-lich bei der Codierung von Proteinen und nicht von kleinen Molekülen.

Das CML-Format (Chemical Markup Language) stellt schließlich das dritte hier

vorstellte Format dar. Dabei handelt es sich um eine auf XML (eXtensible Markup Language) basierende Notation zur Repräsentation chemischer Informationen mithil-fe von Tags. Als Wurzel des Dokuments befindet sich auf der obersten Ebene ein molecule-Element, dem eine Identifikationsnummer sowie der Name des Moleküls als Attribute beigefügt werden können. Weitere Eigenschaften können in Form zu-sätzlicher Tags innerhalb des molecule-Elements angegeben werden. Die beiden we-sentlichen Elemente innerhalb des molecule-Tags sind das AtomArray-Element zur Deklaration von Atominformationen sowie das BondArray-Element als Container für Bindungsstrukturinformationen. Damit stimmt der Aufbau prinzipiell mit den zuvor beschriebenen Formaten derart überein, dass alle drei Verfahren zunächst die Atome und anschließend die Bindungen beschreiben. Atom-Elemente innerhalb des AtomAr-rays können über eine ganze Reihe von Attributen verfügen, darunter eine eindeutige ID, der Elementtyp sowie die X-, Y- und Z-Koordinaten. Die Bond-Elemente im Rahmen des BondArray verfügen über ein Attribut atomRefs2, welches als Wert die IDs der verbundenen Atome enthält. Neben weiteren möglichen Attributen verfügen Bindungen noch über den Grad der Bindung sowie eine dokumentweit eindeutige ID (nach [CML03]). Abbildung 2.4 zeigt zur Verdeutlichung des strukturellen Aufbaus die CML-Datei eines einfachen Moleküls. Hauptvorteile der CML liegen vor allem in der klaren Struktur, die validierbar ist und für die Parser mit wenig Aufwand ge-schrieben werden können. Obwohl noch nicht sehr weit verbreitet, ist dieses Format

2.4 Feature Trees

10

als Standard etabliert und verfügt über eine umfangreiche Spezifikation. Negativ macht sich der Speicherplatzbedarf bemerkbar, der aufgrund der umfangreichen Tag-Struktur die anderen Formate übertrifft.

Abbildung 2.4 Beispiel CML-Datei aus Testdatenbestand

Bei der Vielzahl vorhandener Notationen und Formate stellt sich die Frage, in-wieweit zwischen den unterschiedlichen Repräsentationen konvertiert werden kann. Tatsächlich existieren sehr viele mittlerweile veraltete Formate, sowie unvollständige und zum Teil fehlerhafte Daten (vgl. [Koh07]), so dass entsprechende Filterimple-mentierungen sehr aufwendig sind. Häufig werden daher von kommerziellen Prog-rammpaketen Schnittstellen angeboten, um bearbeitete Strukturen in einer Vielzahl von Formaten zu speichern und zu exportieren. Im Open Source-Bereich existiert das Programm „Open Babel: The Open Source Chemistry Toolbox“, das laufend weite-rentwickelt wird und mittlerweile mit etwa 90 unterstützten chemischen Formaten genutzt werden kann, um zwischen den unterschiedlichen Darstellungen zu wechseln (siehe [Ope08]). Alle der zuvor vorgestellten Formate können mit diesem Tool inei-nander überführt werden, was es ermöglicht, die im Rahmen dieser Arbeit vorzuneh-menden Anpassungen am SiDiff-Algorithmus basierend auf nur einem Format durch-zuführen. Aufgrund der bei der Entwicklung von SiDiff bisherigen Ausrichtung auf XMI-Dokumente (vgl. Kapitel 3 ) sowie der aufgezeigten Vorteile der CML, eignet sich dieses auf XML basierende Format in besonderem Maße als Grundlage zur Spei-cherung der zu vergleichenden molekularen Graphen.

2.4 Feature Trees

Aus dem Bereich des strukturellen Vergleichs zweier Moleküle stammt ein Verfah-ren, das mithilfe speziell angereicherter Molekülgraphen, sogenannter Feature Trees, versucht, eine möglichst gute Überdeckung zu erzielen. Auch wenn die verwendeten Algorithmen zum eigentlichen Vergleich der erzeugten Bäume grundsätzlich anders arbeiten als der SiDiff-Algorithmus, so besitzen die Schritte zur Anreicherung der

2.4 Feature Trees

11

Graphen doch eine gewisse Relevanz im Rahmen dieser Arbeit. Aus diesem Grund wird im folgenden Kapitel das Verfahren der Feature Trees kurz erläutert und es werden die Bereiche aufgezeigt, die für die Anpassung des SiDiff-Algorithmus rele-vant sind.

Der Grundgedanke beim Feature Tree Verfahren ist der, in einem molekularen Graphen Gruppierungen von Atomen und Bindungen mit bestimmten Eigenschaften zu identifizieren und so auf einen neuen Knoten zu reduzieren, dass der entstehende Graph ein Baum ist (siehe Abbildung 2.5). Jedes Atom des Graphen ist in mindestens einem Knoten des Feature Trees enthalten. Sind zwei Atome benachbart, oder ist ein Atom Teil zweier Knoten des Feature Trees, so werden die beiden Knoten mit einer Kante verbunden, wodurch die Topologie des ursprünglichen Graphen erhalten bleibt. Einfache Zyklen im molekularen Graphen werden ebenfalls auf einen Knoten abge-bildet. Polyzyklische Strukturen können bis zu einem gewissen Grad auf eine sternar-tige Knotenstruktur reduziert werden.

Abbildung 2.5 Beispiel zur Erzeugung eines Feature Tree durch Reduktion der mit Kreisen markierten Atomgruppierungen auf einen neuen Knoten des Feature Tree (Quelle: [Rar98], S.471)

Im Anschluss an die strukturelle Erzeugung des Baums erfolgt die Zuweisung der

Eigenschaften, unterschieden nach sterischen und chemischen Features. Sterische Eigenschaften beschreiben das Fragment in Bezug auf seine Größe, wofür häufig die

2.4 Feature Trees

12

Anzahl der Atome und das Van-der-Waals-Volumen5 verwendet werden. Chemische Eigenschaften definieren eine Art Wechselwirkungsprofil mit anderen Substanzen, beispielsweise die Hydrophobizität6. Für jedes Feature werden drei Funktionen defi-niert. Die erste, die Generatorfunktion, berechnet den Wert der Eigenschaft für ein gegebenes Fragment. Die Komparatorfunktion liefert für ein Paar von Eigenschafts-werten einen Ähnlichkeitswert im Bereich [0..1], mit Eins für identisch und Null für keine Ähnlichkeit. Die Kombinationsfunktion schließlich bildet zwei Eigenschafts-werte auf einen einzelnen ab, der konsistent sein muss mit dem Wert, den die Genera-torfunktion für die Vereinigung der beiden Fragmente berechnet hätte. Im Anschluss an diese Anreicherung des Graphen findet der eigentliche Vergleichsvorgang über ein sogenanntes Matching statt, bei dem versucht wird, Teilbäume von Feature Tree A auf Teilbäume von B abzubilden. Ein solches Matching ist gültig, wenn die Abbil-dung Topologie erhaltend ist und jeder Knoten höchstens in einem Match auftritt (vgl. [Koh07]). Über weitere Nebenbedingungen lässt sich die Qualität des Matchings beeinflussen. Hierzu zählen das Gewichtungsverhältnis zwischen sterischen und chemischen Eigenschaften sowie die maximale Größe der zu matchenden Teilbäume. Zum eigentlichen Vergleich der Feature Trees werden drei Algorithmen verwendet: Split Search, Match Search und Split Search mit 1-Shifts, die alle über eine vergleich-bare Leistungsfähigkeit verfügen. Grundgedanke der Verfahren ist der, durch Schnitte in beiden Bäumen Teilbäume zu erzeugen, die dann aufeinander abgebildet werden können. Als abschließende Betrachtung lässt sich festhalten, dass Feature Trees im Bereich des topologischen Vergleichs sehr effizient sind. In ihrer Leistungsfähigkeit lassen sie sich zwischen Fingerprints7 und echten geometrischen 3D-Strukturvergleichen einordnen. Kritisch zu sehen ist die Eigenschaft, dass große mak-rozyklische Systeme mit Feature Trees nicht bearbeitet werden können.

Wie sich im folgenden Kapitel zeigen wird, sind bisherige von SiDiff unterstützte

Dokumenttypen dadurch gekennzeichnet, dass die zu vergleichenden Elemente eine Vielzahl von Eigenschaften besitzen, die für die Berechnung eines Ähnlichkeitswer-tes herangezogen werden können. Ein reiner molekularer Graph verfügt im Gegensatz dazu über viele Elemente, die relativ wenige Eigenschaften besitzen und zudem, je-weils paarweise betrachtet, sehr ähnlich sein können. Als Beispiel können hier Koh-len- oder Wasserstoff-Atome genannt werden, die sehr häufig auftreten, sich im Hinblick auf ihre Eigenschaften jedoch, wenn überhaupt, kaum unterscheiden. Aus diesem Grund erscheint eine Anreicherung des molekularen Graphen mit zusätzlichen Eigenschaften von Vorteil. Im Folgenden wird daher das Verfahren aus dem Bereich der Feature Trees verwendet, um in einem molekularen Graphen bestimmte Atom-

5 Das Volumen, das ein Atom (oder eine Atomgruppierung) basierend auf seinem Van-der-Waals-

Radius (Radius, in den sich kein anderes Atom annähern kann) besitzt (vgl. [Mol96]) 6 Definiert, ob eine Atomgruppierung wasserlöslich (hydrophil) oder wasserunlöslich (hydrophob)

ist (vgl. [Wie04]) 7 Verfahren, bei dem das Vorhandensein bestimmter Eigenschaften oder Molekülfragmente auf die

Bitpositionen eines Bitvektor abgebildet wird (vgl. [Koh07], Foliensatz „2D-Ähnlichkeit“)

2.4 Feature Trees

13

gruppierungen zu markieren. Dabei steht jedoch nicht die Eliminierung von Zyklen im Vordergrund, die vom SiDiff-Algorithmus ohnehin bearbeitet werden können, sondern die Markierung von sogenannten funktionellen Gruppen (siehe Abbildung 4.1). Dabei handelt es sich um in der organischen Chemie häufig vorkommende Ver-bindungen aus zwei oder mehr Atomen, deren chemische Eigenschaften wohlbekannt sind. Von großer Bedeutung sind funktionelle Gruppen, wenn es darum geht, die Wechselwirkungsmöglichkeiten zweier Moleküle zu untersuchen. Beim Einsatz des SiDiff-Algorithmus können sie zudem verwendet werden, um die zu vergleichenden Moleküle mit zusätzlichen Eigenschaften zu versehen und somit die Genauigkeit bei der Ähnlichkeitsbestimmung zu erhöhen (vgl. Kapitel 3 ). Auf den Prozess der Grup-penmarkierung sowie die zu markierenden funktionellen Gruppen wird ausführlich in Kapitel 4 eingegangen.

14

3 Differenzberechnung mit SiDiff

Der SiDiff-Algorithmus wurde 2004 im Rahmen einer Diplomarbeit an der Fach-gruppe der Praktischen Informatik mit dem Ziel entwickelt, zwei Versionen eines UML-Dokuments miteinander zu vergleichen und die Gemeinsamkeiten und Unter-schiede zu ermitteln (vgl. [Weh04]). Bis zu diesem Zeitpunkt konnte beim Vergleich zweier Dokumente innerhalb einer Dokumenthistorie eine Zuordnung der korrespon-dierenden Elemente lediglich anhand ihrer IDs vorgenommen werden. Gerade im Hinblick auf in der Praxis häufig genutztes Reverse-Engineering, bei dem die IDs der ursprünglichen Modellelemente nicht mehr vorhanden sind, war dieses Vorgehen nicht mehr zeitgemäß. Die ursprüngliche Version von SiDiff adressierte diese Prob-lematik, indem für den Vergleich von Modellelementen Ähnlichkeitsmetriken zum Einsatz kamen, die Elemente aufgrund ihrer Eigenschaften und Attribute vergleichen und zuordnen konnten. Dazu werden die existierenden Elemente eines Dokumenttyps mit ihren Eigenschaften zunächst spezifiziert und anschließend mit Gewichtungen und Schwellwerten versehen.

Während in der ursprünglichen Version zunächst Klassen- und Zustandsdiagram-me unterstützt wurden, erfolgte im Rahmen einer weiteren Diplomarbeit eine Anpas-sung an Anwendungsfall-, Aktivitäts-, Sequenz- und Kommunikationsdiagramme, sowie eine Verfeinerung der zuvor bereits unterstützten beiden Diagrammtypen (sie-he [Gad07]). Parallel dazu wurde der Algorithmus intern weiterentwickelt und opti-miert, beispielsweise in der Vergleichsphase durch den Einsatz einer multidimensio-nalen Suchbaumstruktur zur Reduktion der Anzahl benötigter Elementvergleiche (vgl. [Tre07]). Bei der Entwicklung standen zwei Aspekte stets im Vordergrund: der Algorithmus sollte zum einen hoch konfigurierbar, zum anderen möglichst einfach an neue Dokumenttypen anzupassen sein. In diesem Kapitel wird zunächst die Funkti-onsweise des SiDiff-Algorithmus erläutert und aufgezeigt, welche Konfigurations-schritte zur Unterstützung des neuen Dokumenttyps erforderlich sind.

3.1 Der SiDiff-Algorithmus

Der grundsätzliche Ablauf beim Vergleichsvorgang ist unabhängig vom untersuchten Dokumenttyp und wird daher zunächst allgemein betrachtet. [Kel05] liefert eine aus-führliche Beschreibung und wird, sofern nicht anders vermerkt, als Hauptquelle ver-wendet.

In einem ersten Schritt werden die Eingabedokumente eingelesen und die enthal-tenen Elemente in das interne Datenmodell überführt. Wie die Dokumentelemente dabei auf die Datenmodellelemente abzubilden sind, wird durch ein Mapping in einer


15

für den jeweiligen Dokumenttyp spezifischen Konfigurationsdatei definiert. Wurde der interne SiDiff-Graph aufgebaut, erfolgen Vergleich und Auswertung in zwei Pha-sen.

Abbildung 3.1 Datenmodell des SiDiff-Vergleichsalgorithmus (Quelle: [Kel05], S.5)

Zunächst werden im Schritt der Korrespondenzerkennung8 Elemente in Dokument

A und B ermittelt, die einander entsprechen. Für diese Zuordnung sind keine eindeu-tigen Identifizierer erforderlich, sondern es werden vielmehr die Eigenschaften der Elemente für den Vergleich herangezogen. Für je zwei Elemente wird dazu ein Ähn-lichkeitswert über die Attribute der Elemente und deren Umgebung, also Referenzen und Hierarchiebeziehungen, gebildet. Welche Ähnlichkeitsmerkmale dazu herange-zogen werden sollen, wie diese zu gewichten und welche Schwellwerte zu überschrei-ten sind, erfolgt auf Basis einer weiteren dokumenttypspezifischen Konfigurationsda-tei (vgl. [Kel071])). Liegt der ermittelte Ähnlichkeitswert über dem definierten Schwellwert kommen die Elemente als Kandidaten in Frage. Dieser Prozess der Ähn-lichkeitswertermittlung erfolgt in zwei Richtungen: Bottom-up und Top-down (vgl. Abbildung 3.2). In der ersten Phase wird Bottom-up von den Blattknoten hin zur Wurzel des Graphen jedes Element mit den in Frage kommenden Elementen aus dem anderen Graphen verglichen und es werden die Ähnlichkeitswerte bestimmt. Ergibt dieser Vergleich für zwei Elemente in beiden Richtungen einen Ähnlichkeitswert, der höher ist als für jedes andere verglichene Elementpaar, so werden diese Elemente als Korrespondenzen erkannt und als einander entsprechend zugeordnet. In diesem Fall schaltet der Algorithmus in das Top-down Verfahren, indem die zuvor erkannte Kor-respondenz an die Kindelemente propagiert wird, woraufhin deren Ähnlichkeitswerte

8 Als Korrespondenz bezeichnet man ein Paar von Komponenten aus zwei Dokumenten, die inhalt-

lich gleich sind und einander entsprechen (nach [Kel071])


16

basierend auf den neuen Erkenntnissen erneut berechnet werden. Stellt sich auch hier zwischen zwei Elementen ein einzigartiger Ähnlichkeitswert heraus, so werden auch diese einander zugeordnet und das Verfahren läuft Top-down weiter. Der Algorith-mus stoppt, sobald alle Elemente Bottom-up verglichen wurden. Um auch in zykli-schen Strukturen und in Strukturen, die durch eine hohe Anzahl von Abhängigkeits-beziehungen gekennzeichnet sind, möglichst alle Korrespondenzen zu entdecken, läuft der gesamte Algorithmus mehrere Male Bottom-up über den Graphen, was sich in der Praxis als ausreichend herausgestellt hat.

Abbildung 3.2 Schematischer Ablauf der Matching-Phase (Quelle: [Weh04])

Im Anschluss an die Korrespondenzbildung folgt die Differenzermittlung und Ausgabe. In dieser Phase werden die Elemente entsprechend ihrer Differenzen in eine von vier Kategorien eingeteilt. Als Struktur-Differenzen werden Elemente klassifi-ziert, zu denen keine Korrespondenz gefunden werden konnte. Dazu zählen Elemen-te, die zu keinem anderen Element eine Ähnlichkeit über dem spezifizierten Schwellwert erreicht haben, sowie Elemente, für die mehrere Kandidaten mit einem identischen Ähnlichkeitswert existieren, so dass keine eindeutige Entscheidung ge-troffen werden kann, welchem es zugeordnet werden soll. Die Klasse der Attribut-Differenzen beinhaltet Korrespondenzen, bei denen sich ein oder mehrere Attribut-werte geändert haben. Referenz-Differenzen beziehen sich auf Veränderungen bei referenzierten Elementen einer Korrespondenz. Die letzte Kategorie, die Klasse der Verschiebungs-Differenzen, umfasst alle Elemente, bei denen sich das Eltern-Element verändert hat. Geordnet nach diesen Kategorien enthält die Ausgabe alle Elemente aus beiden Dokumenten.

Um den Vorgang der Korrespondenzerkennung zu optimieren, existieren in der ak-tuellen SiDiff-Version zwei Verfahren. Das eine Verfahren berechnet in einem vorge-lagerten Schritt den Hashwert der enthaltenen Elemente, welcher aus dem Hashwert

3.2 Konfigurierbarkeit

17

des Pfades zu dem jeweiligen Element, den Hashwerten der Namen der Unterelemen-te sowie den Hashwerten der Pfade von referenzierten Elementen gebildet wird. Über einen Vergleich der Hashwerte lassen sich Korrespondenzen ohne oder mit nur gerin-gen Unterschieden dann schnell erkennen. Kritisch zu diesem Verfahren ist anzumer-ken, dass aufgrund der Einbeziehung der Pfadangaben sowohl des Elements selbst, als auch der referenzierten Elemente, Verschiebungen nicht erkannt werden können. Das zweite Verfahren verwendet eine mehrdimensionale Suchstruktur, den S³V-Baum, in dem ähnliche Elemente zunächst benachbart angeordnet werden. Anstatt nun jedes Element mit jedem anderen möglichen Kandidaten zu vergleichen, wird der Vergleich nur noch mit im Baum benachbarten Elementen vorgenommen (vgl. [Tre07]). Kritisch bei diesem Verfahren ist, geeignete Merkmale für die Organisation des S³V-Baums sowie eine geeignete Anzahl von zu untersuchenden Nachbarelemen-ten zu wählen.

Als Dokumentformat für bisher unterstützte UML-Diagrammtypen kommt XMI (XML Metadata Interchange) zum Einsatz. Es ist in besonderer Weise zur Speiche-rung von Diagrammen geeignet, da sich Eingabedokumente toolspezifisch mit zusätz-lichen Eigenschaften anreichern lassen und Referenzen zwischen Modellelementen über idref-Attribute umgesetzt werden können (vgl. [Kel05]). Diese Eigenschaften sorgen dafür, dass XMI nicht nur für UML-Diagramme geeignet ist, sondern auch für andere Arten von strukturierten, diagrammähnlichen Dokumenten. Das Datenmodell des internen SiDiff-Graphen ist aus diesem Grunde so gestaltet, dass auch XMI Da-teien verglichen werden können, die keine UML-Diagramme darstellen (vgl. Abbil-dung 3.1). Gerade diese Eigenschaft macht es möglich, den SiDiff-Algorithmus auch für den Vergleich jeglicher anderer graphartiger Strukturen einzusetzen, was den Vergleich von molekularen Graphen erst ermöglicht.

Zur Unterstützung des neuen Dokumenttyps sind mehrere Konfigurationsskripte erforderlich, mit denen über eine Reihe von Parametern und Funktionen der Ver-gleichsvorgang gesteuert wird. Diese Konfigurationsdateien werden im Folgenden kurz beschrieben, um die komplexen Möglichkeiten zur Konfigurierung des Algo-rithmus deutlich zu machen und die abschließenden Überlegungen zu benötigten An-passungserfordernissen zur Unterstützung des neuen Dokumenttyps einzuleiten.


Bei der Anpassung zur Unterstützung eines neuen Dokumenttyps kann an nahezu jeder Stelle des Vergleichsvorgangs über eine Konfigurationsdatei steuernd auf den Ablauf Einfluss genommen werden. Sämtliche verwendeten Konfigurationsdateien basieren auf XML, was Erzeugung, Bearbeitung sowie Validierung erheblich erleich-tert. Im Folgenden werden die Schlüsselstellen im Vergleichsablauf mit den zugehö-rigen Konfigurationsdateien genauer betrachtet.


18

Im ersten Schritt ist zu überlegen, wie die Elemente des zu vergleichenden Doku-menttyps auf das interne SiDiff-Datenmodell abgebildet werden können. Da bisher unterstützte Dokumenttypen im XMI-Format vorlagen und somit auf XML basierten, konnte diese Abbildung mit Hilfe eines XSL Stylesheet (Extensible Stylesheet Lan-guage) vorgenommen werden. Auf diese Weise können eingelesene Eingabeelemente einfach mit xsl-Befehlen in die entsprechenden Datenmodell-Elemente transformiert werden. Dieser Schritt ist von entscheidender Bedeutung, da je nach Art der Abbil-dung der Vergleichsvorgang mehr oder weniger effizient arbeiten kann, im schlimm-sten Falle sogar überhaupt keine brauchbaren Resultate liefert. Es ist also auf eine Abbildung zu achten, die einfach genug strukturiert ist, um effizient durchlaufen wer-den zu können, aber auch komplex genug, um später aussagekräftige Ähnlichkeits-merkmale zu entdecken.

Wurden das Datenmodell erzeugt und die Eingabedokumente eingelesen, können anschließend die zu vergleichenden Elemente genauer spezifiziert werden. Diese Spezifikation der sogenannten Candidates erfolgt in einer weiteren Konfigurationsda-tei. Für jeden Elementtyp können darin Regeln definiert werden, die zutreffen müs-sen, damit ein Element des Typs aus dem einen Dokument überhaupt mit einem ande-ren Element des zweiten Dokuments verglichen wird. Somit lässt sich bereits vor Beginn des eigentlichen Vergleichsvorgangs die Menge der zu vergleichenden Ele-mente entscheidend einschränken, was gerade bei einer großen Anzahl an Elementen einen wesentlichen Einfluss auf die Laufzeit des Algorithmus haben kann.

Im Anschluss an die Kandidateneinschränkung startet der eigentliche Prozess der Korrespondenzerkennung. In der sogenannten MatchingConfig-Konfigurationsdatei wird zunächst die Implementierung des iterativen Matchers gewählt, welcher derzeit der standardmäßige DefaultMatcher ist. Für diesen ist es erforderlich, die Reihenfol-ge zu spezifizieren, in der die Dokumentelementtypen zu betrachten sind. Neben die-ser Beschreibung des iterativen Zuordnungs-Ablaufs müssen für jeden Elementtyp noch weitere Parameter definiert werden, die angeben, welche Nebenbedingungen erfüllt sein müssen, um zwei Elemente des Typs einander zuzuordnen. So kann mit der Option parentForceMatch beispielsweise angegeben werden, ob für ein Zuord-nung bereits die Elternelemente der betrachteten Elemente zugeordnet sein müssen.

Wesentlicher Kern der Ähnlichkeitswertberechnung ist die CompareConfig-Konfigurationsdatei, in der für jeden Elementtyp spezifiziert wird, wie der Ähnlich-keitswert zu berechnen ist und welche Schwellwerte überschritten werden müssen. Für jeden Knotentyp kann eine Reihe von Vergleichsfunktionen definiert werden. Diese Funktionen können Elternknoten, Attribute, Kindknoten oder auch referenzier-te Knotenmengen vergleichen. Als Resultat liefern sie einen Ähnlichkeitswert zwi-schen Null und Eins, wobei Null absolut keine Ähnlichkeit und Eins völlige Identität darstellen. Für jede dieser Funktionen kann eine Gewichtung ebenfalls im Wertebe-reich [0..1] angegeben werden, die prozentual angibt, inwieweit das Ergebnis der Funktionsauswertung in den Gesamtwert des Elements einfließen soll. Auf Element-typebene wird ein Schwellwert definiert, der mindestens erreicht werden muss, damit

3.3 Anpassungserfordernisse

19

zwei Elemente als Korrespondenzen in Frage kommen (vgl. [Ben08]). Liegt nach Auswertung der Funktionen und der Multiplikation mit den Gewichtungsfaktoren der ermittelte Ähnlichkeitswert für ein Paar von Elementen über diesem definierten Schwellwert, so kommen die beiden Elemente als Korrespondenz in Frage. Wird für kein anderes Paar von Elementen, in denen eines der beiden Elemente enthalten ist, ein gleicher oder höherer Ähnlichkeitswert ermittelt, so werden die beiden Elemente als Korrespondenz markiert.

Neben den hier vorgestellten Konfigurationsdateien besteht noch die Möglichkeit, den internen SiDiff-Graphen vor Beginn des Vergleichsvorgangs mit zusätzlichen Informationen anzureichern. Diese Anreicherung konnte zum Zeitpunkt dieser Arbeit jedoch noch nicht über eine externe Datei konfiguriert werden, weshalb diese zukünf-tig vorhandene Funktionalität hier nicht genauer betrachtet werden kann.


Nachdem nun sowohl die Grundlagen über den Aufbau und die Eigenschaften mole-kularer Graphen als auch über die Funktionsweise und Konfigurationsmöglichkeiten des SiDiff-Algorithmus herausgearbeitet wurden, können im Folgenden die erforder-lichen Anpassungen untersucht und spezifiziert werden.

Zu den standardmäßigen Anpassungen gehört die Erstellung der erforderlichen Konfigurationsskripte. Zunächst muss eine Abbildung der Elemente aus molekularen Graphen auf entsprechende Strukturen des internen SiDiff-Datenmodells erarbeitet werden. Wurde diese Abbildung festgelegt, kann ein Skript erstellt werden, welches die molekularen Eingabedokumente in den internen SiDiff-Graphen transformiert. Da mit der CML ein Datenformat zur Speicherung molekularer Graphen auf Basis von XML vorliegt, kann diese Transformation analog zu bisherigen Dokumenttypen mit Hilfe von XSL-Stylesheets erfolgen. Zur Einschränkung der Kandidatenvergleichs-menge können bestimmte Attribute der Elemente in molekularen Graphen ausgenutzt werden, wie beispielsweise der Elementtyp der Atome, was eine Erstellung der Can-didatesConfig-Konfigurationsdatei sinnvoll erscheinen lässt. Für den Ablauf des Ver-gleichsvorgangs und die Ähnlichkeitswertberechnung sind die MatchingConfig- und CompareConfig-Dateien, basierend auf den gewählten Strukturen des Datenmodells, anzulegen. Im Hinblick auf die Eigenschaft molekularer Graphen, viele Elemente mit relativ wenigen einzigartigen Merkmalen zu besitzen, wird im Rahmen der Compa-reConfig die Ermittlung der Ähnlichkeitswerte stark von der Betrachtung der Ele-mentumgebungen beeinflusst werden.

Gerade die Eigenschaft von Molekülen, viele gleichartige Elemente zu enthalten, die sich einzig durch ihre strukturelle Platzierung im Graphen unterscheiden, ist in keinem der bisher unterstützten Dokumenttypen vorhanden. Betrachtet man daher die Elemente ohne Berücksichtigung der Umgebung, so ergibt sich für viele Elementpaa-re ein identischer Ähnlichkeitswert, der dazu führt, dass keine Entscheidung getroffen


20

werden kann, welche einander zuzuordnen sind. Aufgrund des strukturellen Aufbaus von Molekülen mit zyklischen Strukturen und einer nicht selten vorkommenden Symmetrie kann jedoch auch unter Einbeziehung der Umgebung häufig keine eindeu-tige Entscheidung getroffen werden, wie in Abbildung 3.3 beispielhaft dargestellt wird. Das Sauerstoffatom aus Molekül A sowie das über eine Doppelbindung damit verbundene Kohlenstoffatom können aufgrund der Umgebung eindeutig den entspre-chenden Strukturen aus Molekül B zugeordnet werden. Die beiden daran anschlie-ßenden Teilbäume sind jedoch vollkommen identisch, so dass eine eindeutige Zuord-nung nicht möglich ist. Eng verbunden mit dieser Problematik besteht die Schwierig-keit, bei einem ersten Vergleichsdurchlauf mindestens eine Korrespondenz zu finden, die dann als Fixpunkt genutzt werden kann, um Elemente in deren Umgebung nach und nach ebenfalls einander zuordnen zu können. Abbildung 3.4 zeigt zur Verdeutli-chung zwei identische Moleküle, bei deren Vergleich keine Atome oder Bindungen eindeutig einander zugeordnet werden können, so dass die benötigten Fixpunkte voll-ständig fehlen. Es scheint daher erforderlich, den molekularen Graphen mit zusätzli-chen Eigenschaften zu versehen, so dass bestimmte Strukturen möglichst schon in einem ersten Durchlauf als Korrespondenzen erkannt werden können.

Abbildung 3.3 Korrespondenzbildung für zwei Moleküle, bei denen die Abbildung der Teilbäume nicht eindeutig ist (grün: eindeutige Zuordnung; rot: keine eindeutige Zuordnung)

Eine mögliche Lösung für diese Problematik stammt aus dem zuvor beschriebenen

Bereich der Feature Trees, bei dem Atomgruppierungen mit bestimmten Eigenschaf-ten markiert werden. Während bei Feature Trees zyklische Strukturen und funktio-

?


21

nelle Gruppen markiert werden, sind für den Vergleich mit SiDiff funktionelle Grup-pen ausreichend, da Zyklen durch mehrfache Iterationen des Algorithmus bearbeitet werden können. Werden in einem molekularen Graphen die funktionellen Gruppen markiert, so ergeben sich bei einem Vergleich mit einem zweiten markierten Gra-phen, im Falle von gemeinsamen funktionellen Gruppen, weitere Fixpunkte. Zudem können durch die Korrespondenzbildung zweier Gruppen bereits mehrere Atome und Bindungen als Korrespondenzen vermerkt werden.

Die Markierung der funktionellen Gruppen lässt sich aufgrund der beschränkten Anzahl und des strukturellen Aufbaus der Muster sehr effizient durchführen. Da der zu vergleichende Datenbestand nur ein einziges Mal markiert und gespeichert werden muss, ergibt sich für die Laufzeit des eigentlichen Vergleichsvorgangs lediglich ein zusätzlicher Aufwand für die einmalige Markierung der Gruppen in der Anfragestruk-tur. Der gewählte Algorithmus sowie das Format zur Speicherung der markierten Mo-leküle werden ausführlich im folgenden Kapitel behandelt.

Abbildung 3.4 Zuordnungsproblematik bei gespiegelten Strukturen trotz funktioneller Gruppen (orange: Carbonyl-Gruppe)

Selbst mit der Verwendung funktioneller Gruppen sind einige wenige Fälle sym-

metrischer Strukturen denkbar, bei denen aufgrund mehrerer Kandidaten keine Ent-scheidung über eine eindeutige Korrespondenzbildung getroffen werden kann (vgl. Abbildung 3.4). Dies resultiert in einem geringeren Ähnlichkeitswert aufgrund einer geringeren Anzahl an korrespondierenden Elementen, obwohl die verglichenen Mo-leküle unter Umständen sogar identisch sein können. Um auch diese Strukturen zu unterstützen, wäre ein mengenbasierter Ansatz denkbar, der aufgrund der Ähnlich-keitswerte der nicht-korrespondierenden Restelemente und einiger einfacher Aus-schlusskriterien eine Menge noch möglicher Korrespondenzen berechnen könnte. Basierend auf den tatsächlich zugeordneten Elementen und der Menge der möglichen Korrespondenzen ließe sich dann ein weiterer Ähnlichkeitswert berechnen, der die maximal mögliche Ähnlichkeit darstellt. Für das Gesamtergebnis einer Anfrage könn-

?


22

te über einen Gewichtungsparameter definiert werden, inwieweit der rein strukturelle SiDiff-Ähnlichkeitswert und der mengenmäßige Ähnlichkeitswert der Restelemente die Ergebnismenge beeinflussen. Diese Überlegungen werden in Kapitel 5.4 vertieft.

Ein weiterer Anpassungsbedarf besteht in der Umstellung auf den Vergleich eines Dokuments mit mehreren anderen. Bisher stand der Vergleich zweier Dokumente im Mittelpunkt, bei dem detailliert Gemeinsamkeiten und Unterschiede ermittelt und angezeigt wurden. Um ein Anfragemolekül mit einem Datenbestand zu vergleichen, ist es dagegen erforderlich, die einzelnen Strukturvergleiche anzustoßen, die ermittel-ten Ähnlichkeitswerte zu speichern und dann schließlich nur für die ähnlichsten Strukturen die detaillierte Ausgabe zu erzeugen. Für die effiziente Umsetzung unters-tützt SiDiff ein sogenanntes Graph-Repository, in das mehrere Graphen zu Beginn geladen werden können und auf dem dann die einzelnen Vergleiche ausgeführt wer-den. Die Menge der Graphen, die in diesem Respository abgelegt werden können, ist hauptspeicherabhängig, so dass zur Verwendung großer Datenbestände eine partielle Bearbeitung mit anschließender Zusammenfügung der Ergebnisse erforderlich wird.

23

4 Markierungsprozess funktioneller Gruppen

Wie in Kapitel 2.4 bereits erläutert, handelt es sich bei funktionellen Gruppen um wohlbekannte und häufig auftretende Atom- und Bindungsgruppierungen mit be-stimmten Eigenschaften. Häufig stellen sie Charakteristika eines Molekülbereichs dar, die dafür entscheidend sind, mit welchen Bereichen anderer Substanzen diese in Verbindung treten können. Als Unterstützung im Vergleichsprozess können sie zu-dem als mögliche Fixpunkte für den Algorithmus in der Matching-Phase dienen.

Die Problematik, ein Muster in einem Graphen zu finden, lässt sich auf das Prob-lem der Subgraph-Isomorphie zurückführen, welches zur Klasse der NP-vollständigen Probleme zählt (vgl. [Var061]). Es handelt sich also um ein Entschei-dungsproblem, für das kein Algorithmus bekannt ist, der in polynomieller Zeit eine Lösung berechnen kann. In der Praxis sorgen einige problemspezifische Nebenbedin-gungen jedoch häufig dafür, dass viele Probleme dennoch effizient lösbar sind, bei-spielsweise Charakteristika der Graphstruktur oder der zu verwendenden Muster. Aus diesem Grund ist zunächst eine Eingrenzung und Untersuchung der zu markierenden Muster notwendig, um anschließend einen geeigneten Algorithmus wählen zu kön-nen.

4.1 Verwendete funktionelle Gruppen

Als Merkmal für die Einteilung in funktionelle Gruppen dient der Elementtyp der jeweiligen Gruppe. Jede funktionelle Gruppe besteht aus mindestens einem Grund-atom, das seinerseits Bindungen zu anderen Atomen besitzt. Je nach Elementtyp die-ses Grundatoms erfolgt eine erste Klassifizierung in Gruppen mit Schwefel (S), Phosphor (P), Stickstoff (N), Sauerstoff (O) und Kohlenstoff (C). Innerhalb dieser Gruppen existieren mehrere Muster, die genau die Atomtypen und Bindungsgrade spezifizieren, die mit diesem Startatom verbunden sein müssen, damit es sich um die jeweilige funktionelle Gruppe handelt. Jede Gruppe besitzt mindestens eine Bindung zum Rest des Moleküls, der durch ein Wildcard-Element9 (R) dargestellt wird. Abbil-dung 4.1 zeigt anhand zweier funktioneller Gruppen den Aufbau der Muster.

9 Symbol für beliebiges anderes Zeichen (nach [Def08])

4.1 Verwendete funktionelle Gruppen

24

Abbildung 4.1 Beispielmuster für die Verbindungsklassen der Alkene und Nitrate (Quelle der Strukturen: [Str96])

Untersucht man die Muster auf strukturelle Überdeckung, also darauf, inwieweit ein Muster Teil eines anderen Musters ist, so lässt sich bei manchen Mustern eine derartige Abhängigkeit ausmachen. Gerade innerhalb der Gruppierungen um einen bestimmten Startatomtyp existieren derartige Abhängigkeitsbeziehungen, jedoch auch in wenigen Fällen über diese Gruppengrenzen hinaus. Untersucht man diese Abhän-gigkeitsbeziehungen genauer, ergibt sich eine Hierarchie von Mustern, welche die Reihenfolge definiert, in der diese in einem molekularen Graphen zu markieren sind. Auf der obersten Ebene liegen die Muster, die Schwefel enthalten, gefolgt von Phos-phor, Stickstoff, Sauerstoff und schließlich Kohlenstoff. Die verwendeten Muster, eingeteilt in die beschriebene Hierarchie, werden in Kapitel A des Anhangs aufge-zeigt. Da die Atomtypen Schwefel bis Sauerstoff deutlich seltener auftreten als Koh-lenstoff, besitzt eine markierte Gruppe aus dieser Kategorie eine deutlich höhere Aus-sagekraft als eine markierte Kohlenstoffverbindung in dem Sinne, dass sie eine höhe-re Wahrscheinlichkeit hat, bei ähnlichen Strukturen als Fixpunkt für den Vergleich zu dienen. Ein wesentlicher Vorteil dieser Gruppeneinteilung entsprechend dem Start-atomtyp des Musters liegt darin, dass für einen Algorithmus nicht alle Muster durch-probiert werden müssen, sondern nur die, bezogen auf einen Startknoten, passenden Muster, was die Menge bereits erheblich einschränkt. Darüber hinaus sind die meis-ten Muster nicht sonderlich komplex mit einer Atomanzahl von vier bis acht Atomen zusammen mit einer entsprechenden Bindungsanzahl. Eine Ausnahme zu dieser Re-gel stellen polyzyklische Kohlenstoffverbindungen dar, die aufgrund ihrer Ringstruk-turen eine höhere Zahl von Atomen und Bindungen erreichen können. Es stellt sich jedoch die Frage, bis zu welchem Grad eine Markierung polyzyklischer Kohlenstoff-verbindungen im Hinblick auf die Erzeugung vergleichbarer Charakteristika über-haupt sinnvoll ist. [Lip08] analysiert die strukturelle Vielfalt der in der CAS registry (Chemical Abstracts Service) erfassten organischen Substanzen. Im Rahmen ihrer Untersuchungen stellen sie eine Übersicht der häufig enthaltenen heterozyklischen Strukturen dar, woraus ersichtlich wird, das gerade einfache Strukturen mit wenigen Zyklen sehr häufig vorkommen, komplexe Ringsysteme dagegen seltener. Natürlich würde bei einem Match zweier markierter, hochkomplexer Ringsysteme direkt eine hohe Ähnlichkeit erkannt werden. Andere Strukturen jedoch, die nur leichte Abwei-chungen zu diesem Ringsystem aufweisen, würden in diesem Fall keinen weiteren

4.2 Algorithmus zur Gruppenmarkierung

25

Fixpunkt enthalten und eine Überlagerung würde erschwert. Aus diesem Grund wer-den für die Gruppenmarkierung im Rahmen dieser Arbeit funktionelle Gruppen mit bis zu drei zusammenhängenden Ringstrukturen verwendet, da diese nach [Lip08] relativ häufig auftreten und somit zur Ermittlung von Fixpunkten geeignet sind. Eine genaue Spezifizierung der polyzyklischen Verbindungen findet sich in [Hel74].

Insgesamt ergibt sich damit ein Katalog von etwa 60 Mustern funktioneller Grup-pen, die im Folgenden in molekularen Graphen zu identifizieren und zu markieren sind. Diese werden im Anhang mit Namen, Struktur und Ranking-Position für die Reihenfolge der Musterüberprüfung aufgelistet.


Aus den im vorherigen Abschnitt angestellten Überlegungen zu Art und Struktur der Muster ergeben sich die Merkmale und Nebenbedingungen, die für eine effiziente Gestaltung des Algorithmus von Bedeutung sind. Zu nennen sind die geringe Ge-samtanzahl und die einfache Struktur der zu markierenden Muster, die hierarchische Ordnung sowie die Eigenschaft, bei der Mustersuche mit einem Startatom eines be-stimmten Typs beginnen zu können. Bevor auf einen Algorithmus eingegangen wird, der diese Nebenbedingungen berücksichtigt, soll zunächst eine kurze Übersicht über andere mögliche Verfahren gegeben werden.

4.2.1 Verfahren zum Pattern Matching

Es existieren mehrere Verfahren, die darauf abzielen, alle möglichen Isomorphismen zwischen zwei Graphen G und G‘ zu berechnen. [Ull76] verwendet dazu einen einfa-chen Suchbaum-Algorithmus, in dem alle möglichen Relations-Matrizen so angelegt sind, dass an den Blättern Kandidaten für gültige Isomorphismen zu finden sind. Für jeden dieser Kandidaten muss getestet werden, ob die durch die untersuchte Matrix erzeugte Abbildung die Isomorphie-Bedingungen erfüllt. Durch eine Verfeinerung, die einige Schritte bei der Kandidatenermittlung einspart und zudem den Suchbaum reduziert, lässt sich die Menge der zu testenden Matrizen einschränken. [Val97] ent-wickelte basierend darauf einen Algorithmus, der bei nicht-zusammenhängenden Mustern jede Komponente des Musters auf den Zielgraph abbilden kann. Erwähnung findet hier, dass bei einem attributierten Graph nicht nur die Struktur, sondern auch die Attribute der Knoten und Kanten entscheidend für die Ermittlung einer Isomor-phie sind. Da gerade die Attribute der Atome und Bindungen für eine Zuordnung ent-scheidend und die Muster alle zusammenhängende Komponenten sind, würde ein solcher Ansatz zu viele Vergleiche erfordern.

Einen anderen Ansatz wählt [Che081], bei dem eine Mustererkennung in einem gerichteten Graph durch eine Reihe von R-join-Operationen (reachability join) auf einer Graph-Datenbank vorgenommen wird, die Graphen in Tabellen speichert. Dazu


26

werden zunächst Cluster-basierte Indizes angelegt, die angeben, welche Tupel über Tabellen verknüpft sind, um im Folgenden mit einem Zwei-Schritt R-join-Algorithmus die Erreichbarkeit zu überprüfen. Eine Musterermittlung erfolgt dann über einen Vergleich der Erreichbarkeit der Knoten sowie deren Labels. Während dieses Verfahren sehr effizient auf großen, gerichteten Graphen arbeitet, erscheint eine Anpassung an ungerichtete und Zyklen enthaltende Graphen nur schwer mög-lich. Abgesehen davon würde eine Umstellung auf eine relationale Datenbank erfor-derlich, was auch auf Seiten des Vergleichstools zu umfangreichen Anpassungserfor-dernissen führen würde.

[Var07] nutzen bei der Mustersuche einen rekursiven Ansatz, der berücksichtigt,

dass ein Muster seinerseits aus anderen Mustern bestehen kann. Aus diesem Grund wird zum Zeitpunkt des Kompilierens zunächst für jedes Muster die Aufrufstruktur der Elemente in einem sogenannten Call Plan definiert. Dieser wird anschließend so umgeformt, dass er auf Basis einer globalen Suchstrategie möglichst effizient genutzt werden kann (Flattened Pattern). In einem letzten Schritt vor der Ausführung wird schließlich ein sogenannter Search Graph gebildet, der entsprechend möglicher Pa-rametereingaben für jedes Flattened Pattern eine Suchstrategie definiert. Zur Laufzeit wird zu dem Search Graph der zugehörige Search Plan aufgrund der nun bekannten Parameter erstellt. Mithilfe einer sogenannten Magic Set Transformation wird der Search Plan entsprechend der rekursiven Aufrufe so zerschnitten und mit Zusatzin-formationen angereichert, dass in einem bottom-up Prozess der Matcher nicht-relevante Zuordnungen ignorieren kann. Der daraus resultierende Rule Goal Graph liefert damit schließlich die Regeln, die iterativ bottom-up abgearbeitet werden kön-nen (vgl. Abbildung 4.2). Dieses Verfahren findet hauptsächlich Anwendung im Be-reich der Graph-Transformationen und wurde bei [Var07] in VIATRA210 realisiert. Interessant im Rahmen dieser Arbeit ist die Betrachtungsweise eines Musters als Menge von Sub-Mustern, die einen rekursiven Ablauf nahelegt. Des Weiteren liefert die Eigenschaft funktioneller Gruppen, mit einem bestimmten Startatom zu beginnen, einen Ansatzpunkt für eine Suchstrategie ähnlich des beschriebenen Search Graph Verfahrens.

10 VIATRA2 (Visual Automated Model Transformations) stellt zur Ergänzung existierender Mo-

dell-Transformations-Frameworks seinerseits ein Framework zur Unterstützung von Spezifikati-on, Design, Ausführung, Validierung und Wartung von Transformationen zur Verfügung (vgl. [VIA08])

Abbildung 4.2 Überblick über den rekursiven Pattern Matching Prozess nach [RGPM

[Var06] beschreiben in

gorithmus für eine inkrementelle Mustersuche, die ebenfalls im Bereich der GraphTransformationen zum Einsatz kommt. Transformations-Tools (mit dem alle komplettenstimmten Search Plan ermittelt wurden, in einem Der Matching Tree wird inkrementell mit jedem gefundenen schen Muster und ModellStrukturen und einem Benachrichtigungsmter überprüft werden können, die einen möglichen positiven Match ungültig machen würden. Da die Muster der funktionellen Gruppen hierarchisch geoeiner bestimmten Reihenfolge zu markieren sind, ist einnicht erforderlich. Der vorgestellte Abladie Markierung funktioneller Gruppen in vielen Bereichen geeignet und wird daher im Folgenden kurz beschrieben.

Während der Mustersuche werden Knoten des Musters entsprechenden Elementen aus dem Modell so zugeormit KantenbeschriftungenSubgraph des Mustergraphen, so dass ters ein Teil des gesamten MustersPlan, der angibt, in welcher Reihenfolge sen werden sollen, wird in jedem Schritt Musters einem Element des Modells zugeordnet. dies, dass in jedem Schritt das muster durch die neue Bindung ching Tree angelegt, in dem den. Eine Zuordnung auf der Stufe Submusters. Wie diese Submuster den Stufen des Baumes zuzuordnen sinddurch den Search Plan definiert.


Überblick über den rekursiven Pattern Matching Prozess nach [RGPM[Var07], S.5)

in ihrer Arbeit grundsätzliche Datenstrukturen und einen Aeine inkrementelle Mustersuche, die ebenfalls im Bereich der Graph

onen zum Einsatz kommt. Unabhängig von gängigen (Graph Transformation Tools) wird ein Verfahren

alle kompletten und nicht-erweiterbaren Zuordnungen, die nach einem bermittelt wurden, in einem Matching Tree gespeichert werden.

wird inkrementell mit jedem gefundenen Elementschen Muster und Modell erweitert. Besonders ist, dass mithilfe der vorgestellten

Benachrichtigungsmechanismus zeitgleich auch negative Muter überprüft werden können, die einen möglichen positiven Match ungültig machen

Da die Muster der funktionellen Gruppen hierarchisch geordnet und somit in einer bestimmten Reihenfolge zu markieren sind, ist eine solche Funktionalität hier nicht erforderlich. Der vorgestellte Ablauf bei der Mustersuche dagegen erscheint für die Markierung funktioneller Gruppen in vielen Bereichen geeignet und wird daher

beschrieben. Während der Mustersuche werden Knoten des Musters entsprechenden Elementen

aus dem Modell so zugeordnet, dass die Korrespondenzbildung (Matchingbeschriftungen, Start- und Zielknoten ist. Ein Submuster wird definiert als

Subgraph des Mustergraphen, so dass mit einem kompletten Matchingters ein Teil des gesamten Musters zugeordnet wurde. Entsprechend eines

in welcher Reihenfolge Musterelemente Modellelementen zugewisen werden sollen, wird in jedem Schritt eine weitere Komponente (Musters einem Element des Modells zugeordnet. Betrachtet als Submuster

, dass in jedem Schritt das k-te Submuster erweitert wird, indem das muster durch die neue Bindung zugeordnet wird. Für jedes Muster P

angelegt, in dem Zuordnungen für Elemente des Musters organisiert weauf der Stufe k des Baums repräsentiert ein Matching des

Submusters. Wie diese Submuster den Stufen des Baumes zuzuordnen sinddefiniert. Die Blätter des Baumes stellen somit maximale pa

Algorithmus zur Gruppenmarkierung

27

Überblick über den rekursiven Pattern Matching Prozess nach [RGPM-VHV] (Quelle:

grundsätzliche Datenstrukturen und einen Al-eine inkrementelle Mustersuche, die ebenfalls im Bereich der Graph-

Unabhängig von gängigen Graph-wird ein Verfahren erläutert,

, die nach einem be-gespeichert werden.

Element-Match zwi-dass mithilfe der vorgestellten

echanismus zeitgleich auch negative Mus-ter überprüft werden können, die einen möglichen positiven Match ungültig machen

rdnet und somit in solche Funktionalität hier

uf bei der Mustersuche dagegen erscheint für die Markierung funktioneller Gruppen in vielen Bereichen geeignet und wird daher

Während der Mustersuche werden Knoten des Musters entsprechenden Elementen Matching) konsistent

uster wird definiert als Matching eines Submus-

Entsprechend eines Search Musterelemente Modellelementen zugewie-

Komponente (Variable) des htet als Submuster bedeutet

Submuster erweitert wird, indem das k+1-te Sub-Pn wird ein Mat-

für Elemente des Musters organisiert wer-des Baums repräsentiert ein Matching des k-ten

Submusters. Wie diese Submuster den Stufen des Baumes zuzuordnen sind, wird stellen somit maximale par-


28

tielle Zuordnungen des Musters dar. Bei einem Muster Pn mit n zuzuordnenden Ele-menten bedeutet ein Matching auf der maximalen Stufe n somit einen kompletten Match des Musters. Zur Speicherung, welche Musterknoten auf welche Modellknoten abgebildet wurden, wird ein Binding Array verwendet, in dem die gebildeten Paare abgelegt werden. Um Zuordnungen bei Modelländerungen zu benachrichtigen, wer-den für Einfüge- sowie Löschoperationen Notification Arrays vorgehalten, in denen die zu benachrichtigenden Matchings vermerkt werden. Die verwendeten Datenstruk-turen zusammen mit einer Beispielbelegung werden in Abbildung 4.3 dargestellt. Der Matching Tree mit dem Namen LHS in Abbildung 4.3(b) stellt darin den Baum für das zu erkennende Muster dar, während NAC den Baum eines negativen Musters rep-räsentiert.

Abbildung 4.3 Beispiel verwendeter Datenstrukturen in [IGPM-VVS] (Quelle: [Var06], S.6)

Während der inkrementellen Ausführungsphase erfolgt die Steuerung über vier

grundlegende Operationen. Werden Elemente hinzugefügt, so erweitert die insert()-Operation das jeweilige Submuster, validate() steuert rekursiv die Erweiterung mit insert() über alle Submuster. Werden Matchings entfernt, so kann mit delete() ein gesamter Baumzweig ab dem benannten Matching gelöscht werden. Invalidate() ist dann für die rekursive Entfernung aller Zuordnungen von Kindelementen des aktuel-len Matchings zuständig.

4.2.2 Verfahren zur Markierung funktioneller Gruppen

In Anlehnung an das zuvor beschriebene Verfahren lässt sich auch für die Muster funktioneller Gruppen eine Art Search Plan erstellen. Abbildung 4.4 zeigt als Bei-spiel die Molekülstruktur (a), in der der die funktionelle Gruppe (b) zu markieren ist. Aus der Gruppendefinition lässt sich der Search Plan (c) ableiten. Entsprechend der Musterdefinition können die Atome in einer bestimmten Reihenfolge auf die Knoten


29

des Moleküls abgebildet werden. Da die zu markierenden Gruppen ausgehend von einem bestimmten Startknoten häufig in mehrere Richtungen zu entwickeln sind, er-gibt sich eine baumartige, rekursive Aufrufstruktur. Bildet die Zuordnung des Start-atoms die Wurzel des Musters, so stellen die Zweige Submuster dar, die ihrerseits als Wurzel das jeweilige Matching der direkt benachbarten Atome besitzen. Entspre-chend rekursiver Aufrufe wird jedes Submuster erweitert, indem seine Submuster zugeordnet werden. Ein Submuster ist komplett zugeordnet, sobald alle Zweige des Submusters zugeordnet wurden. Für Muster, die Zyklen enthalten, würde bei Errei-chen eines bereits zugeordneten Knotens rekursiv zurückgesprungen, so dass sich auch für diese eine Baumstruktur ergibt.

Die Zuordnungsspeicherung der Muster-Molekül-Knotenpaare könnte ähnlich der

in [Var06] vorgestellten Binding Arrays vorgenommen werden, wie in Abbildung 4.5 dargestellt. Die Abbildung zeigt die Molekülstruktur, den Matching Tree und das Binding Array zu einem Zeitpunkt, zu dem bereits das Stickstoffatom sowie zwei der drei Sauerstoffatome zugeordnet wurden. Zwei der drei Submuster, die unterhalb des Muster-Startatoms angeordnet sind, wurden bereits vollständig abgearbeitet. Zum dargestellten Zeitpunkt wurde gerade das Sauerstoffatom Oc des Musters dem Sauers-toffatom O2 des Moleküls zugeordnet, wodurch das zweite Submuster vervollständigt wurde. Als nächstes wird das dritte Submuster auf den Molekülgraph abgebildet, in-dem im Molekül eine Entsprechung für Od gesucht wird.

Da keine zwei Muster zeitgleich verarbeitet werden müssen, ist ein Notification-Mechanismus nicht erforderlich. Für die Bearbeitung wird ein sehr ähnlicher Funkti-onsumfang benötigt. Analog zu insert() ist eine Erweiterung des jeweiligen Submus-ters durch Hinzufügen des nächsten Matchings vorzunehmen. Kann ein unvollständi-ges Submuster nicht erweitert werden, so muss sein Wurzel-Matching entfernt und

(a) Molekülstruktur (b) Graph funktioneller Grup pe (c) Search Plan

N

O

DB EB EB

EB

Abbildung 4.4 Beispielstrukturen für den Algorithmus zur Markierung funktioneller Gruppen (DB=Doppelbindung; EB=Einzelbindung) (Quelle Abb.(b): [Str96], S.9)


30

zurückgesprungen werden. Dafür wird eine Funktionalität ähnlich der delete()-Operation erforderlich. Wurden zu diesem Zeitpunkt bereits andere Submuster unter der betroffenen Wurzel zugeordnet, so müssen diese Matchings mit den entsprechen-den Verwaltungsstrukturen ebenfalls zurückgesetzt werden, was der invalidate()-Operation entspricht. Aufgrund der Eigenschaft molekularer Graphen, viele sehr ähn-liche Elemente zu enthalten, ist die Entscheidung, welches benachbarte Atom mit dem nächsten Musterknoten zuzuordnen ist, häufig nicht eindeutig. An diesen Stellen ist eine probeweise Bildung aller möglichen Kombinationen bis zur Ermittlung einer, auch für darunterliegende Submuster, gültigen Zuordnung erforderlich. Weitere Merkmale funktioneller Gruppen sowie der Moleküle sorgen für eine starke Ein-schränkung der zu testenden Muster.

Wird die Suche nach einem Muster mit einem bestimmten Startatomtyp begonnen,

so schränkt alleine diese Bedingung die Menge der zu testenden Muster erheblich ein. Organische Moleküle sind dadurch gekennzeichnet, dass sie hauptsächlich aus Koh-len- und Wasserstoffatomen bestehen und andere Atomtypen wie Schwefel, Phos-phor, Stickstoff und Sauerstoff deutlich seltener vorkommen. Beginnt man bei der Gruppenmarkierung bei den selteneren Atomen, was die hierarchische Strukturierung der funktionellen Gruppen möglich macht, so lassen sich die Muster mit der höchsten

DB EB EB

EB

Na

Ob Oc Od

Re

Na Ob Oc Od Re

N1 O3 O2

Binding Array

Matching Tree

Molekülstruktur

Abbildung 4.5 Beispielbelegung Matching Tree und zugehöriger Binding Array bei Mustersuche


31

Priorität gleich zu Beginn abarbeiten. Da diese nicht sonderlich zahlreich sind und zudem eine geringe Komplexität besitzen, lässt sich mit wenigen Knotenvergleichen entscheiden, ob ein Muster passt oder nicht, was ein Abarbeiten der Muster ermög-licht. Viele dieser Muster enthalten zudem auch Kohlen- und Wasserstoffatome, so dass beim Match eines Musters zugleich die Restmenge der noch zu überprüfenden und häufig zahlreichen Kohlenstoffatome reduziert wird.

Wurden alle funktionellen Gruppen um die selten vorkommenden Elementtypen markiert, folgen schließlich die Kohlenstoffgruppen. Aufgrund der polyzyklischen Strukturen mit bis zu 23 Atomen sind die Muster, die zu Beginn getestet werden müs-sen, deutlich komplexer. Darüber hinaus stellt sich bei Mustern, die komplett aus Kohlenstoffatomen bestehen, die Frage, mit welchem Atom die Musterdefinition be-ginnen soll. Beide Problematiken lassen sich mit einer Abwandlung des Algorithmus von Morgan adressieren (vgl. [Koh07]). Morgans Algorithmus bestimmt die kanoni-sche11 Nummerierung der Atome eines molekularen Graphen, die als Grundlage für eine kanonische Darstellung des Graphen genutzt werden kann. Dazu wird zunächst jeder Knoten mit seiner Konnektivität bewertet. Anschließend wird die erweiterte Konnektivität ermittelt, indem die Grade der benachbarten Knoten miteinbezogen werden. Der Algorithmus iteriert über den Graphen, bis sich die Anzahl der unter-schiedlichen Grad-Klassen nicht mehr verändert. Anschließend erfolgt eine eindeuti-ge Nummerierung, indem beim Knoten mit dem höchsten Gewicht begonnen wird und anschließend die Nachbarn in absteigender Reihenfolge mit Breitensuche mar-kiert werden. Bei Mehrdeutigkeit werden Atomtyp und Bindungsordnung miteinbe-zogen. Abbildung 4.6 verdeutlicht den Prozess zur Ermittlung der kanonischen Nummerierung anhand eines Beispiels. Verändert man den Algorithmus derart, dass für die Grundgewichtung der Atome der Atomtyp bereits miteinbezogen wird, sowie für die erweiterte Konnektivität die Bindungsordnung, so ergibt sich für die hetero-zyklischen Strukturen sowohl im Muster als auch im molekularen Graphen ein ein-deutiges Startatom. Mit Morgans Algorithmus lässt sich zudem eine Rangordnung der Kohlenstoffatome im molekularen Graphen berechnen, die sicherstellt, dass die zuerst besuchten Atome mögliche Startatome heterozyklischer Strukturen sind, womit auch die Rangordnung innerhalb der Kohlenstoff-Muster umgesetzt werden kann.

11 Kanonisch = eindeutig


32

Abbildung 4.6 Beispiel zur Ermittlung der kanonischen Nummerierung mit dem Algorithmus von Morgan (nach [Koh07], Foliensatz „2D Ähnlichkeit“, S.18ff)

4.2.3 Verwendeter Algorithmus

Zur Markierung der funktionellen Gruppen mit dem zuvor beschriebenen Verfahren, sind sowohl das Molekül als auch die Muster zunächst in eine geeignete Objektstruk-tur zu importieren. Da der molekulare Graph im CML-Format vorliegt und die Mus-terdefinitionen ebenfalls in einem CML-ähnlichen Format vorgenommen werden können, wird dazu ein SAX-Parser (Simple API for XML) verwendet. Dieser erzeugt bei der Initialisierung einen Musterverwaltungs-Container und lädt jedes Muster als Compound12 in dessen Verwaltungsstrukturen. Anschließend wird für das Molekül ein zweiter Parser verwendet, der dieses in die Objektstruktur unter Verwaltung der Klasse lädt, die im Folgenden den Markierungsprozess steuert. Abbildung 4.7 zeigt das UML-Klassendiagramm zur Modellierung der Molekülstrukturen. Ein Molekül besteht aus Atomen und Bindungen und kann darüber hinaus Compounds enthalten. Jeder Compound umfasst ein oder mehrere dieser Atome und Bindungen. Ein Atom kann mit mehreren Bindungen verknüpft sein, jede Bindung verbindet genau zwei Atome. Die auf diesen Strukturen arbeitenden Verwaltungsklassen werden in Abbil-dung 4.8 dargestellt. Der MoleculeAnnotator lädt zu Beginn das zu markierende Mo-lekül und initialisiert den PatternManager, der seinerseits die Musterdefinitionen in Form von Compound-Elementen unter seine Verwaltung stellt.

12 Der Begriff Compound wird im Folgenden stellvertretend für eine Gruppierung von Atomen und

Bindungen verwendet


33

Abbildung 4.7 Klassendiagramm der Molekülstruktur

Abbildung 4.8 Klassendiagramm der Verwaltungsstrukturen

In einem ersten Schritt wird der molekulare Graph mit der angepassten Variante von Morgans Algorithmus markiert, wodurch die Reihenfolge, in der die Atome als Startatome zu besuchen sind, festgelegt wird. Die Atomtypen werden in der Reihen-folge Schwefel, Phosphor, Stickstoff, Sauerstoff und schließlich Kohlenstoff besucht. Innerhalb jeder dieser Startatom-Gruppen ermittelt sich die Reihenfolge aufgrund der

Documents

Vergleich molekularer Graphen mithilfe des SiDiff ...pi.informatik.uni-siegen.de/Projekte/sidiff/papiere/Grassow2008DA.pdf · Universität Siegen Fachbereich 12 - Elektrotechnik und