Sottosequenza comune piu` lunga (programmazione dinamica

Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Sottosequenza comune piu' lunga
(programmazione dinamica)
Laboratorio di Programmazione II
Corso di Laurea in Bioinformatica
Dipartimento di Informatica - Università di Verona
Sommario
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Cammino piu' lungo su un DAG
Distanza di modica e sottosequenza comune piu' lunga
Cammino piu' lungo su un DAG
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Il problema del turista a manhattan
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Problema del turista a manhattan
Data una griglia regolare di nodi connessi da archi orientati
pesati (→ ↓)
Data un nodo sorgente src ed un nodo destinazione snk
Trovare il cammino piu' lungo da src ad snk
Intuizione:
griglia → mappa topologica di manhattan
archi orientati → strade di manhattan, peso → attrazioni
turistiche
src → locazione iniziale del turista, snk → destinazione
nale
Soluzione del problema del turista a manhattan
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Programmazione dinamica
Considerare tutti i cammini per una ricerca esaustiva non
e' praticabile
Scegliere sempre l'arco con peso piu' alto → porta a
soluzioni sub ottime
Programmazione dinamica, intuizione
trovo il cammino piu' lungo da src a tutti i nodi
per ogni nodo calcolo il cammino piu' lungo per arrivare a
quel nodo (s ) dati i cammini piu' lunghi per arrivare ai suoi
predecessori
si ,j = max {s↓ + w↓ , s→ + w→ }
restituisco il valore s della destinazione
Soluzione del problema del turista a manhattan
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Note
Programmazione dinamica → molto simile a ricorsione ma:
sso un ordine per le chiamate ricorsive
memorizzo i valori calcolati durante le chiamate ricorsive
L'ordine con cui valuto il valore s di un nodo e' importante
Per poter valutare correttamente il valore s di un nodo
devo aver valutato completamente il valore s dei suoi
predecessori
Manhattan come un DAG
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
il problema del turista a Manhattan e i DAG
La mappa topologica di Manhattan che abbiamo
considerato puo' essere considerata come un particolare
DAG
DAG: griglia regolare
Ordine utilizzato per la programmazione dinamica: un
particolare ordinamento topologico del DAG
Esempio: Problema del turista a Manhattan
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Example (Manhattan as a DAG)
3
0
Distanza di
modica e
sottosequenza comune
piu' lunga
2
3
1
1
5
0
3
4
2
2
7
Esempio: Ordine topologico per Manhattan
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Example (ordine topologico per manhattan)
B
A
C
3
3
0
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
2
1
5
0
2
E
D
1
3
0
2
4
B
A
F
C
3
7
D
5
E
1
F
4
7
Problema del cammino piu' lungo su DAG
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Cammino piu' lungo su DAG
Soluzione con Programmazione dinamica
trovo il cammino piu' lungo da src a tutti i nodi
per ogni nodo calcolo il cammino piu' lungo per arrivare a
quel nodo (s ) dati i cammini piu' lunghi per arrivare ai suoi
predecessori
sv = maxu∈pred (v ) {su + wu,v }
pred (v ) insieme dei predecessori di v
ordine topologico → calcolo su prima di calcolare il valore s
di tutti i suoi successori
Distanza di modica e sottosequenza comune piu'
lunga
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Distanza di modica
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Distanza di modica
date due stringhe v e w
distanzaModica(v,w) minimo numero di operazioni per
trasformare una stringa nell'altra con operazioni di
modica
inserire caratteri
eliminare caratteri
sostituzioni (noi non le consideriamo per il problema LCS)
Distanza di Modica: permette di comparare stringhe di
dimensioni diverse
Altre misure (e.g. distanza di Hamming) non lo
permettono
Allineamento
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Allineamento
date due stringhe v e w
Allineamento delle due stringhe e' una matrice con due
righe dove:
la prima riga contiene i caratteri di v con possibili spazi
la seconda riga contiene i caratteri di w con possibili spazi
nessuna colonna contiene due spazi
se n e' la lunghezza di v ed m e' la lunghezza di w allora il
massimo numero di colonne e' n + m
dato un allineamento la distanza di modica e' pari al
numero di colonne con spazi (nella prima o nella seconda
riga)
Esempio Allineamento
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Example (Allineamento)
A T - G T T A T A T C G T - A - C
Problema LCS
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Problema della Sottosequenza comune piu' lunga
una sottosequenza di una stringa v e' una sequenza
(ordinata) di caratteri non necessariamente consecutivi
v = ATTGCTA allora AGCA e ATTA sono sottosequenze
di v
una sottosequenza comune di due stringhe v e w e' una
sottosequenza di v e di w
v = ATCTGAT w = TGCATA allora TCTA e' una
sottosequenza comune
Vogliamo trovare la sottosequenza comune piu' lunga tra
due stringhe
Problema LCS e distanza di modica
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Sottosequenza comune piu' lunga e distanza di modica
se s (v , w ) indica la lunghezza della sottosequenza comune
piu' lunga tra v e w
se assumiamo possibili solo operazioni di inserzione e
modica
allora la distanza di modica d(v,w) = n + m - 2s(v,w)
se massimizzo s(v,w) minimizzo d(v,w)
Esempio LCS e Allineamento
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Example (Allineamento)
A T - C - T G A T
- T G C A T - A s(v,w) = 4, d(v,w) = 5 = 7 + 6 - 2*4
Problema LCS e DAG
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
LCS e grafo di modica
grafo di modica: grafo diretto aciclico che rappresenta
tutte le possibili operazioni di modica per due stringhe
griglia regolare con n+1 * m+1 nodi
archi sono etichettati con la modica da eettuare
grafo di modica per il problema LCS: diagonali solo tra
archi che hanno caratteri uguali
se massimizzo s(v,w) minimizzo d(v,w)
Esempio: LCS e grafo di modica
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
Example (LCS e grafo di modica)
A
0
G
1
2
3
4
5
6
7
8
+1
A
T
A - T
A G -
Esercizi: cammini su DAG e LCS
Sottosequenza
comune piu'
lunga (programmazione
dinamica)
Cammino
piu' lungo su
un DAG
Distanza di
modica e
sottosequenza comune
piu' lunga
cammino piu' lungo per DAG e LCS
validi per il progetto nale
Completare l'implementazione del metodo
computeSValues(...) della classe LongestPath.java
Implementare il metodo computeLongestPath(...) della
classe LongestPath.java
Implementare il metodo computeLabelledPath(...) della
classe EditGraph.java
Nota: scaricare la classe LDAG.java e la classe
AOEtichettato.java (utilizzate da EditGraph.java)