24.11.2000 - Multiple Alignment

Problem: Zu zwei gegebenen Sequenzen und gegebener Score-Funktion,
berechne das score-optimale Alignment der beiden Sequenzen.

Beobachtung: Die Sequenzen seien s1=xX, s2=yY, dabei seien x und y
die Anfangsstuecke (Praefixe) von s1 und s2, und X bzw. Y sei jeweils
der letzte Buchstabe von s1 bzw. s2.
Jedes Alignment (insbesondere das optimale) muss auf eine von drei Arten
Enden:
1. ...X dabei bedeuten die Punkte ein Alignment von x mit yY
...-

2. ...- dabei bedeuten die Punkte ein Alignment von xX mit y
...Y

3. ...X dabei bedeuten die Punkte ein Alignment von x mit y
...Y

Behauptung: Das OPTIMALE Alignment von xX und yY ergibt sich, wenn man die
BESTE Moeglichkeit aus folgenden dreien auswaehlt:
1. Verlaengere das OPTIMALE Alignment von x und yY mit (X,-)
2. Verlaengere das OPTIMALE Alignment von xX und y mit (-,Y)
3. Verlaengere das OPTIMALE Alignment von x und y mit (X,Y)

Beweisskizze: (Indirekt.) Angenommen, es gaebe noch ein besseres Alignment
von xX und yY. Das muesste auf eine der drei oben genannten Arten enden.
Jetzt Fallunterscheidung... Dann haette man auch schon ein besseres
Alignment von mindestens einem der drei Vorgaenger-Faelle gehabt.
Widerspruch mit Induktion.

D.h. man hat das optimale Alignment-Problem von xX und yY auf das von
kuerzeren Sequenzen zurueckgefuehrt. Man kann die optimale Score
von s1 und s2 also mit Hilfe einer Tabelle berechnen, in der man
die optimalen Scores aller Praefixkombinationen von s1 und s2 speichert:

Sei T[i,j] (0<=i<=laenge(s1), 0<=j<=laenge(s2)) die optimale Score
von s1[1..i] und s2[1..j].
Die nullte Zeile T[0,j] ist leicht zu berechnen, ebenso die erste Spalte
T[i,0] (hier ist ein Praefix einer der Sequenzen mit "nichts" aligniert,
und man vergibt die "Gap"-Strafe gemaess der Laenge des Praefixes)
Dann baut man die Tabelle zeilenweise (oder spaltenweise) gemaess
der obigen Behauptung.

Um nacher das Alignment auszugeben, muss man wissen, welche der drei
Moeglichkeiten in jeder Zelle der Tabelle zum optimalen Score gefuehrt
hat; das kann man sich in einer zweiten Tabelle merken.


Die "Hausaufgabe" war/ist, das zu programmieren und an einigen Sequenzen
zu testen.