Bio

02 Scoring von Alignments

  1. Einführung in die Bioinformatik
  2. Scoring von Alignments
  3. Der Needleman-Wunsch-Algorithmus

Prüfen auf Identität

Die einfachste Art, zwei Sequenzen miteinander zu vergleichen ist, zu prüfen, ob sie identisch sind. Dazu müssen jeweils die 0. Position der ersten Sequenz mit der 0. Position der zweiten, die 1. der ersten mit der 1. der zweiten und so weiter vergleichen werden:

Der folgende Code macht genau das gleiche, verwendet dabei jedoch statt einer for-Schleife eine while-Schleife:

while-Schleifen brauchen nicht nur mehr Zeilen, sondern sind auch gefährlicher, da man gerne mal das ‘i++;’ vergisst.

Das Ergebnis einer solchen Prüfung kann offensichtlich nur zwei Werte annehmen: true oder false.

Sowohl Mutationen, als auch Rasterverschiebungen führen bei dieser Methode zu einem ‘false‘:

APFELSAFT
APPELSAFT
oder
APFELSAFT
PFELSAFT

Im folgenden Kapitel betrachten wir zunächst der ersten Fall und bewerten ein Alignment unter Berücksichtigung von Mutationen.

Bewerten von Mutationen

Welches der folgenden zwei Alignments ist das wahrscheinlichere?

KIRSCHSAFT
PIRSCHSAFT
oder
KIRSCHSAFT
KIRSCHSAAT

Beide Alignments unterscheiden sich in genau einer Aminosäure. Um eine qualifizierte Aussage zu treffen, bei welchem es sich um das ‘bessere’ bzw. wahrscheinliche Alignment handelt, müssen wir den Austausch K<>P mit dem Austausch F<>A vergleichen.

Hierzu wird eine sogenannte ‘Substitution Matrix‘ verwendet. Dabei handelt es sich um eine Tabelle, in der Aminosäure-Paare (z.B. P-P, G-C, W-A..) eine Punktzahl (Score) zugewiesen wird. Paare gleicher Aminosäuren bekommen dabei eine positive Punktzahl, während eine Mutation in der Regel einen negativen Score bekommt. Es gibt verschiedene solcher Tabellen, die sich in ihrer Berechnung unterscheiden. Wir verwenden hier die BLOSUM50 Matrix. Berechnet wird der Score bei BLOSUM50 durch die Formel

Wobei p(ab) die Wahrscheinlichkeit für das Auftreten des Paares A-B in natürlichen Proteinsequenz-Alignments ist, während q(a) bzw. q(b) die Frequenz in zufälligen ist. Das Ergebnis wird zur nächsten Ganzzahl gerundet.

(source: http://www.ncbi.nlm.nih.gov/IEB/ToolBox/C_DOC/lxr/source/data/BLOSUM50)

Der Score einer Sequenz berechnet sich aus der Summe der Scores aller Paare. Die Paarung einer Aminosäure mit einer Lücke (gap) ist ebenfalls zulässig und wird immer mit dem selben Score, der sogenannten gap-penalty bewertet. In der abgebildeten Tabelle hat diese den Wert -5.

In unserem Beispiel oben unterschieden sich die ersten beiden Sequenzen im Paar K‑P, welches den Wert ‑1 hat, während sich die folgenden zwei Sequenzen im Paar A‑F mit dem Wert ‑3 unterschieden. Der Score für das erste Alignment summiert sich damit auf 62, während der des zweiten 58 beträgt. (Man beachte, dass die korrekte Paarung von K‑K 6 Punkte, während die von F‑F 8 Punkte bringt.)

Die Sequenzen KIRSCHSAFT und PIRSCHSAFT haben damit eine größere Ähnlichkeit, als KIRSCHSAFT und KIRSCHSAAT.

Bewerten von Alignments

Das vorherige Kapitel hat schon einiges vorausgegriffen, doch soll nun auch gezeigt werden, wie die Berechnung des Scores ‘in großem Stil’ durchgeführt wird.

Ähnlich wie beim direkten Vergleich zweier Sequenzen, werden die Sequenzen in einer for-Schleife gelesen. Die int-Variable ‘score’ wird verwendet, um den Punktestand zu messen. In jedem Schritt wird der Punktestand um den entsprechenden Wert erhöht. Dazu muss auf die SubstitutionMatrix zugegriffen werden.

Um mit der SubstitutionMatrix arbeiten zu können, benötigen wir den Objekttyp Dictionary<Key, Value>.

Ein Dictionary<Key, Value> ähnelt einem Nachschlagewerk, bei dem jedes Element (Value) mit einem anderen Objekt (Key) identifiziert wird. Nehmen wir an, dass das Dictionary<char, int> mit der Bezeichnung ‘buchstaben’ das folgende Key-Value-Pair enthält: ‘C’, 3

buchstaben[‘C’] liefert damit den int-Wert 3 zurück.

Bei der SubstitutionMatrix handelt es sich um ein Objekt des Typs Dictionary<char, Dictionary<char, int>>, also ein Dictionary<char, …>, welches als Value ein Dictionary<char, int> beinhaltet. Das äußere beinhaltet damit die Zeilen der SubstitutionMatrix (z.B. substimatrix[‘C’] ist die Zeile ‘C’), während das Innere die Einträge in der Zeile beinhaltet (z.B. substimatrix[‘C’][‘P’] ist der Score für ein C‑P-Paar – also ‑4).

Sowohl im folgenden Codebeispiel, als auch im herunterladbaren Beispielprojekt, wird die BLOSUM50-Substitutions Matrix mit ‘blosum50matrix’ bezeichnet. Wie dieses Objekt zustande kommt, kannst du dir im Code anschauen, ist hier aber nicht weiter von Bedeutung.

Wichtig ist, dass wir in Zeile 207 überprüfen, ob wir bereits am Ende einer der beiden Sequenzen angelangt sind, bzw. ob das Zeichen an der Position ‘-‘, also eine gap ist. In diesem Fall müssen wir die gap penalty verwenden. Andernfalls wird der score in Zeile 210 um den Wert des Paares erhöht, der in der BLOSUM50 nachgesehen wird.

Mit der oben beschriebenen Methode kann nun Berechnet werden, wie gut ein Alignment ist.

Weiter geht es mit dem Needleman-Wunsch Algorithmus.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.