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: Brute Force Methode

Die Brute Force Methode ist ein Prozeß, um Strukturen zu finden, die eine bestimmte, gesuchte Teilstruktur enthalten. Dies wird über die Graphentheorie realisiert, es wird also überprüft, ob der Graph GQ (Q = Query, Anfrage) isomorph mit einem Subgraphen von GT (T = Target, Ziel) ist.

Mapping

Es ist dabei eine Zuordnung aller Knoten aus GQ mit allen Knoten aus QT nötig: (1,2,3,4), (1,2,3,5), ... (5,4,3,2)
Obwohl z.B. ein Mapping (1,2,3,5) unsinnig ist, da bei dieser Teilstruktur zu 5 gar keine Bindung vorliegt, werden beim Atom-by-Atom Match der Brute Force Methode alle Kombinationsmöglichkeiten durchlaufen. Dies führt wiederum zu der Formel:

Graphentheorie

und damit zu einem NP-Problem. Das oben angegebene Beispiel erfordert beim Vergleich von zwei relativ kleinen Molekülen 120 einzelne Zuordnungen (Mappings). Der Algorithmus muß also verbessert werden, indem die Mappings auf die Sinnvollen reduziert werden.


© 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