Optimierung des Backtracking Algorithmus

Zur Verkürzung der Rechenzeiten gibt es unterschiedliche Ansätze, Substruktursuchen nach einem Backtracking Algorithmus zu optimieren.

1. Verbesserung der Hard- und Software
Neben schnelleren Computersystemen kann eine Beschleunigung auch durch Verwendung paralleler Rechner-Architekturen erreicht werden.

2. Anwendung von heuristischen Methoden
Dabei werden vor allem lokale Eigenschaften der Atome berücksichtigt. (Atomtyp, Anzahl der Bindungen, Bindungsordnung, Ringgröße) H-Atome können (zunächst) unterdrückt werden; die Suche kann an Atomen möglichst niedriger Konnektivität begonnen werden.

3. Preprocessing
Die Strukturen in der Datenbank werden vorab unabhängig von Suchanfragen auf mögliche Substrukturen (Schlüssel) überprüft. Als Ergebnis wird ein Bit-String konstruiert, wobei jedes Bit die An- oder Abwesenheit des jeweiligen Schlüssels (also einer definierten Substruktur) repräsentiert. Bei der Substruktursuche kann dann bereits durch Abgleich mit den Schlüsseln (Screening) ein Großteil der Strukturen eliminiert werden.

4. Partitionierung
Die Atome werden nach Element und Konnektivität in Klassen eingeteilt. (Sussenguth, 1965) Ist die entsprechende Klasse in der Struktur nicht vorhanden, bleibt sie auch bei der Suche unberücksichtigt.

zum Beispiel:

Klassenbeschreibung	Atome von GQ	Atome von GT
C-Atom mit 1 Einfach-Bindung (Klasse I)	1, 2	2, 5
C-Atom mit 2 Einfach-Bindungen (Klasse II)		4
C-Atom mit 3 Einfach-Bindungen (Klasse III)	3	3
O-Atom mit 1 Einfach-Bindung (Klasse IV)	4	1

Nur wenn alle definierten Klassen der Suchanfrage (von G_Q) auch im Zielmolekül (G_T) vorhanden sind, ist ein Isomorphismus möglich. Im Beispiel werden von Anfragemolekül 3 Klassen (1,3,4) und vom Zielmolekül alle 4 Klassen belegt, d.h. es ist prinzipiell Isomorphismus möglich.
Durch mehrmalige Partitionierung und Relaxation (Berücksichtigung der Nachbarn) kann die Laufzeit auf polynomiale Ordnung reduziert werden.

© Prof. Dr. J. Gasteiger, Dr. A. Schunk, Dr. Th. Engel, CCC Univ. Erlangen, Wed Jun 9 13:49:45 2004 GMT
 BMBF-Leitprojekt Vernetztes Studium - Chemie