Dynamische Programmierung (4) Editierdistanz Approximative Zeichenkettensuche Sequence Alignment Prof. Dr. S. Albers
Prof. Dr. Th Ottmann
Approximative Zeichenkettensuche
T j i E(i, j) P Für jede Textstelle j und jede Musterstelle i berechne
die Editierdistanz des zu Pi ähnlichsten, bei j endenden
Teilstücks Tj´,j von T. Betrachte verwandtes Problem:
Approximative Zeichenkettensuche
Methode:
for all 1 j n do
Berechne j´, so dass D(P,Tj´, j) minimal ist
Für 1 i m und 0 j n sei:
Optimale Spur:
Pi = b a a c a a b c
Tj´, j = b a c b c a c
Approximative Zeichenkettensuche
Rekursionsgleichung:
Bemerkung:
j´ kann für Ei-1, j-1, Ei – 1,j und Ei, j – 1 ganz verschieden sein.
Teilspur einer optimalen Spur ist eine optimale Teilspur.
Approximative Zeichenkettensuche
Anfangsbedingungen:
E0,0 = E(, ) = 0
Ei,0 = E(Pj ,) = i
aber
E0,j = E( ,Tj) = 0
Beobachtung:
Die optimale Editiersequenz von P nach Tj´, j beginnt nicht mit
einer Einfügung von tj´ .
Approximative Zeichenkettensuche
0 1 2 3 4 0 0 0 0 0 1 1 1 1 1 2 1 2 1 1 2 3 2 1 2 0 0 1 2 3 0 0 0 0 1 1 1 1 0 1 2 2 1 1 1 2 2 2 1 2 5 4 3 2 2 3 3 2 2 1 T = a b b d a d c b c P = a d b b c Abhängigkeitsgraph
Approximative Zeichenkettensuche
Satz
Gibt es im Abhängigkeitsgraphen einen Weg von E0, j´- 1 nach Ei, j , so ist
Tj´, j ein zu Pi ähnlichstes, bei j endendes Teilstück von T mit
D(Pi, Tj´,j) = Ei, j
Ähnlichkeit von Zeichenketten
Sequence Aligment:
Finde für zwei DNA – Sequenzen Einfügestellen von Leerzeichen, so
dass die Sequenzen möglichst ähnlich sind
G A - C G G A T T A G
G A T C G G A A T A G
Ähnlichkeit von Zeichenketten
- c FürLeerzeichen - 2 für Mismatch - 1 } s(a,b) für Match + 1 allgemein Situation Bsp. Ähnlichkeitsmaß für Zeichenpaare:
Ähnlichkeitsmaß für Sequencen:
Ziel: Finde Alignment mit optimaler Ähnlichkeit
Ähnlichkeit von Zeichenketten
Ähnlichkeiten zweier Zeichenketten S(A,B)
Operationen:
1. Ersetzen eines Zeichens a durch ein Zeichen b :
Gewinn: s(a,b)
2. Löschen eines Zeichens von A, Einfügen eines Zeichens von B Verlust: – c
Aufgabe:
Finde eine Folge von Operationen zur Unwandlung von A in B,
so dass die Summe der Gewinne maximiert wird.
Ähnlichkeit von Zeichenketten
Si,j = S(Ai, Bj) , 0 i m , 0 j n
Rekursionsgleichung:
Sm,n = max (Sm-1,n-1 + s(am, bn),
Sm-1,n - c, Sm,n-1 - c)
Anfangsbedingung:
S0,0 = S(, ) = 0
S0,j = S(, Bj) = - jc
Si,0 = S(Ai ,) = - ic
Ähnlichste Teilzeichenketten
Gegeben: zwei Zeichenketten A = a1 .... am und B = b1 ... bn
Gesucht: Ein zwei Intervalle [i´, i] [1, m] und [j´, j] [1, n],
so dass:
S(Ai´,i , Bj´,j ) S(Ak´,k , Bl´,l ),
für alle [k´,k] [1, m] und [l´,l] [1, n].
Naives Verfahren:
for all [i´, i] [1, m] and [j´, j] [1, n] do
Berechne S(Ai´,i , Bj´,j )
Ähnlichste Teilzeichenketten
Methode:
for all 1 i m , 1 j n do
Berechne i´ und j´, so dass S(Ai´,i , Bj´,j ) maximal ist
Für 0 i m und 0 j n sei:
Optimale Spur:
Ai´,i = b a a c a - a b c
Bj´,j = b a - c b c a - c
Comments