Dynamische
Programmierung (4)
Editierdistanz
Approximative Zeichenkettensuche
Sequence Alignment
Prof. Dr. S. Albers
Prof. Dr. Th Ottmann
WS03/04
1
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
WS03/04
2
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
WS03/04
3
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
i
WS03/04
n
n
f
t
- e r
- o r
p o l
m
-
a
a
t
t
i k i o n
4
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
GAG CA- CTTG GATTCTC G G
- - - CACGTGG- - - - - - - - -
WS03/04
5
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
WS03/04
6
Editier-Distanz
Einheitskostenmodell:
1 falls a  b
c ( a, b)  
0 falls a  b
a   , b   möglich
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
WS03/04
7
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
WS03/04
8
Berechnung der Editier-Distanz
Sei Ai = a1...ai und Bj = b1....bj
Di,j = D(Ai,Bj)
A
B
WS03/04
9
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
WS03/04
10
Berechnung der Editier-Distanz
Rekursionsgleichung, falls m,n  1:
 Dm1,n1

Dm ,n  min  Dm1,n
D
 m ,n1
 c(am , bn ),


1, 

1 
 Berechnung aller Di,j erforderlich, 0  i  m, 0  j  n.
Di-1,j-1
Di-1,j
+d
Di,j-1
WS03/04
+1
+1
Di,j
11
Rekursiongleichung für die Editier-Distanz
Anfangsbedingungen:
D0,0 = D(, ) = 0
D0,j = D(,Bj) = j
Di,0 = D(Ai,) = i
Rekursionsgleichung:
 Di 1, j 1

Di , j  min  Di 1, j
D
 i , j 1
WS03/04
 c(ai , b j )


1, 

1 
12
Berechnungsreihenfolge für die Editier-Distanz
b1 b2 b3 b4
.....
bn
a1
a2
am
WS03/04
Di-1,j-1
Di-1,j
Di,j-1
Di,j
13
Algorithmus für die Editier-Distanz
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))
WS03/04
14
Beispiel für die Editier-Distanz
0
WS03/04
b
1
a
2
a
3
c
4
a
b
a
c
1
2
3
4
15
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)
WS03/04
16
Spurgraph der Editieroperationen
a
b
a
c
0
1
2
3
4
b
1
1
1
2
3
a
2
1
2
2
3
a
3
2
2
2
3
c
4
3
3
3
2
=
B =
WS03/04
17
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.
WS03/04
18
Approximative Zeichenkettensuche
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)
j
T
P
WS03/04
19
Approximative Zeichenkettensuche
Naives Verfahren:
for all 1  j´  j  n do
Berechne D(P,Tj´, j)
wähle Minimum
WS03/04
20
Approximative Zeichenkettensuche
Betrachte verwandtes Problem:
j
T
i
E(i, j)
P
WS03/04
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.
21
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:
Ei , j  1min
D( Pi ,Tj, j )
 j ´ j 1
Optimale Spur:
Pi = b a a c a a b c
Tj´, j = b a c b c a c
WS03/04
22
Approximative Zeichenkettensuche
Rekursionsgleichung:
 Ei 1, j 1  c( pi , t j ),


Ei , j  min 
Ei 1, j  1,



E

1
i , j 1


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.
WS03/04
23
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´ .
WS03/04
24
Approximative Zeichenkettensuche
Abhängigkeitsgraph
T =
a
b
b
d
0
0
0
0
0
0
0
0
0
0
a
1
0
1
1
1
0
1
1
1
1
d
2
1
1
2
1
1
0
1
2
2
b
3
2
1
1
2
2
1
1
1
2
b
4
3
2
1
2
3
2
2
1
2
c
5
4
3
2
2
3
3
2
2
1
P
a
d
c
b
c
=
WS03/04
25
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
WS03/04
26
Ä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 TC G G A A T A G
WS03/04
27
Ähnlichkeit von Zeichenketten
Ähnlichkeitsmaß für Zeichenpaare:
Bsp.
Situation
allgemein
+1
für Match
-1
für Mismatch
-2
FürLeerzeichen
} s(a,b)
-c
Ähnlichkeitsmaß für Sequencen:
S ( A, B) 

Ähnlichkeit des Zeichenpaars
alleZeichenpaare
Ziel: Finde Alignment mit optimaler Ähnlichkeit
WS03/04
28
Ä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.
WS03/04
29
Ä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
WS03/04
30
Ä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 )
WS03/04
31
Ä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:
H i , j  max
1ii 1,
1 j  j 1
S ( Ai,i , B j, j )
Optimale Spur:
Ai´,i = b a a c a - a b c
Bj´,j = b a - c b c a - c
WS03/04
32
Ähnlichste Teilzeichenketten
Rekursionsgleichung:
 H i 1, j 1  s (ai , b j ),


H i 1, j  c,


H i , j  max 

H i , j 1  c,




0
Anfangsbedingung:
H0,0 = H(, ) = 0
Hi,0 = H(Aj ,) = 0
H0,j = H( ,Bj ) = 0
WS03/04
33

Microsoft PowerPoint Presentation: 16_4_DynProg