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 G_Q (Q = Query, Anfrage) isomorph mit einem Subgraphen von G_T (T = Target, Ziel) ist.

Es ist dabei eine Zuordnung aller Knoten aus G_Q mit allen Knoten aus Q_T 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:

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