Docking von starren und flexiblen Proteinen

Seminar Bioinformatik, „Theoretical Analysis of Protein-Protein Interactions”

Präsentation von Andreas Schlicker (andreasschlicker@web.de)

2

ÜbersichtÜbersicht

Molecular surface recognition:Molecular surface recognition: Docking von starren Proteinen und Docking von starren Proteinen und

Liganden mit Hilfe von Korrelation Liganden mit Hilfe von Korrelation geometrischer Eigenschaftengeometrischer Eigenschaften

Dead-End Elimination theorem (DEE):Dead-End Elimination theorem (DEE): Reduktion des Konformations-Suchraums Reduktion des Konformations-Suchraums

bei flexiblem Dockingbei flexiblem Docking Protein Docking mit flexiblen Protein Docking mit flexiblen

SeitenkettenSeitenketten

3

Molecular surface Molecular surface recognitionrecognition Docking von Molekülen anhand Docking von Molekülen anhand

geometrischer Eigenschaftengeometrischer Eigenschaften Form von Interfaces im gebundenen Form von Interfaces im gebundenen

und freien Zustand häufig sehr ähnlichund freien Zustand häufig sehr ähnlich

Suche im 6-dimensionalen Rotations- Suche im 6-dimensionalen Rotations- und Translationsraumund Translationsraum

4

Repräsentation der Repräsentation der MoleküleMoleküle

Projektion der Projektion der 3D-Koordinaten 3D-Koordinaten auf ein Gitterauf ein Gitter Gitterpunkt Gitterpunkt

innerhalb des innerhalb des Moleküls, wenn Moleküls, wenn Atomkern Atomkern innerhalb Radius innerhalb Radius r vorhandenr vorhanden

[1]

[1]

5

Matching von Matching von Oberflächen (I)Oberflächen (I) Korrelation der geometrischen FormKorrelation der geometrischen Form

((αα, , ββ, , γγ) gibt die Verschiebung von ) gibt die Verschiebung von Molekül b in Bezug auf Molekül a anMolekül b in Bezug auf Molekül a an

[1]

Kein Kontakt Kein Kontakt Korrelation = 0 Korrelation = 0Kontakt Kontakt Korrelation > 0 Korrelation > 0

je besser der Kontakt, desto größer je besser der Kontakt, desto größer die Korrelationdie Korrelation

6

Matching von Matching von Oberflächen (II)Oberflächen (II)

Problem: auch Überlappung liefert Problem: auch Überlappung liefert positive Korrelationpositive Korrelation

Lösung: Lösung: ρρ in Gleichung [2a] << 0 in Gleichung [2a] << 0 δδ in Gleichung [2b] > 0 in Gleichung [2b] > 0

Überlappung wird mit Überlappung wird mit

negativer Korrelation bestraftnegativer Korrelation bestraft

[1]

7

Berechnung (I)Berechnung (I)

Direkte Berechnung der Korrelation Direkte Berechnung der Korrelation benötigt Zeit O(Nbenötigt Zeit O(N66)) Verwende Fourier Transformation Verwende Fourier Transformation

Korrelation wird durch Inverse Fourier-Transformation erhaltenKorrelation wird durch Inverse Fourier-Transformation erhalten

[1]

Benötigte Zeit liegt in Benötigte Zeit liegt in O(N³ln(N³))O(N³ln(N³))

8

Berechnung (II)Berechnung (II)

Molekül a wird fixiert, Molekül b wird Molekül a wird fixiert, Molekül b wird in allen Orientierungen getestetin allen Orientierungen getestet

[1]

9

ResultateResultate

Test mit 5 Komplexen, zwei Test mit 5 Komplexen, zwei Durchgänge mit unterschiedlichen Durchgänge mit unterschiedlichen Gitter-GrößenGitter-Größen

[1]

[1]

[1]

10

Vor- und NachteileVor- und Nachteile

Vorteile:Vorteile: Schnelle BerechnungSchnelle Berechnung Meistens korrekte VorhersageMeistens korrekte Vorhersage Parameter sind universell einsetzbarParameter sind universell einsetzbar

Nachteile:Nachteile: Starre MoleküleStarre Moleküle Keine Berücksichtigung physiko-Keine Berücksichtigung physiko-

