Declumbing

Obwohl es genügend Motivation gibt, (sub)optimale Alignments und ihre Anzahl zu bestimmen, hat die besprochene Methode einen Nachteil. Man erhält unter Umständen eine sehr große Anzahl von Alignments, welche sich nur unwesentlich unterscheiden. Dies ist nicht immer das, was man will. So ist man z.B. an allen ``guten'' lokalen Alignments interessiert, welche keinen (Mis)Match gemeinsam haben. In den Übungen wird mit Hilfe des jetzt besprochenen ``Declumbing''-Algorithmus versucht, mehrere Vorkommen eines kleineren Lektin Moleküls in einem größeren zu identifizieren. Man kennt die Funktion des kleineren Moleküls (Docking-Stelle für Zucker) und kann dann mit Hilfe von Declumbing bestimmen, wo das größere Molekül ebenfalls potentielle Docking-Stellen besitzt. Wir werden nun das Problem für lokales Alignment formaler erklären.

Definition 7   Sei A ein gebenenes lokales Alignment. Mit clump(A) (Klumpen) bezeichnen wir eine Menge von Alignments, in der jedes Alignment einen Match bzw. Mismatch mit A teilt.

Unser Ziel ist es nun, gegeben ein ``cutoff'' Wert $\Delta$, von allen clumps C(A), welche ein $\delta$-optimales Alignment A, mit $\delta \leq \Delta$ enthalten, genau einen optimalen Repräsentanten auszugeben. Wir wollen also alle genügend guten und genügend verschiedenen Alignments ausgeben. Der Algorithmus für lokales Alignment mit declumbing läuft dann im Prinzip wie folgt ab:

1.

Während der Berechnung von S_i,j speichern wir (i,j) mit dem Wert S_i,j in einer Maximum-Warteschlange.

2.

Wir entfernen nun das maximale Element M und die entprechende Position (i,j) aus der Warteschlange und führen folgende Fallunterscheidung durch:

(a)

$S_{i,j} \neq M$
Nimm das nächste Element. In diesem Fall ist Position (i,j) der Anfang eines Alignments, welches zu einem Clump gehört, dessen optimaler Repräsentant schon ausgegeben wurde.

(b)

  S_i,j = M
Gebe das optimale lokale Alignment A von Position (i,j) aus und ändere die Matrix S so ab, daß während des Algorithmus keine Alignment aus der Menge clump(A) mehr ausgegeben wird.

Der entscheidende Schritt in obigem Algorithmus liegt natürlich darin, die Matrix in Schritt 2b so abzuändern, daß die Effekte der Alignments in dem Clump aus der Matrix entfernt werden.

Der Einfachheit halber nehmen wir den Fall von konstanten Indel-Kosten g. Wir nehmen an, daß der optimale Repräsentant A eines clumps von Position (k,l) bis Position (o,p) mit k<o und l<p läuft. Wir wollen mit S^* die geänderte Matrix bezeichnen. Es ist klar, daß S^*_i,j = S_i,j für i<k oder j<l und $S^*_{k,l} = \max\{0,S^*_{k-1,l}-g,S^*_{k,l-1}-g\}$, d.h. der Match (k,l) ist nicht erlaubt. Wir müssen nun von k abwärts solange Einträge neu berechnen, bis in einer Zeile k'>k die beiden Matrizen übereinstimmen. In Zeile k fangen wir an Position l+1 an und berechnen S^*_k,j für alle $j=l+1,\ldots,j'$, wobei j' der minimale Index mit S^*_k,j'=S_k,j' ist. Die Neuberechnungsregel lautet dann:

• $S^*_{k',j'} = \max\{0,S^*_{k'-1,j}-g,S^*_{k',j'-1}-g\}$, falls (k',j') ein (Mis)match in A ist.
• $S^*_{k',j'} = \max\{0,S^*_{k'-1,j}-g,S^*_{k',j'-1}-g,S^*_{k'-1,j'-1}+s(a_{k'},b_{j'}\}$, sonst.

Man muß in darauffolgenden Zeilen die jeweilige Zeile mindestens bis zur letzten geänderten Position in der vorausgehenden Zeile berechnen und mindestens ab der ersten geänderten Position.

Der Algorithmus soll für affine Gapkosten in der Übung implementiert werden und u.a. an dem bereits erwähnten Lektinbeispiel ausgetestet werden.