Allineamento di stringhe e sottosequenza palindroma più lunga

Due esercitazioni sulla programmazione dinamica (Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigmala programmazione dinamica (DP) evolve il divide and conquer: invece di risolvere di nuovo le stesse sottoistanze, le salva in una tabella. Fibonacci ricorsivo costa F_n - 1 addizioni (esponenziale), quello con tabella n - 1. Tre condizioni: sottostruttura, sottoistanze ripetute, spazio dei sottoproblemi ristretto. Bottom-up o memoizzazione (ricorsione + tabella globale). Per i problemi di ottimizzazione lo schema è: sottostruttura ottima, ricorrenza sui costi, informazione addizionale, calcolo della tabella, ricostruzione.Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma →) che riusano la struttura della Longest Common Subsequence - ricorrenza, tabella e ricostruzionela LCS di X (m caratteri) e Y (n caratteri) è la sottosequenza comune più lunga. Sottoistanze = coppie di prefissi (Theta(mn)). Ricorrenza: l(i,j) = 0 se i = 0 o j = 0; 1 + l(i-1,j-1) se x_i = y_j; max{l(i-1,j), l(i,j-1)} altrimenti. Bottom-up con tabelle l e b (freccia): mn confronti; ricostruzione in O(m+n). Il D&C sulla stessa ricorrenza costa C(m+n,m) - 1 nodi interni nel caso peggiore (esponenziale). Memoizzazione: stessa complessità nel caso peggiore, ma molto meno lavoro su stringhe simili. Spazio ridotto a Theta(min{m,n}) se serve solo la lunghezza.Longest Common Subsequence - ricorrenza, tabella e ricostruzione →: la prima con lo stesso spazio dei sottoproblemi (coppie di prefissi), la seconda con uno spazio diverso (sottostringhe).

Allineamento di stringhe di DNA

L'alfabeto del DNA è $\Sigma_{DNA} = \{A, C, G, T\}$ (i quattro nucleotidi); per l'allineamento si estende con un carattere di spazio, $\Sigma^E_{DNA} = \{A, C, G, T, -\}$. Si risolve un problema di ottimizzazione molto simile alla LCS e il costo ottimo è una metrica di similarità tra le due stringhe.

Definizione del problema

Definizione (allineamento). Date $X = \langle x_1, \dots, x_m \rangle$ e $Y = \langle y_1, \dots, y_n \rangle$ su $\Sigma_{DNA}$, un allineamento di lunghezza $k$ è una coppia di stringhe $Z^X = \langle z^X_1, \dots, z^X_k \rangle$, $Z^Y = \langle z^Y_1, \dots, z^Y_k \rangle$ su $\Sigma^E_{DNA}$, con $k \ge \max\{m, n\}$, tali che:

1. $X$ è sottosequenza di $Z^X$ e $Y$ è sottosequenza di $Z^Y$ (esistono $1 \le i_1 < \dots < i_m \le k$ con $X = \langle z^X_{i_1}, \dots, z^X_{i_m} \rangle$, e analogamente per $Y$);
2. le posizioni che non realizzano caratteri di $X$ (rispettivamente $Y$) contengono solo $-$;
3. in ogni posizione $r$ non ci sono due $-$: $(z^X_r \in \Sigma_{DNA}) \lor (z^Y_r \in \Sigma_{DNA})$.

In pratica ogni posizione (colonna) dell'allineamento è di uno di tre tipi: carattere di $X$ sopra carattere di $Y$; carattere di $X$ sopra uno spazio; spazio sopra carattere di $Y$.

Esempio. $X = \langle A, G, T, T \rangle$, $Y = \langle A, T, T \rangle$. Due allineamenti:

Z^X = A G T T          Z^X = A G T T
Z^Y = A - T T          Z^Y = A T T -

Nel secondo, la posizione $2$ realizza insieme $x_2 = G$ e $y_2 = T$.