chemischer Eigenschaftenchemischer Eigenschaften

11

Dead-End Elimination Dead-End Elimination TheoremTheorem Konformationsraum von Proteinen Konformationsraum von Proteinen

sehr groß, selbst bei Verwendung sehr groß, selbst bei Verwendung von Rotamer-Bibliothekenvon Rotamer-Bibliotheken

Systematische Suche nach der Systematische Suche nach der „global minimum energy „global minimum energy conformation“ (GMEC) praktisch conformation“ (GMEC) praktisch unmöglichunmöglich

12

Energie einer Energie einer KonformationKonformation

Potentielle Energie eines Proteins:Potentielle Energie eines Proteins:

[2]

13

„„Dead-Ending“ RotamereDead-Ending“ Rotamere

Rotamere, die in der GMEC nicht Rotamere, die in der GMEC nicht vorkommen könnenvorkommen können

Rotamer iRotamer irr kann nicht vorkommen, kann nicht vorkommen, wenn für ein Paar (iwenn für ein Paar (irr, i, itt) gilt:) gilt:

[2]

14

Erweiterung auf Erweiterung auf RotamerpaareRotamerpaare Energie eines Rotamerpaares [iEnergie eines Rotamerpaares [irrjjss]]

Interaktionsenergie mit anderen RotamerenInteraktionsenergie mit anderen Rotameren

Rotamerpaar [iRotamerpaar [irrjjss] ist „dead-ending“, wenn gilt:] ist „dead-ending“, wenn gilt:

[2]

[2]

[2]

15

AlgorithmusAlgorithmus Eliminiere alle Rotamere, die Eliminiere alle Rotamere, die

offensichtlich inkompatibel sindoffensichtlich inkompatibel sind Eliminiere „dead-ending“ Rotamere Eliminiere „dead-ending“ Rotamere

mit dem DEE Theoremmit dem DEE Theorem Wende DEE Theorem auf alle Wende DEE Theorem auf alle

Rotamerpaare an und markiere Rotamerpaare an und markiere „dead-ending“ Paare„dead-ending“ Paare

Iteriere, bis keine weiteren Rotamere Iteriere, bis keine weiteren Rotamere mehr entfallenmehr entfallen

16

Resultate (I)Resultate (I) Test mit dem Insulin-DimerTest mit dem Insulin-Dimer

anfängliche Kombinationsmöglichkeiten: anfängliche Kombinationsmöglichkeiten: 2,7*102,7*107676

Nach 9 Iterationen: 7200 Nach 9 Iterationen: 7200 Modellierung des Modellierung des

Proteins liefert 55 Proteins liefert 55 richtig richtig vorhergesagte vorhergesagte ResiduenResiduen Verborgene Verborgene

Residuen werden Residuen werden mit 93% Genauigkeit mit 93% Genauigkeit vorhergesagtvorhergesagt

[2]

17

Resultate (II)Resultate (II)

Blind-Test an Limulus polyphemus Blind-Test an Limulus polyphemus 194 Aminosäuren, wovon 71 % richtig 194 Aminosäuren, wovon 71 % richtig

vorhergesagt wurdenvorhergesagt wurden Viele Fehler durch falsche Salz- und Viele Fehler durch falsche Salz- und

Wasserstoffbrücken an exponierten Wasserstoffbrücken an exponierten GruppenGruppen

18

Vor- und NachteileVor- und Nachteile

Vorteile:Vorteile: Schnelle Berechnung (Aufwand steigt „nur“ Schnelle Berechnung (Aufwand steigt „nur“

quadratisch mit Anzahl der Aminosäuren)quadratisch mit Anzahl der Aminosäuren) Starke Reduzierung des SuchraumsStarke Reduzierung des Suchraums

Nachteile:Nachteile: Ungenauigkeiten durch verwendete Ungenauigkeiten durch verwendete

EnergiefunktionEnergiefunktion Benötigt relativ genaues TemplateBenötigt relativ genaues Template Abhängig von der verwendeten Rotamer-Abhängig von der verwendeten Rotamer-

BibliothekBibliothek

19

