Proteinstrukturalignment - Berechnung von Alignments

Inhaltsverzeichnis

1 Einführung

2 DALI
2.1 Distanzmatrizen
2.2 Scorefunktion
2.3 Monte-Carlo-Optimierung
2.4 Anwendung bei DALI
2.4.1 Phase 1
2.4.2 Phase 2
2.4.3 Phase 3
2.5 Fehlerabschätzung

3 Proteinstrukturalignment durch inkrementelle kombinatorische Erweiterung des optimalen Pfades
3.1 Bestimmung der Seeds
3.2 Erweiterung des Alignments
3.3 Optimierung der Ergebnisse
3.4 Bewertung

4 Sekundärstrukturmatching
4.1 Graphentheoretischer Ansatz
4.2 Verbesserung des Alignments
4.3 Bewertung

5 Multiples Strukturalignment
5.1 Taylor, Flores, Orengo [14]
5.2 Haraldsson, Ohlsson [4]

6 Auswertung

1 Einführung

Proteine, das heißt Aminosäureketten, sind ein elementarer Grundbaustein aller Zellen. Sie haben im Körper verschiedenste Aufgaben und sind unter anderem in Form von Sturkturproteinen für den Aufbau von Gewebe, in Form von Enzymen für katalytische Funktionen, in Form von Hormonen für Steueraufgaben im Körper oder als Transportprotein wie zum Beispiel beim Hämoglobin für den Transport verschiedenster Substanzen im Körper zuständig.

Bei der Untersuchung von Proteinen unterscheidet man zwischen 3 Abstrak- tionsebenen: der Primärstruktur, der Sekundärstruktur sowie der Tertiärstruk- tur. Die Primärstruktur ist die einfachste Form, hier wird lediglich die Protein- sequenz betrachtet, die aus der DNA-Sequenz abgeleitet werden kann. Als Se- kundärstruktur bezeichnet man die Anordnung der Aminosäuren zu Sekundärstruk- turelementen wie der α-Helix oder dem β-Faltblat. Sie gibt Aufschluss über die die chemische Zusammensetzung eines Proteins, ignoriert allerdings die An- ordnung der Aminosäuren im Raum. Als Tertiärstruktur bezeichnet man die räumliche Anordnung, sie gibt also Aufschluss über die tatsächliche Gestalt des Proteins, ist aber naturgemäß auch die komplexeste Darstellungsform. Gele- gentlich ist zusätzlich noch von der Quartärstruktur die Rede, dabei betrachtet man Proteinkomplexe, die aus mehreren Proteinen zusammengesetzt sind. Die- se werden hier aber nicht weiter behandelt. Abbildung 1 zeigt beispielhaft zwei Tertiärstrukturen in einer 3D-Ansicht.

Abbildung 1: Das Enzym Alkoholdehydrogenase bei einem Menschen (links) und einem Pferd (rechts)

Abbildung in dieser Leseprobe nicht enthalten

Um die Funktionsweise von Proteinen zu untersuchen ist es oft hilfreich, Ge- meinsamkeiten zwischen Proteinen herauszufinden. Nun gibt es zwar eine Viel- zahl von effizienten Algorithmen, um Primärstrukturen zu vergleichen, unter anderem BLAST[8]sowie verschiedene Weiterentwicklungen (PSI-BLAST und Gapped BLAST[2], BLAST 2[8]u.a.), allerdings stellte sich heraus, daß die Ter- tiärstruktur einen weitaus größeren Einfluß auf die Funktion des Proteins hat als die Primärstruktur. Zudem haben Proteine mit ähnlicher Primärstruktur auch ähnliche Tertiärstrukturen, allerdings gilt der Umkehrschluss nicht zwangsläufig, so daß ein Tertiärstrukturvergleich auch Ähnlichkeiten finden kann, die aus der Primärstruktur nicht sofort ersichtlich sind. Abbildung 2 zeigt beispielhaft ein vollständiges Alignment zweier Proteine.

Ziel ist es daher Algorithmen zu finden, die zwei oder mehr Tertiärstrukturen verarbeiten und gemeinsame Teilstrukturen erkennen können. Ich werde im fol- genden fünf Algorithmen vorstellen, die dazu verschiedene Strategien verfolgen.