Costo. Una matrice di score $S \in \mathbb{Z}^{4 \times 4}$ dà un intero $s_{UV}$ per ogni coppia ordinata di nucleotidi $(U, V)$ (di solito simmetrica, positiva sulla diagonale per i match, negativa altrove); la penalità di gap $g \in \mathbb{Z}$ (di solito negativa) è il peso di una posizione con uno spazio. Il peso di una posizione e il costo dell'allineamento sono

$$p(z^X_r, z^Y_r) = \begin{cases} s_{z^X_r z^Y_r} & z^X_r \ne - \ \land \ z^Y_r \ne - \\ g & \text{altrimenti} \end{cases} \qquad c(Z^X, Z^Y) = \sum_{r=1}^{k} p(z^X_r, z^Y_r).$$

Problema dell'allineamento ottimo. Date $X, Y \in \Sigma_{DNA}^*$, $S$ e $g$, determinare il costo massimo di un allineamento delle due stringhe.

Esempio (seguito). $s_{UU} = 1$, $s_{UV} = -3$ per $U \ne V$, $g = -2$. Il primo allineamento costa $1 + (-2) + 1 + 1 = 1$; il secondo $1 + (-3) + 1 + (-2) = -3$. Il primo è ottimo (controllato enumerando tutti i $129$ allineamenti ammissibili delle due stringhe: nessuno supera $1$).

Sottostruttura ottima

Appena si sceglie come finiscono i due allineamenti, il resto è un allineamento di prefissi. Lo spazio dei sottoproblemi è quindi quello della LCS: $\{(X_i, Y_j) : 0 \le i \le m,\ 0 \le j \le n\}$.

Casi base. Se $i = 0$ il prefisso $X_0$ è vuoto: per la condizione 3 non possono esserci due spazi nella stessa posizione, quindi l'unico allineamento ammissibile di $(\varepsilon, Y_j)$ è $Z^{X_0} = \langle -, \dots, - \rangle$ ($j$ spazi), $Z^{Y_j} = Y_j$, di costo $j \cdot g$. Simmetricamente per $j = 0$ il costo è $i \cdot g$; per $i = j = 0$ la coppia di stringhe vuote ha costo $0$.

Casi non di base ($i > 0$, $j > 0$). Sia $(Z^{X_i}, Z^{Y_j})$ un allineamento ottimo di $(X_i, Y_j)$, di lunghezza $k$. L'ultima posizione può essere solo di tre tipi:

1. $z^{X_i}_k = x_i$ e $z^{Y_j}_k = y_j$ (l'ultima posizione realizza gli ultimi caratteri di entrambi). Allora le prime $k - 1$ posizioni sono un allineamento ottimo di $(X_{i-1}, Y_{j-1})$ — altrimenti, con il cut-and-paste, se ne potrebbe sostituire uno migliore e ottenere un allineamento di $(X_i, Y_j)$ di costo superiore — e $c(Z^{X_i}, Z^{Y_j}) = c(Z^{X_{i-1}}, Z^{Y_{j-1}}) + s_{x_i y_j}$.
2. $z^{X_i}_k = x_i$ e $z^{Y_j}_k = -$ (solo l'ultimo carattere di $X_i$). Le prime $k - 1$ posizioni sono un allineamento ottimo di $(X_{i-1}, Y_j)$ e $c = c(Z^{X_{i-1}}, Z^{Y_j}) + g$.
3. $z^{X_i}_k = -$ e $z^{Y_j}_k = y_j$, simmetrico: allineamento ottimo di $(X_i, Y_{j-1})$ e $c = c(Z^{X_i}, Z^{Y_{j-1}}) + g$.

I tre allineamenti ottenuti dai tre punti a partire dagli ottimi dei sottoproblemi sono tutti ammissibili, quindi vince quello di costo massimo.

Ricorrenza sui costi

Con $C(i, j)$ il costo dell'allineamento ottimo di $(X_i, Y_j)$, per $0 \le i \le m$ e $0 \le j \le n$:

$$C(i, j) = \begin{cases} j \cdot g & i = 0 \\ i \cdot g & j = 0 \\ \max\{\, C(i-1, j-1) + s_{x_i y_j},\ \ C(i-1, j) + g,\ \ C(i, j-1) + g \,\} & i > 0 \ \land \ j > 0 \end{cases}$$

Per ricostruire l'allineamento si salva, come nella LCS, una freccia: $\nwarrow$, $\uparrow$ o $\leftarrow$ secondo quale dei tre termini realizza il massimo.

Codice bottom-up

Il grafico delle dipendenze è identico a quello della LCS (la cella $(i, j)$ dipende da $(i-1, j-1)$, $(i-1, j)$ e $(i, j-1)$), quindi si riempie per righe.

ALIGN(X, Y, S, g)
  m <- |X|; n <- |Y|
  for i <- 0 to m do C[i, 0] <- i * g; b[i, 0] <- '↑'     { b[0, 0] non viene letta }
  for j <- 1 to n do C[0, j] <- j * g; b[0, j] <- '←'
  for i <- 1 to m do
    for j <- 1 to n do
      d <- C[i-1, j-1] + S[x_i, y_j]
      u <- C[i-1, j] + g
      l <- C[i, j-1] + g
      C[i, j] <- max(d, u, l)
      if C[i, j] = d then b[i, j] <- '↖'
      else if C[i, j] = u then b[i, j] <- '↑'
      else b[i, j] <- '←'
  return (C[m, n], b)

PRINT_ALIGN(X, Y, b, i, j)       { stampa le colonne dell'allineamento da sinistra a destra }
  if i = 0 and j = 0 then return
  if b[i, j] = '↖' then
    PRINT_ALIGN(X, Y, b, i-1, j-1);  stampa la colonna (x_i sopra y_j)
  else if b[i, j] = '↑' then
    PRINT_ALIGN(X, Y, b, i-1, j);    stampa la colonna (x_i sopra '-')
  else
    PRINT_ALIGN(X, Y, b, i, j-1);    stampa la colonna ('-' sopra y_j)

Il costo è $\Theta(mn)$ (confronti e addizioni tra interi) e la ricostruzione ha $O(m + n)$ chiamate.

Esempio eseguito

$X = ACCGT$, $Y = AGCT$, $s_{UU} = 1$, $s_{UV} = -3$ per $U \ne V$, $g = -2$. In grassetto il percorso della ricostruzione.

Celle a mano:

• Riga $0$ e colonna $0$: $C(0, j) = j \cdot (-2)$ e $C(i, 0) = i \cdot (-2)$.
• $(1, 1)$: $x_1 = y_1 = A$, quindi $C(0, 0) + s_{AA} = 0 + 1 = 1$; le altre due scelte danno $C(0,1) + g = -4$ e $C(1,0) + g = -4$. Massimo $1$, $\nwarrow$.
• $(2, 2)$: $x_2 = C$ e $y_2 = G$ sono diversi: $C(1,1) + s_{CG} = 1 - 3 = -2$; $C(1,2) + g = -1 - 2 = -3$; $C(2,1) + g = -1 - 2 = -3$. Massimo $-2$, $\nwarrow$.
• $(2, 3)$: $x_2 = y_3 = C$: $C(1,2) + 1 = -1 + 1 = 0$, contro $-5$ e $-4$. Vale $0$.
• $(4, 3)$: $x_4 = G$, $y_3 = C$. $C(3,2) + s_{GC} = -4 - 3 = -7$; $C(3,3) + g = -1 - 2 = -3$; $C(4,2) + g = -2 - 2 = -4$. Massimo $-3$ con $\uparrow$: $G$ è allineata a uno spazio.

Risultato: $C(5, 4) = -2$. Ricostruzione: $(5,4) \nwarrow$ colonna $(T, T)$; $(4,3) \uparrow$ colonna $(G, -)$; $(3,3) \nwarrow$ colonna $(C, C)$; $(2,2) \nwarrow$ colonna $(C, G)$; $(1,1) \nwarrow$ colonna $(A, A)$. Letto in avanti:

Z^X = A C C G T
Z^Y = A G C - T       costo: 1 + (-3) + 1 + (-2) + 1 = -2

La tabella e la ricostruzione sono state confrontate con una enumerazione di tutti gli allineamenti su $300$ coppie casuali di stringhe corte e matrici di score casuali.

Spazio lineare

Le stringhe di DNA sono molto lunghe e uno spazio $\Theta(mn)$ è inaccettabile. Se serve solo il costo ottimo (nessuna ricostruzione) basta una sola riga, anzi un solo vettore $C[0..n]$, supponendo $n \le m$ (altrimenti si scambiano i ruoli). All'inizio dell'iterazione $j$ interna all'iterazione $i$, $C[0..j-1]$ contiene la riga $i$ già calcolata, e $C[j..n]$ la riga $i - 1$. Calcolando $C(i, j)$ servono $C(i-1, j-1)$, $C(i-1, j) = C[j]$ e $C(i, j-1) = C[j-1]$. Il primo termine va conservato prima di sovrascrivere $C[j]$: lo si tiene nella variabile prev.

ALIGNMENT_COST(X, Y, S, g)                { vincolo: |X| >= |Y| }
  m <- |X|; n <- |Y|
  for j <- 0 to n do C[j] <- j * g       { riga 0 }
  for i <- 1 to m do
    prev <- C[0]                         { C(i-1, 0), serve alla colonna j = 1 }
    C[0] <- i * g                        { C(i, 0) }
    for j <- 1 to n do
      new <- max(prev + S[x_i, y_j], C[j] + g, C[j-1] + g)
      prev <- C[j]                       { C(i-1, j), per la colonna j+1 }
      C[j] <- new
  return C[n]

Nell'esempio, dopo l'iterazione $i$ il vettore vale la riga $i$ della tabella: dopo $i = 1$ è $(-2, 1, -1, -3, -5)$, dopo $i = 3$ è $(-6, -3, -4, -1, -3)$, e alla fine $C[4] = -2$. Il tempo è $\Theta(mn)$, lo spazio ausiliario $\Theta(\min\{m, n\})$; verificato su stringhe casuali contro la tabella completa.

Memoizzazione e spazio. Il codice memoizzato non permette di risparmiare spazio, perché le sottoistanze sono generate in ordine dinamico e non ordinato. In compenso, su sequenze molto simili fa molto meno lavoro del bottom-up. Il compromesso: se lo spazio quadratico non è un problema, la memoizzazione è preferibile; con spazio lineare serve il bottom-up (più lento su DNA molto simili).

Sottosequenza palindroma più lunga (LPS)

Definizione. Una stringa $Z = \langle z_1, \dots, z_m \rangle$ è palindroma se $z_{1+h} = z_{m-h}$ per $0 \le h \le m - 1$, cioè $Z$ è uguale alla stringa letta al contrario. La stringa vuota è palindroma ($m = 0$). Esistono palindrome di lunghezza pari ($\langle A, C, C, A \rangle$) e dispari ($\langle A, I, A \rangle$).

Data $X = \langle x_1, \dots, x_n \rangle$, si cerca la sua Longest Palindrome Subsequence, $\text{LPS}(X)$: la sottosequenza palindroma più lunga. Per esempio $X = \langle S, O, B, S \rangle$ ha $\text{LPS}(X) = \langle S, O, S \rangle$.

Lo spazio dei sottoproblemi

Se $Z = \langle z_1, \dots, z_m \rangle$ è una sottosequenza palindroma di $X$, realizzata dagli indici $j_1 < \dots < j_m$, allora anche $Z_{2..m-1}$ è palindroma, ed è sottosequenza di $X_{2..n-1}$ (se non è vuota), perché $j_2 > 1$ e $j_{m-1} < n$. Si toglie un carattere da ciascun estremo: servono quindi le sottostringhe $X_{i..j}$, non i prefissi. Lo spazio è $\mathcal{S}_X = \{X_{i..j} : 1 \le i \le j \le n\}$, di cardinalità $\Theta(n^2)$.

Sottostruttura ottima

Sia $Z = \langle z_1, \dots, z_m \rangle$ una LPS di $X_{i..j}$.

1. $i = j$: $Z = \langle x_i \rangle$ (base).
2. $j = i + 1$: se $x_i = x_j$ allora $Z = \langle x_i, x_j \rangle$, altrimenti $Z = \langle x_i \rangle$ oppure $Z = \langle x_j \rangle$ (base).
3. $j > i + 1$ (almeno tre caratteri):
   • se $x_i = x_j$, allora $z_1 = z_m = x_i$ e $Z_{2..m-1}$ è una LPS di $X_{i+1..j-1}$;
   • se $x_i \ne x_j$, allora $Z$ è la più lunga tra una LPS di $X_{i+1..j}$ e una LPS di $X_{i..j-1}$.

Dimostrazione dei punti 1 e 2: banali. Punto 3, $x_i = x_j$. Siano $j_1 < \dots < j_m$ gli indici che realizzano $Z$. Si dimostra prima $z_1 = z_m = x_i$. Se $Z = \varepsilon$ o $z_1 = z_m \ne x_i$, allora $\langle x_i, Z, x_j \rangle$ sarebbe ancora palindroma (i due estremi sono uguali tra loro) e sottosequenza di $X_{i..j}$ (usa gli indici $i < j_1$ e $j > j_m$, perché $z_1, z_m \ne x_i$ implica che né $i$ né $j$ siano tra gli indici di $Z$), più lunga di $Z$ di $2$ caratteri: contraddizione. Quindi $z_1 = z_m = x_i$ e $m \ge 2$. $Z_{2..m-1}$ è palindroma ed è sottosequenza di $X_{i+1..j-1}$. Se non fosse una LPS di $X_{i+1..j-1}$, si prenderebbe una LPS $Z'$ di $X_{i+1..j-1}$ e $\langle x_i, Z', x_j \rangle$ sarebbe una sottosequenza palindroma di $X_{i..j}$ più lunga di $Z$ (cut-and-paste).

Punto 3, $x_i \ne x_j$. Poiché $Z$ è palindroma, $z_1 = z_m$ non può essere uguale sia a $x_i$ sia a $x_j$. Se $z_1 = z_m \ne x_i$, l'indice $i$ non è usato e $Z$ è una sottosequenza di $X_{i+1..j}$; se $z_1 = z_m \ne x_j$, $Z$ è sottosequenza di $X_{i..j-1}$ (può valere anche entrambi). In ciascun caso $Z$ è palindroma e, per cut-and-paste, deve essere una LPS della sottostringa corrispondente. Poiché le LPS di $X_{i+1..j}$ e $X_{i..j-1}$ sono anche sottosequenze palindrome di $X_{i..j}$, $Z$ è la più lunga delle due. $\square$

Ricorrenza e informazione addizionale

Con $p(i, j) = |\text{LPS}(X_{i..j})|$, per $1 \le i \le j \le n$:

$$p(i, j) = \begin{cases} 1 & i = j \\ 2 & j = i + 1 \ \land \ x_i = x_j \\ 1 & j = i + 1 \ \land \ x_i \ne x_j \\ 2 + p(i+1, j-1) & j > i + 1 \ \land \ x_i = x_j \\ \max\{p(i+1, j),\ p(i, j-1)\} & j > i + 1 \ \land \ x_i \ne x_j \end{cases}$$

Informazione addizionale, per i casi $j > i + 1$: $b(i, j) = \swarrow$ se $\text{LPS}(X_{i..j}) = \langle x_i, \text{LPS}(X_{i+1..j-1}), x_j \rangle$; $\downarrow$ se $= \text{LPS}(X_{i+1..j})$; $\leftarrow$ se $= \text{LPS}(X_{i..j-1})$.

Codice bottom-up per diagonali

Sia $\ell = j - i + 1$ la lunghezza della sottostringa. I casi base stanno sulle diagonali $\ell = 1$ e $\ell = 2$. Per $\ell \ge 3$, la cella $(i, j)$ dipende da $(i+1, j-1)$ (lunghezza $\ell - 2$) e da $(i+1, j)$ e $(i, j-1)$ (lunghezza $\ell - 1$): una scansione per diagonali crescenti è coerente. Sono valide anche la scansione per righe dalla $n$ alla $1$ (colonne crescenti) e quella per colonne dalla $1$ alla $n$ (righe decrescenti).

COMPUTE_P(X)
  n <- |X|
  for i <- 1 to n-1 do
    P[i, i] <- 1
    if x_i = x_{i+1} then P[i, i+1] <- 2 else P[i, i+1] <- 1
  P[n, n] <- 1
  for l <- 3 to n do
    for i <- 1 to n - l + 1 do
      j <- i + l - 1
      if x_i = x_j then
        P[i, j] <- P[i+1, j-1] + 2;  B[i, j] <- '↙'
      else if P[i+1, j] >= P[i, j-1] then
        P[i, j] <- P[i+1, j];        B[i, j] <- '↓'
      else
        P[i, j] <- P[i, j-1];        B[i, j] <- '←'
  return (P[1, n], B)

Costo. Spazio $\Theta(n^2)$ per $P$ e $B$. Un confronto tra caratteri per ogni sottostringa di lunghezza $\ge 2$, cioè per ogni coppia $i < j$:

$$T(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \sum_{i=1}^{n-1} (n - i) = \sum_{i'=1}^{n-1} i' = \frac{n(n-1)}{2} = \Theta(n^2).$$

Se interessa solo la lunghezza, le tabelle si possono sostituire con tre vettori (diagonali $\ell$, $\ell - 1$ e $\ell - 2$), spazio lineare, come per la LCS (verificato con Python).

Esempio eseguito

$X = ABCBDACB$ ($n = 8$). Ogni cella $(i, j)$ con $i < j$ contiene $p(i, j)$ e la freccia; in grassetto le celle visitate dalla ricostruzione.

Alcune celle:

• $(2, 4)$: $x_2 = x_4 = B$, quindi $p = 2 + p(3, 3) = 2 + 1 = 3$ ($\swarrow$).
• $(1, 3)$: $x_1 = A \ne C = x_3$; $p(2, 3) = 1$ e $p(1, 2) = 1$ sono uguali, e per il $\ge$ del codice si sceglie $\downarrow$.
• $(1, 6)$: $x_1 = x_6 = A$, quindi $p = 2 + p(2, 5) = 2 + 3 = 5$ ($\swarrow$).
• $(1, 8)$: $x_1 = A \ne B = x_8$; $p(2, 8) = 5 \ge p(1, 7) = 5$, quindi $\downarrow$.

Ricostruzione (cammino evidenziato): $(1,8) \downarrow$ passa a $(2,8)$, che è $\swarrow$ e stampa $x_2 = B$; $(3,7)$ è $\swarrow$ e stampa $C$; $(4,6)$ è $\downarrow$ e va a $(5,6)$, dove $j = i + 1$ e $x_5 = D \ne A = x_6$: si stampa $x_5 = D$; risalendo si stampano $x_7 = C$ e $x_8 = B$. La LPS è $\langle B, C, D, C, B \rangle$, di lunghezza $p(1, 8) = 5$ (la stessa dei controlli con forza bruta e con $\text{LCS}(X, X^R)$).

PRINT_LPS(X, B, i, j)                      { prima chiamata: PRINT_LPS(X, B, 1, n) }
  if i = j then print(x_i); return
  if j = i + 1 then
    if x_i = x_j then print(x_i x_j) else print(x_i)
    return
  if B[i, j] = '↙' then
    print(x_i)
    PRINT_LPS(X, B, i+1, j-1)
    print(x_j)
  else if B[i, j] = '↓' then PRINT_LPS(X, B, i+1, j)
  else PRINT_LPS(X, B, i, j-1)

(Nelle dispense i return e il ramo else dei casi base sono omessi: senza di essi, dopo il caso base il codice leggerebbe $B[i,j]$, non definito.) Il numero di caratteri stampati è $|\text{LPS}(X)| = O(n)$. L'albero delle chiamate ha un solo nodo per livello e la differenza $j - i$ (all'inizio $n - 1$) decresce di $1$ o di $2$ a ogni livello, fino a $1$ o $0$: i confronti sono $\Theta(n)$.

Relazione con la LCS. $\text{LPS}(X)$ ha la stessa lunghezza di $\text{LCS}(X, X^R)$, con $X^R$ la stringa rovesciata (verificato per $400$ stringhe casuali). Il codice dedicato è però più economico: usa il solo triangolo superiore ($n(n-1)/2$ confronti, invece degli $n^2$ della LCS).

def lps_len(x):
    n = len(x)
    p = [[0] * n for _ in range(n)]
    for i in range(n):
        p[i][i] = 1
    for i in range(n - 1):
        p[i][i + 1] = 2 if x[i] == x[i + 1] else 1
    for l in range(3, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            p[i][j] = p[i + 1][j - 1] + 2 if x[i] == x[j] else max(p[i + 1][j], p[i][j - 1])
    return p[0][n - 1]

assert lps_len("ABCBDACB") == 5 and lps_len("SOBS") == 3

Domande d'esame

1. (Risposta numerica.) Per $X = \langle S, O, B, S \rangle$ qual è $\text{LPS}(X)$ e quanti confronti tra caratteri esegue COMPUTE_P su una stringa di $n = 10$ caratteri? Traccia: $\langle S, O, S \rangle$; $n(n-1)/2 = 45$ confronti.
2. (Quesito aperto.) Perché per la LPS lo spazio dei sottoproblemi è quello delle sottostringhe e non dei prefissi? Come si scandisce la tabella? Traccia: a ogni passo si tolgono caratteri da entrambi gli estremi, quindi servono sottostringhe $X_{i..j}$ ($\Theta(n^2)$); $(i, j)$ dipende da $(i+1, j-1)$, $(i+1, j)$, $(i, j-1)$, di lunghezza $\ell - 2$ e $\ell - 1$: per diagonali crescenti.
3. (Calcolo.) Con $s_{UU} = 1$, $s_{UV} = -3$ e $g = -2$, per $X = \langle A, C \rangle$ e $Y = \langle A \rangle$ quanto vale $C(2, 1)$? Qual è l'allineamento? Traccia: $C(1, 1) = 1$, $C(2, 0) = -4$, $C(1, 0) = -2$; $C(2, 1) = \max\{-2 - 3,\ 1 - 2,\ -4 - 2\} = -1$, con $\uparrow$: $A C / A -$, costo $1 - 2 = -1$.

Esercizi svolti di esame su problemi dello stesso tipo (ricorrenza sulle sottostringhe, scansione per diagonali): Esercizio - sottosequenza quasi palindroma di lunghezza massima (compito dell'8 luglio 2024, es. 2) e Esercizio - sottosequenza antipalindroma di lunghezza massima (compito del 9 luglio 2025, es. 2).