Substruktursuche: Backtracking Algorithmus
Bei diesem Algorithmus (von Ray & Kirsch, 1957) findet ebenfalls eine Atom-by-Atom Suche statt. Allerdings ist sie hierarchisch in einer baumartigen Struktur organisiert.
Um die Suche zu beschleunigen, wird die Suchtiefe reduziert, indem solche Zuordnungen zwischen Substruktur und untersuchter Struktur, die sinnlos sind (z.B. wegen Mißachtung der Konnektivität) abgebrochen werden. Im Beispiel ist eine Abbildung von C1 auf O1 nicht möglich, da es sich um verschiedene Elemente handelt. Der Algorithmus kehrt dann zum nächsthöheren Knoten des Baums zurück. Als Startpunkt wird nach Möglichkeit ein Atom mit wenigen Bindungen und/oder hoher Bindungsordnung gewählt (z.B. Carbonyl-O). Hier sind wenige Permutationen möglich bzw. sinnvoll und der Algorithmus kann dadurch schneller durchlaufen werden.
Im gezeigten Beispiel sind nur insgesamt 16 Zuordnungen (Mappings) zur vollständigen Überprüfung der Substruktur nötig - im Gegensatz zu 120 Möglichkeiten in der Brute Force Methode. Meistens wird ein Isomorphismus (also Übereinstimmung der Substrukturen) schon vor dem Durchlaufen aller Zuordnungen gefunden.
Durch diese Modifikation des Algorithmus liegt hier nur noch ein exponentieller Zusammenhang zwischen Laufzeit und Atomzahl vor. Dennoch ist der Rechenaufwand hoch.
Backtracking-Algorithmen sind das Kernstück jeder Substruktursuche.
© 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
|