Proteinstrukturalignment - Berechnung von Alignments

1 Einf¨ uhrung

Proteine, das heißt Aminos¨ aureketten, sind ein elementarer Grundbaustein aller Zellen. Sie haben im K¨ orper verschiedenste Aufgaben und sind unter anderem in Form von Sturkturproteinen f¨ ur den Aufbau von Gewebe, in Form von Enzymen f¨ ur katalytische Funktionen, in Form von Hormonen f¨ ur Steueraufgaben im K¨ orper oder als Transportprotein wie zum Beispiel beim H¨ amoglobin f¨ ur den Transport verschiedenster Substanzen im K¨ orper zust¨ andig. Bei der Untersuchung von Proteinen unterscheidet man zwischen 3 Abstraktionsebenen: der Prim¨ arstruktur, der Sekund¨ arstruktur sowie der Terti¨ arstruktur. Die Prim¨ arstruktur ist die einfachste Form, hier wird lediglich die Proteinsequenz betrachtet, die aus der DNA-Sequenz abgeleitet werden kann. Als Se-kund¨ arstruktur bezeichnet man die Anordnung der Aminos¨ auren zu Sekund¨ arstrukturelementen wie der α-Helix oder dem β-Faltblat. Sie gibt Aufschluss ¨ uber

die die chemische Zusammensetzung eines Proteins, ignoriert allerdings die An-ordnung der Aminos¨ auren im Raum. Als Terti¨ arstruktur bezeichnet man die r¨ aumliche Anordnung, sie gibt also Aufschluss ¨ uber die tats¨ achliche Gestalt des

Proteins, ist aber naturgem¨ aß auch die komplexeste Darstellungsform. Gelegentlich ist zus¨ atzlich noch von der Quart¨ arstruktur die Rede, dabei betrachtet man Proteinkomplexe, die aus mehreren Proteinen zusammengesetzt sind. Diese werden hier aber nicht weiter behandelt. Abbildung 1 zeigt beispielhaft zwei Terti¨ arstrukturen in einer 3D-Ansicht.

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

Um die Funktionsweise von Proteinen zu untersuchen ist es oft hilfreich, Gemeinsamkeiten zwischen Proteinen herauszufinden. Nun gibt es zwar eine Vielzahl von effizienten Algorithmen, um Prim¨ arstrukturen 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 Terti¨ arstruktur einen weitaus gr¨ oßeren Einfluß auf die Funktion des Proteins hat als die Prim¨ arstruktur. Zudem haben Proteine mit ¨ ahnlicher Prim¨ arstruktur auch ¨ ahnliche Terti¨ arstrukturen, allerdings gilt der Umkehrschluss nicht zwangsl¨ aufig, so daß ein Terti¨ arstrukturvergleich auch ¨ Ahnlichkeiten finden kann, die aus der

Prim¨ arstruktur nicht sofort ersichtlich sind. Abbildung 2 zeigt beispielhaft ein vollst¨ andiges Alignment zweier Proteine.

Ziel ist es daher Algorithmen zu finden, die zwei oder mehr Terti¨ arstrukturen verarbeiten und gemeinsame Teilstrukturen erkennen k¨ onnen. Ich werde im folgenden f¨ unf Algorithmen vorstellen, die dazu verschiedene Strategien verfolgen.

2

Die Beschreibungen der Algorithmen erheben keinen Anspruch auf Vollst¨ andigkeit, sondern sollen lediglich einen ¨ Uberblick ¨ uber die Funktionsweise und der

Effizienz der verschiedenen Algorithmen geben. F¨ ur eine ausf¨ uhrliche Beschreibung mit s¨ amtlichen Details sei der interessierte Leser auf die jeweiligen Papers verwiesen.

Abbildung 2: Ein Alignment zwischen zwei Immunoglobulinen[1]

2 DALI

2.1 Distanzmatrizen

DALI[5] ist ein Akronym f¨ ur 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¨ auren mit den Koordinaten (a 1 , · · · , a n ). Dann ist D die Distanzmatrix von P , wenn D ∈ N ^nxn und d ij = |a i − a j | gilt.

