Datenbankgestützte Substanzbeschaffung in der forschenden Chemieindustrie – ein algorithmischer Optimierungsansatz
Die Speicherung und Suche chemischer graphischer Datentypen wie Strukturen und
Reaktionen in relationalen Datenbanksystemen ist ein in Wissenschaft und Industrie
etabliertes Verfahren. Aufgrund der rechenintensiven Algorithmen zur Erkennung
von (Sub)Graphen-Isomorphismus benutzen solche Systeme in der Regel schnellere
Selektionsmechanismen, um die Menge potentieller Kandidaten bereits im Vorfeld
einzuschränken.
Dabei werden verbreitet Selektionsmechanismen eingesetzt, die auf numerischen und
binären Vektoren, Fingerprints genannt, basieren, mit einer klaren Dominanz binärer
Fingerprints aufgrund ihrer Geschwindigkeitsvorteile bei bitweisen Operationen und
der besseren Speichereffizienz. Die beiden am Häufigsten eingesetzten binären Finger-
prints sind einerseits Pfad-generiert, andererseits Wörterbuch-generiert, wobei beide
spezifische Schwächen, insbesondere blinde Stellen, aufweisen.
Um diese Schwächen zu überwinden, benutzt die Pgchem::Tigress Erweiterung
für das objektrelationale Datenbankmanagementsystem PostgreSQL einen hybri-
den binären Fingerprint, der aus einem invarianten Pfad-generierten Teil und einem
Substruktur-generierten Teil besteht, welcher extern durch ein Wörterbuch von Sub-
strukturmustern konfiguriert werden kann.
Diese Arbeit stellt einen neuartigen Ansatz vor, um für beliebige Strukturdaten mittels
dynamischer diskreter Optimierung die optimierte Konfiguration des Wörterbuchs für
den Substruktur-generierten Teils des Fingerprints zu finden.
Mittels des Einsatzes des in dieser Arbeit entwickelten Verfahrens kann die notwendige
Rechenleistung zum Betrieb eines chemischen Informationssystems um durchschnittlich
42 Prozent reduziert werden. Durch den so verbesserten Anfragedurchsatz lassen sich
der Umstieg auf die nächsthöhere verfügbare Leistungsstufe eines Servers vermeiden
und so signifikante Opportunitätserlöse bei den Betriebskosten realisieren.
The storage and retrieval of chemical graphical datatypes such as structures and
reactions in relational database systems is a common technique used in academia and
industry alike. Due to the computationally intensive algorithms used for (sub)graph-
isomorphism detection, such systems commonly use faster screening mechanisms in
order to reduce the set of potentional match positives before applying aforementioned
algorithms.
Widely used screening mechanisms are based on numerical and binary vectors, called
fingerprints, with a clear dominance of binary fingerprints due to the raw speed
advantage of bitwise operations and compactness in storage. The two most commonly
used types of binary fingerprints are path-generated and substructure-generated, both
of which have specific shortcomings, especially blind spots.
To overcome this shortcomings, the Pgchem::Tigress chemistry extension to the
PostgreSQL object-relational database management system uses a hybrid binary
fingerprint, consisting of an invariant path-generated part and an substructure-generated
part which is externally configurable through a dictionary of substructure patterns.
This thesis presents a novel approach of using dynamic discrete optimization to find an
optimized dictionary configuration for the substructure-generated part of the fingerprint
for arbitrary sets of structural data.
By means of applying the method developed in this thesis, the computational power
neccessary to run a chemical information system can be reduced by 42 percent on
average. By improving the query throughput, upgrading the server hardware to the
next level of computational power can be avoided and thus opportunity revenues of
the operating costs are realized.
Preview
Cite
Citation style:
Could not load citation form.