Protein Docking mit Protein Docking mit flexiblen Seitenkettenflexiblen Seitenketten

Docking von rigiden Strukturen keine Docking von rigiden Strukturen keine gute Lösunggute Lösung

Problem des exponentiellen Problem des exponentiellen Wachstums des Konformationsraums Wachstums des Konformationsraums bei flexiblen Seitenkettenbei flexiblen Seitenketten

20

FlexibilitätFlexibilität

Alle Residuen flexibel behandeln sehr Alle Residuen flexibel behandeln sehr aufwändig selbst bei Verwendung aufwändig selbst bei Verwendung von Rotamer-Bibliothekenvon Rotamer-Bibliotheken Nur Interface-Residuen flexibelNur Interface-Residuen flexibel

Interface benötigtInterface benötigt

Rigides Docking zur Erzeugung von Rigides Docking zur Erzeugung von AnfangsstrukturenAnfangsstrukturen

21

Rigides DockingRigides Docking

Verwendet geometrische und einfache Verwendet geometrische und einfache chemische Fitness Funktionenchemische Fitness Funktionen

Von den erzeugten Komplexstrukturen Von den erzeugten Komplexstrukturen wurden die 60 besten weiter verfolgtwurden die 60 besten weiter verfolgt Oft große Überlappung der Proteine und Oft große Überlappung der Proteine und

inkorrekt platzierte Seitenketteninkorrekt platzierte Seitenketten

22

Bestimmung der Bestimmung der BindungsstelleBindungsstelle Residuen, die innerhalb 6 Å eines Residuen, die innerhalb 6 Å eines

Atoms des anderen Proteins liegen Atoms des anderen Proteins liegen

Seitenketten ohne Rotamere (CYS in Seitenketten ohne Rotamere (CYS in Disulfidbrücken, ALA, GLY) werden Disulfidbrücken, ALA, GLY) werden nicht berücksichtigtnicht berücksichtigt

23

GMECGMEC

GMEC = Kombination der Rotamere, GMEC = Kombination der Rotamere, die die niedrigste Energie lieferndie die niedrigste Energie liefern

Anwendung des DEE-Theorems Anwendung des DEE-Theorems möglichmöglich

[3]

24

Suche nach der GMECSuche nach der GMEC

Zwei Strategien:Zwei Strategien: Multi-Greedy MethodeMulti-Greedy Methode Branch-and-cut basierend auf einem ILPBranch-and-cut basierend auf einem ILP

25

Multi-Greedy Methode Multi-Greedy Methode (I)(I) Aufbau eines Enumerations-Baumes Aufbau eines Enumerations-Baumes

mit möglichen Kombinationenmit möglichen Kombinationen

[3]

26

Integer Linear Program Integer Linear Program (ILP)(ILP) Formulierung als Minimierungs-Problem Formulierung als Minimierungs-Problem

auf einem ungerichteten Graphenauf einem ungerichteten Graphen Knoten v für alle Rotamere, E(v) = EKnoten v für alle Rotamere, E(v) = Etpltpl

ir ir - E- Emaxmax

Kanten uv für Rotamer-Paare verschiedener Residuen, Kanten uv für Rotamer-Paare verschiedener Residuen,

E(uv) = EE(uv) = Epwpwir,js ir,js - E- Emaxmax

k-partiter Graph mit negativen Kanten- und k-partiter Graph mit negativen Kanten- und Knoten-GewichtenKnoten-Gewichten

GMEC entspricht Rotamer-Graph mit GMEC entspricht Rotamer-Graph mit minimalem Gewichtminimalem Gewicht

27

ILP (II)ILP (II)

[3]

[3]

28

Branch-and-cut Branch-and-cut

Lösen der Relaxation des ILPsLösen der Relaxation des ILPs Falls Lösung ā nicht optimal, suche Falls Lösung ā nicht optimal, suche

nach nach

fa <= ffa <= f00, die , die ā alsā als mögliche Lösung mögliche Lösung ausschließtausschließt

Falls keine Ungleichung gefunden Falls keine Ungleichung gefunden wird, aufsplitten in zwei wird, aufsplitten in zwei Unterprobleme Unterprobleme

29

EnergieberechnungEnergieberechnung