Die Beschreibungen der Algorithmen erheben keinen Anspruch auf Vollständig- keit, sondern sollen lediglich einen Überblick über die Funktionsweise und der Effizienz der verschiedenen Algorithmen geben. Für eine ausführliche Beschrei- bung mit sämtlichen Details sei der interessierte Leser auf die jeweiligen Papers verwiesen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Ein Alignment zwischen zwei Immunoglobulinen[1]

2 DALI

2.1 Distanzmatrizen

DALI[5]ist ein Akronym für Distance matrix ALIgnment. Wie der Name bereits andeutet, basiert der Algorithmus auf dem Vergleich von Distanzmatrizen.

Definition 1 Sei P ein Protein, bestehend aus n Aminosäuren mit den Koordinaten [Abbildung in dieser Leseprobe nicht enthalten] Dann ist D die Distanzmatrix von P , wenn [Abbildung in dieser Leseprobe nicht enthalten] und[Abbildung in dieser Leseprobe nicht enthalten] gilt.

Wir betrachten nur eine Koordinate pro Aminosäure, da bei sämtlichen Algorithmen lediglich die Cα-Atome betrachtet werden. Das sind die Kohlenstoffatome, die das Rückgrat der Aminosäurekette bilden. Eventuelle Nebenäste der Kette können für gewöhnlich ignoriert werden, da sie nur minimalen Einfluss auf die Funktion des Proteins haben.

Die Vorteile bei der Verwendung von Distanzmatrizen liegen auf der Hand. Sie verlegen das Problem auf elegante Weise aus dem dreidimensionalen in den zweidimensionalen Raum, sie erledigen automatisch das Problem, die Struktu- ren gegeneinander rotieren oder verschieben zu müssen, da sie nur mit relativen Koordinaten arbeiten, enthalten aber trotzdem genügend Informationen, um die dreidimensionale Struktur wieder zu berechnen. Allerdings enthalten sie mehr Informationen als nötig, so daß bei einem Vergleich zweier vollständiger Matri- zen viele unnötige Operationen durchgeführt werden würden.

Zu Beginn des Algorithmus wird für beide zu vergleichende Proteine jeweils die Distanzmatrix berechnet.

2.2 Scorefunktion

Um die Güte eines gefundenen Alignments zu bewerten, wird eine Scorefunktion benötigt. Diese ist wie folgt definiert:

Abbildung in dieser Leseprobe nicht enthalten

Dabei bezeichnet L die Länge des zu untersuchenden Alignments und φ ist eine Ähnlichkeitsfunktion, die folgendermaßen berechnet wird:

Abbildung in dieser Leseprobe nicht enthalten

Hierbei bezeichnet θE die maximale zu tolerierende Abweichung, in unserem Fall 0.2, also 20%, dAij beziehungsweisedij dieDistanzenzwischendemi-ten und dem j-ten Cα-Atom in den Proteinen A und B und d∗ij bezeichnetden Durchschnitt zwischen dAij sowied j.wwirddurchw[Abbildung in dieser Leseprobe nicht enthalten] ) definiert.