Wir betrachten nur eine Koordinate pro Aminos¨ aure, da bei s¨ amtlichen Al-gorithmen lediglich die C ^α -Atome betrachtet werden. Das sind die Kohlenstoffatome, die das R¨ uckgrat der Aminos¨ aurekette bilden. Eventuelle Neben¨ aste der Kette k¨ onnen f¨ ur gew¨ ohnlich 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 Strukturen gegeneinander rotieren oder verschieben zu m¨ ussen, da sie nur mit relativen Koordinaten arbeiten, enthalten aber trotzdem gen¨ ugend Informationen, um die dreidimensionale Struktur wieder zu berechnen. Allerdings enthalten sie mehr Informationen als n¨ otig, so daß bei einem Vergleich zweier vollst¨ andiger Matrizen viele unn¨ otige Operationen durchgef¨ uhrt werden w¨ urden. Zu Beginn des Algorithmus wird f¨ ur beide zu vergleichende Proteine jeweils die Distanzmatrix berechnet.

3

2.2 Scorefunktion

Um die G¨ ute eines gefundenen Alignments zu bewerten, wird eine Scorefunktion ben¨ otigt. Diese ist wie folgt definiert:

Dabei bezeichnet L die L¨ ange des zu untersuchenden Alignments und φ ist eine ¨ Ahnlichkeitsfunktion, die folgendermaßen berechnet wird:

Hierbei bezeichnet θ ^E die maximale zu tolerierende Abweichung, in unserem Fall 0.2, also 20%, d A ij beziehungsweise d B

und dem j-ten C ^α -Atom in den Proteinen A und B und d ^∗ ij . w wird durch w(r) = exp(− r ² Durchschnitt zwischen d A ij sowie d B α 2 ) definiert.

Die Funktion φ ^E (i, j) wird als elastische Scorefunktion bezeichnet, da sie n¨ aher beeinander liegende Aminos¨ auren im Alignment h¨ oher gewichtet als weiter entfernt liegende. Außerdem betrachtet sie Abweichungen immer relativ, da eine kleine Abweichung von einem großen Wert nat¨ urlich weniger relevant ist als die selbe Abweichung von einem kleineren Wert. Offensichtlich f¨ uhren Vergleiche eines C ^α -Atoms mit sich selbst zu einem maximalen Wert, w¨ ahrend alle anderen Paare Werte unterhalb des Maximalwerts erhalten, abh¨ angig von der Differenz zwischen den Distanzen relativ zur Durchschnittsdistanz. Die Funktion w dient dazu, Paare, die sehr weit auseinanderliegen, weniger stark zu gewichten. Dadurch erhalten lokale Alignments einen deutlich h¨ oheren 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¨ at von Berechnungen auf Kosten der Genauigkeit zu reduzieren. Das Verfahren wurde nach gleichnamigen Stadtteil von Monaco benannt, der f¨ ur seine Casinos bekannt ist. Der Name r¨ uhrt daher, daß es sich hierbei um einen zuf¨ alligen Algorithmus handelt.

Das Verfahren kann f¨ ur Maximierungsprobleme verwendet werden, bei denen die L¨ osung aus mehreren Teilst¨ ucken zusammengesetzt wird. Den Suchraum solcher Probleme kann man sich als Baum vorstellen. Dabei beschreibt jeder Knoten eine Kombination von Teill¨ osungen und jede Kante das Aufnehmen eines weiteren Teilst¨ ucks in die Teill¨ osung [Abb. 1]. Die Monte-Carlo-Optimierung schl¨ agt dabei folgenden Weg vor, das n¨ achste Teilst¨ uck auszuw¨ ahlen. Zuerst wird der Zwischenscore f¨ ur jede m¨ ogliche Erweiterung der jetzigen L¨ osung berechnet. Danach wird jedem Score eine Wahrscheinlichkeit zugeordnet, und zwar entsprechend der Formel