Optimierung der GMEC mit AMBEROptimierung der GMEC mit AMBER Freie Bindungsenergie:Freie Bindungsenergie:

[3]

ΔΔGGESES: elektrostatischer Beitrag: elektrostatischer Beitrag ΔΔGGcavcav: freie Cavitäts-Energie in Wasser: freie Cavitäts-Energie in Wasser ΔΔGGconfconf: Änderung der Entropie: Änderung der Entropie ΔΔGGvdWvdW: Änderung der freien van-der-Waals : Änderung der freien van-der-Waals

EnergieEnergie

30

Algorithmus (I)Algorithmus (I)

Generierung von Ausgangsstrukturen Generierung von Ausgangsstrukturen mit Hilfe von rigidem Docking mit Hilfe von rigidem Docking

Bestimmung der Aminosäuren am Bestimmung der Aminosäuren am InterfaceInterface Variation dieser Aminosäuren durch Variation dieser Aminosäuren durch

RotamereRotamere Iterative Anwendung des DEE Iterative Anwendung des DEE

Theorems zur Reduktion des Theorems zur Reduktion des KonformationsraumesKonformationsraumes

31

Algorithmus (II)Algorithmus (II)

Finden der GMEC mit Hilfe der Finden der GMEC mit Hilfe der schnellen Heuristic bzw. des exakten schnellen Heuristic bzw. des exakten branch-and-cut Algorithmusbranch-and-cut Algorithmus

Optimierung der Molekülgeometrien Optimierung der Molekülgeometrien mit Hilfe eines Molekülmechanik mit Hilfe eines Molekülmechanik KraftfeldesKraftfeldes

Berechnung der freien Berechnung der freien BindungsenergieBindungsenergie

32

Resultate (I)Resultate (I)

Test mit drei Protein Komplexen Test mit drei Protein Komplexen Anwendung des DEE ergibt große Anwendung des DEE ergibt große

VereinfachungVereinfachung

[3]

33

Resultate (II)Resultate (II)

[3]

34

Resultate (III)Resultate (III)

[3]

35

Resultate (IV)Resultate (IV)

[3]

36

Vor- und NachteileVor- und Nachteile

Vorteile:Vorteile: Heuristik liefert schnell gute Annäherung Heuristik liefert schnell gute Annäherung

an optimale Lösungan optimale Lösung Branch-and-cut liefert optimale RotamereBranch-and-cut liefert optimale Rotamere

Nachteile:Nachteile: Keine perfekte Trennung von guten und Keine perfekte Trennung von guten und

schlechten Ergebnissenschlechten Ergebnissen Ergebnisse stark von der Wahl des Ergebnisse stark von der Wahl des

Kraftfeldes abhängigKraftfeldes abhängig

37

ZusammenfassungZusammenfassung

Rigides Docking nur erfolgreich, Rigides Docking nur erfolgreich, wenn native und Komplexstruktur wenn native und Komplexstruktur sehr ähnlich sindsehr ähnlich sind

Rigides Docking aber guter Rigides Docking aber guter Startpunkt für flexibles DockingStartpunkt für flexibles Docking

Dead-End elimination starke Dead-End elimination starke Vereinfachung bei flexiblem DockingVereinfachung bei flexiblem Docking

38

ReferenzenReferenzen

[1][1] Katchalski-Katzir, E., Shariv, I., et al., (1992) PNAS, 89, 2195-

2199. Molecular Surface Recognition: Determination of Geometric Fit between Proteins and their Ligands by Correlation Techniques

[2] Desmet, J., De Maeyer, M., Hazes, B., and Lasters, I., (1992) Nature, 356, 539-542. DEE Theorem and its Use in Protein DEE Theorem and its Use in Protein Side Chain Positioning Side Chain Positioning

[3] Althaus, E., Kohlbacher, O., Lenhof, H.-P., and Muller, P., [3] Althaus, E., Kohlbacher, O., Lenhof, H.-P., and Muller, P., (2002) J. Comput. Biol., 9, 597-612. A Combinatorial Approach (2002) J. Comput. Biol., 9, 597-612. A Combinatorial Approach to Protein Docking with Flexible Side Chainsto Protein Docking with Flexible Side Chains