Dynamische Programmierung (4) Editierdistanz Approximative Zeichenkettensuche Sequence Alignment Prof. Dr. S. Albers
Prof. Dr. Th Ottmann
Dynamische Programmierung (4) Editierdistanz Approximative Zeichenkettensuche Sequence Alignment Prof. Dr. S. Albers
Prof. Dr. Th Ottmann
Dynamisches Programmieren
Algorithmenentwurfstechnik, oft bei Optimierungsproblemen
angewandt
Allgemein einsetzbar bei rekursiven Problemlöseverfahren, wenn
Teillösungen mehrfach benötigt werden
Lösungsansatz: Tabellieren von Teilergebnissen
Vorteil: Laufzeitverbesserungen, oft polynomiell statt exponentiell
Zwei verschiedene Ansätze
Bottom-up:
+ kontrollierte effiziente Tabellenverwaltung, spart Zeit
+ spezielle optimierte Berechnungsreihenfolge, spart Platz
- weitgehende Uncodierung des Originalprogramms erforderlich
möglicherweise Berechnung nicht benötigter Werte
Top-down: ( Memoisierung, Notizblockmethode)
+ Originalprogramm wird nur gering oder nicht verändert
+ Nur tatsächlich benötigte Werte werden berechnet
separate Tabellenverwaltung benötigt Zeit
Tabellengröße oft nicht optimal
Probleme der Ähnlichkeiten von Zeichenketten
Editier-Distanz
Berechne für zwei gegebene Zeichenfolgen A und B möglichst effizient die Editier-Distanz D(A,B) und eine minimale Folge von Editieroperationen, die A in B überführt.
i n f - - - o r m a t i k -
i n t e r p o l - a t i o n
Probleme der Ähnlichkeiten von Zeichenketten
Approximative Zeichenkettensuche
Finde für einen gegebenen Text T, ein Muster P und eine Distanz d alle Teilketten P´ in T mit D(P,P´) d
Sequence Alignment
Finde optimale Alignments zwischen DNA-Sequencen
G A G C A - C T T G G A T T C T C G G
- - - C A C G T G G - - - - - - - - -
Editier-Distanz
Gegeben: Zwei Zeichenketten A = a1a2 .... am und B = b1b2 ... bn
Gesucht: Minimale Kosten D(A,B) für eine Folge von Editieroperationen, um A in B zu überführen.
Editieroperationen:
1. Ersetzen eines Zeichens von A durch ein Zeichen von B
2. Löschen eines Zeichens von A
3. Einfügen eines Zeichens von B
Editier-Distanz
Einheitskostenmodell: Dreiecksungleichung soll für c im allgemeinen gelten:
c(a,c) c(a,b) + c(b,c)
Ein Buchstabe wird höchstens einmal verändert
Editier-Distanz
Spur als Repräsentation von Editiersequenzen
A = b a a c a a b c
B = a b a c b c a c
oder mit Indels
A = - b a a c a - a b c
B = a b a - c b c a - c
Editier-Distanz (Kosten) : 5
Aufteilung einer optimalen Spur ergibt zwei optimale Teilspuren
Dynamische Programmierung anwendbar
Berechnung der Editier-Distanz
Sei Ai = a1...ai und Bj = b1....bj
Di,j = D(Ai,Bj)
A
B
Berechnung der Editier-Distanz
Drei Möglichkeiten eine Spur zu beenden:
1. am wird durch bn ersetzt:
Dm,n = Dm-1,n-1 + c(am, bn)
2. am wird gelöscht: Dm,n = Dm-1,n + 1
3. bn wird eingefügt: Dm,n = Dm,n-1 + 1
Berechnung der Editier-Distanz
Di-1,j-1 Di-1,j Di,j Di,j-1 +d +1 +1 Rekursionsgleichung, falls m,n 1:
Berechnung aller Di,j erforderlich, 0 i m, 0 j n.
Algorithmus Editierdistanz
Input: Zwei Zeichenketten A = a1 .... am und B = b1 ... bn
Output: Die Matrix D = (Dij)
1 D[0,0] := 0
2 for i := 1 to m do D[i,0] = i
3 for j := 1 to n do D[0,j] = j
4 for i := 1 to m do
5 for j := 1 to n do
6 D[i,j] := min( D[i - 1,j] + 1,
7 D[i,j - 1] + 1,
8 D[i –1, j – 1] + c(ai,bj))
Beispiel für die Editier-Distanz
c a a b c a b a 4 3 2 1 4 3 2 1 0
Berechnung der Editieroperation
Algorithmus Editieroperationen (i,j)
Input: Berechnet Matrix D
1 if i = 0 and j = 0 then return
2 if i 0 and D[i,j] = D[i – 1 , j] + 1
3 then „lösche a[i]“
4 Editieroperationen (i – 1, j)
5 else if j 0 and D[i,j] = D[i, j – 1] + 1
6 then „füge b[j] ein“
7 Editieroperationen (i,j – 1)
8 else
/* D[i,j] = D[i – 1, j – 1 ] + c(a[i], b[j]) */
9 „ersetze a[i] durch b[j] “
10 Editieroperationen (i – 1, j – 1)
Aufruf: Editieroperationen(m,n)
Spurgraph der Editieroperationen
0 1 2 3 4 1 2 3 4 1 1 2 3 1 2 2 3 2 2 2 3 3 3 3 2 B = a b a c A = b a a c
Subgraph der Editieroperationen
Spurgraph: Übersicht über alle möglichen Spuren zur
Transformation von A in B, gerichtete Kanten von Knoten (i, j)
zu (i + 1, j), (i, j + 1) und (i + 1, j + 1).
Gewichtung der Kanten entsprechen den Editierkosten.
Kosten nehmen entland eines optimalen Weges monoton zu.
Jeder Weg mit monoton wachsenden Kosten von der linken oberen
Ecke zu rechten unteren Ecke entspricht einer optimalen Spur.
Approximative Zeichenkettensuche
T P j Gegeben: zwei Zeichenketten P = p1p2 ... pm ( Muster) und
T = t1t2 ... tn (Text)
Gesucht: Ein Intervall [j´, j], 1 j´ j n, so dass das Teilwort
Tj´ , j = tj´ ... tj das dem Muster P
ähnlichste Teilwort von T ist, d.h. für alle anderen
Intervalle [k´ , k], 1 k´ k n, gilt:
D(P,Tj´, j) D(P, Tk´, k)
Approximative Zeichenkettensuche
Naives Verfahren:
for all 1 j´ j n do
Berechne D(P,Tj´, j)
wähle Minimum
Comments