Kapitelanfang Vorige Seite Nächste Seite Nächstes Kapitel
VERN Home navigation
 
Chemoinformatik
Einführung in die Chemoinformatik
Repräsentation chemischer Strukturen
Repräsentation chemischer Reaktionen
Datentypen/Datenformate
Datenbanken/Datenquellen
Suchmethoden
Einführung
bibliographische Suche
numerische Suche
Struktursuche
Substruktursuche
Substruktursuche
Möglichkeiten
Strukturerkennung
Graphentheorie
Komplexität
Atom by Atom Match
Brute Force Methode
  Backtracking Algorithmus
Beispiel
Oprimierung
Ähnlichkeitssuche
Markush-Formeln
Literatur
Deskriptoren für chemische Verbindungen
Methoden zur Datenanalyse
Anwendungen

Startseite

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.

Mapping

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.

Backtracking-Pfad

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
navigation BMBF-Leitprojekt Vernetztes Studium - Chemie