Die Funktion [Abbildung in dieser Leseprobe nicht enthalten wird als elastische Scorefunktion bezeichnet, da sie näher beeinander liegende Aminosäuren im Alignment höher gewichtet als wei- ter entfernt liegende. Außerdem betrachtet sie Abweichungen immer relativ, da eine kleine Abweichung von einem großen Wert natürlich weniger relevant ist als die selbe Abweichung von einem kleineren Wert. Offensichtlich führen Ver- gleiche eines Cα-Atoms mit sich selbst zu einem maximalen Wert, während alle anderen Paare Werte unterhalb des Maximalwerts erhalten, abhängig von der Differenz zwischen den Distanzen relativ zur Durchschnittsdistanz. Die Funktion w dient dazu, Paare, die sehr weit auseinanderliegen, weniger stark zu gewich- ten. Dadurch erhalten lokale Alignments einen deutlich höheren Stellenwert im Gesamtscore als das globale Alignment.

2.3 Monte-Carlo-Optimierung

Die Monte-Carlo-Optimierung ist eine bekannte und verbreitete Methode, um die Komplexität von Berechnungen auf Kosten der Genauigkeit zu reduzieren. Das Verfahren wurde nach gleichnamigen Stadtteil von Monaco benannt, der für seine Casinos bekannt ist. Der Name rührt daher, daß es sich hierbei um einen zufälligen Algorithmus handelt.

Das Verfahren kann für Maximierungsprobleme verwendet werden, bei denen die Lösung aus mehreren Teilstücken zusammengesetzt wird. Den Suchraum solcher Probleme kann man sich als Baum vorstellen. Dabei beschreibt jeder Knoten eine Kombination von Teillösungen und jede Kante das Aufnehmen eines weiteren Teilstücks in die Teillösung [Abb. 1].

Die Monte-Carlo-Optimierung schlägt dabei folgenden Weg vor, das nächste Teilstück auszuwählen. Zuerst wird der Zwischenscore für jede mögliche Erweiterung der jetzigen Lösung berechnet. Danach wird jedem Score eine Wahrscheinlichkeit zugeordnet, und zwar entsprechend der Formel

Abbildung in dieser Leseprobe nicht enthalten

Dabei steht S′ für den neuen Score, S für den bisherigen Score und β ist ein Parameter, der sich im Laufe des Algorithmus ändern kann. Bei physikalischen Berechnungen wird beispielsweise häufig die Temperatur für β verwendet.

Dieses Vorgehen stellt natürlich keineswegs sicher, daß der optimale Pfad gefunden wird. Im schlimmsten Fall kann sogar das Ergebnis mit dem schlechtesten Score herauskommen.

Um dennoch verwertbare Ergebnisse zu bekommen, wendet man das Verfahren häufig mehrfach an und wählt das Ergebnis mit dem besten Score aus. Je nach konkreter Anwendung der Optimierung können dabei beachtlich gute Ergebnisse berechnet werden, die aber dennoch von der Qualität nach unten nicht abgeschätzt werden können.

2.4 Anwendung bei DALI

In unserem konkreten Problemfall betrachten wir das Hinzufügen oder Entfer- nen von Tetrapeptiden¹als Schritt in der Monte-Carlo-Optimierung. DALI arbeitet in zwei Modi: Dem Erweiterungs- und dem Reduktionsmodus. Im Erweiterungsmodus wird zu einem gegebenen Alignment jedes Tetrapeptid betrachtet, mit dem das Alignment erweitert werden könnte. Für jede mögliche Erweiterung wird dann der Score berechnet und entsprechend dem Monte-Carlo- Verfahren eine Erweiterung ausgewählt. Im Reduktionsmodus werden Tetrapep- tidabschnitte aus dem Alignment entfernt, die insgesamt einen negativen Wert zum Score beitragen. Tetrapeptide, die einmal entfernt wurden, werden markiert und danach nicht mehr in das Alignment aufgenommen, um Endlosschleifen zu vermeiden.

Unabhängig davon werden in jedem Schritt des Algorithmus Tetrapeptide entfernt, die redundant sind, das heißt Tetrapeptide, die vollständig von zwei oder mehreren anderen Tetrapeptiden überlappt werden.

2.4.1 Phase 1

Am Anfang des Algorithmus werden Paare von Hexapeptiden²gesucht, bei de- nen die zugehörigen Abschnitte der Distanzmatrizen einen hinreichend kleinen Unterschied aufweisen. Von diesen Paaren werden 100 Stück, die sogenannten Seeds, ausgewählt.

Alle Seeds werden gleichzeitig betrachtet. In jedem Durchlauf des Algorith- mus werden dabei je fünf Erweiterungs- und ein Reduktionszyklus durchgeführt. Der Parameter β wird dabei in den ersten Runden auf 50 gesetzt, um die Ali- gnments schnell wachsen zu lassen. Sollten dabei 2 Alignments entstehen, die mehr als 50% Überlappung aufweisen, so werden diese zu einem zusammenge- fasst.

Nach einigen Runden wird β geändert, und zwar auf

Abbildung in dieser Leseprobe nicht enthalten

Dabei steht [Abbildung in dieser Leseprobe nicht enthalten] für den maximalen bisher gefundenen Score.

[...]

¹Tetrapeptide sind eine Verbindung von vier Aminosäuren zu einer Kette

²Analog zu Tetrapeptiden sind Hexapeptide Ketten von sechs Aminosäuren