# Domande Bioinformatica

### Descrivere l'algoritmo bit-parallel:
Problema: pattern matching:
**input:** testo $T$, pattern $P$, alfabeto $\Sigma$. $n=|T|, m=|P|$.
**soluzione:** trovare gli $i$ tali che $T[i:i+m-1]=P$

L'algortimo bit-parallel: è un algoritmo semi-numerico la cui complessità è quadratica: $O(nm)$, ma sfrutta il fatto che su un numero fromato da più bit(generalmente 32 o 64) la cpu può agire in tempo constante. L'agoritmo lavora con operazione bit level.
- Costruisco la matrice $M[][]$ come $M[i][j] = 1$ se e solo se $P[:i]=T[j-i+1:j]$, $0$ altrimenti. Ossia vale uno se la sottostringa di lunghezza $i$ che termina in posizione $j$ del testo è uguale al prefisso di lunghezza $i$ del pattern.
- Per costruirla parto dai casi base: $M[0][.]=1, M[.][0]=0$
- Passo ricorsivo: $M[i][j]=1$ sse $M[i-1][j-1]=1 \wedge P[i] = T[j]$.
- Costruendo $M$ in questo modo non sto sfruttando il parallelismo sui bit.

Per sfruttare le operazioni bit-level rappresento ogni colonna della matrice $M$ tramite un singolo numero la cui rappresentazione binaria corrisponde ai valori della matrice $M$ in tale colonna.
È inoltre necessario mantenrere, $U[\sigma]$, un array di bit tale che $U[\sigma, x]=1$ sse $P[x]=\sigma$.
- Esempio di $U[]$ se $P=abra$:
- $U[a]=1001$
- $U[b]=0100$
- $U[c]=0010$

Comprimiamo $M$ in un array $C$ dove $C[i]$ corrisponde alla rappresentazione numerica della colonna $i$ in $M$ allora possiamo partire dalla colonna $0$ che sappiamo essere composta da tutti $0$ e passare dalla colonna $j$ alla colonna $j+1$ facendo:
1. right shift di $C[j-1]$
2. metto 1 in prima posizione.
3. faccio l'AND con $U[T[j]]$ per controllare che ci sia un match con il carattere $T[j]$

Supponendo di avere una word-size $w$ allora le 3 operazioni precedenti si riassumo in: $C[j]=((C[j-1]>>1)|(1<<(w-1)))\&U[T[j]]$.
Per sapere se ho un'occorrenza di $P$ in $T$ che termina in posizione $j$ basta controllare se il bit meno significativo di $C[j]$ vale $1$.

Tale algortimo smette però di funzionare se la lunghezza del pattern è maggiore della word-size ($m>w$). In tal caso devo svolgere lo stesso ragionamento sui $\lceil \frac{m}{w} \rceil$ blocchi necessari, ricordando però che per tutti i blocchi tranne il primo invece di inserire un $1$ in prima posizione bisogna inserire l'ultimo bit del blocco precedente.

### Descrivere l'algoritmo Karp-Rabin:
Problema: pattern matching:
**input:** testo $T$, pattern $P$, alfabeto $\Sigma$. $n=|T|, m=|P|$.
**soluzione:** trovare gli $i$ tali che $T[i:i+m-1]=P$

Definiamo la funzione $H$ per trovare la finger-print di una stringa (in questo caso binaria ma è generalizzabile) come $H(S)=\sum_{i=1}^{|S|}{2^{i-1}*H(S[i])}$.
È possibile utilizzare una sliding window di larghezza $m$ su $T$, infatti si può passare alla finestra successiva facendo: $H(T[i+1:i+m])=(H(T[i:i+m-1])-H(T[i]))/2+2^{m-1}*H(T[i+m])$.
Per sapere se la finestra corrente corrisponde ad un'occorrenza del pattern nel testo possiamo notare come: $T[i:i+m-1]=P \iff H(T[i:i+m-1])=H(P)$.

Per il momento l'algoritmo non è lineare, infatti il valore della finger-print può valere fino a $2^n-1$, possiamo assumere che effettuare operazoini su numeri grandi impiega un tempo logaritmico rispetto al numero stesso. Quindi effettuando $O(m)$ operazioni su numeri gradi fino a $2^n-1$ costa $O(nm)$.

Per ovviare parzialmente a questo problema possiamo intruddurre un modulo $M$, ed eseguire il procedimento spiegato precedentemente mantenendo in numeri modulo $M$. Utilizzando un modulo appropriato l'algoritmo diventa lineare rispetto alla lunghezza del testo, l'introduzione del modulo ha però reso l'algoritmo non deterministico. Infatti possono esistere falsi positivi: $x \equiv y (mod M)$ non implica $x=y$. Per diminuire esponenzialmente la probabilità di errore possiamo eseguire lo stesso procedimento con più moduli diversi, e mantere solo l'intersezione delle loro occorrenze, infatti basta che anche solo un modulo non giudichi una finestra uguale al pattern per essere sicuri che non sia un'occorenza (non esistono i falsi negativi: se $x = y$ allora $x \equiv y(mod M)$).
In conclusione scegliendo un numero piccolo e costante di moduli(se i moduli sono primi dimuiscono le collisioni) allora quasi sicuramente troveremo tutte le occorrenze di $P$ in $T$ in $O(n+m)$.
Una variazione del karp-rabin deterministico consistene nel controllare manualmente le candidate occorrenze trovate dall'algoritmo, in questo modo l'algoritmo diventa deterministico ma ha complessità, nel caso peggiore(sia $T$ e sia $P$ sono formate da molte occorrenze della stessa lettera ) $O(nm)$.
### Descrivere l'algoritmo lineare per calcolare la sottostringa più lunga di 2 stringhe
Problema: longest common substring
**input:** 2 stringhe $s$, $t$. $n=|s|=|t|$ ma generallizzabile a $|s|\neq|t|$.
**output:** stringa di lunghezza massima contenuta sia in $s$ sia in $t$.
**soluzione:** suffix-tree generalizzato.
Dando per note le nozioni di suffix-tree e della sua costruzione in tempo lineare rispetto alla stringa sul quale è costruito, definiamo un suffix-tree generalizzato come un suffix-tree costruito su un insieme di stringhe, e per ogni suffisso mantiene l'informazione riguardo a quale stringa appartiene.
Costruiamo un suffix-tree generalizzato su $s$ e $t$, una sottostringa può essere visto come un prefisso di un suffiso, allora per come è strutturato un suffix-tree una sottostringa corrisponde ad un percorso dalla radice ad un determinato nodo dell'albero. La sottostringa che stiamo cercando deve appartenere sia ad $s$ sia a $t$, ciò implica che deve essere il prefisso di almeno un suffisso di $s$ e di almeno un suffisso di $t$. Ma allora per richiedere che appartenga ad entrambe le stringhe possiamo controllare che nel sottoalbero del nodo in questione esista almeno una foglia che rappresenta un suffiso in $s$ ed una che rappresenta un suffisso in $t$.
Per riassumere stiamo cercando il nodo il cui percorso dalla radice al nodo stesso(misurato in termini di caratteri) è massimo, e nel suo sottoalbero devono essere presenti almeno una foglia relativa ad $s$ ed una relativa a $t$.
Per fare ciò, tramite una procedura bottom-up, possiamo partire dalle foglie e per ogni nodo mantenere 2 flag che memorizzano se è presente o meno in quel sottoalbero una foglia per ognuna delle 2 stringhe. Per calcolare i valori del flag $x$ di un nodo che non sia foglia basta fare l'or dei valori del flag $x$ sui suoi figli.
Detto ciò poi tramite una visita dell'albero si cerca il nodo il cui percorso dalla radice al nodo stesso(misurato in termini di caratteri) è massimo ed entrmabi i suoi flag sono true. La sottostringa sarà la concatenazione dei caratteri sul percorso dalla radice a tale nodo.
### Descrivere l'algoritmo per calcolare la sottostringa più lunga di 2 stringhe usando suffix-array
Dopo aver calcolato il suffix-array sulle 2 stringhe, il relativo array LCP e per ogni suffisso nel suffix-array a quale stringa appartiene; bisogna cercare i 2 suffissi consecutivi del suffix-array che non appartengono alla stessa stringa con LCP massimo. Nel caso in cui cercassi la sottostringa comune più lunga a $K$ stringhe allora, sempre dopo aver calcolato il suffix-array sulle 2 stringhe, il relativo array LCP e per ogni suffisso nel suffix-array a quale stringa appartiene; sono interessato il subarray che contiene almeno un suffisso di ognuna delle $K$ stringhe in modo che il minimo valore di LCP tra 2 coppie consecutive di suffissi nel subarray sia massimo.
### Descrivere l'algoritmo per fare RMQ su un array
**input:** array $A$
**query:** intevallo $(b,e)$
**risposta:** $min_{b \le i \le e}A[i]$
Bisogna riuscire ad ottenere una complessità temporale costante per ogni query senza avere una complessità quadratica di memoria/preprocessing. L'idea è calcolare per ogni indice $i$ il minimo di ogni subarray che inizia in $i$ con lunghezza una potenza di 2 : $D[x,h]=min_{x \le i < x+2^{h}}A[i]$.
Fatto ciò allora è possibile scomporre ogni query $(l,r)$:
- calcolo $h = \lfloor log_{2}{(r-l+1)} \rfloor$.
- $min_{l \le i \le r}A[i] = min(D[l,h],D[r-2^h+1,h])$
### Descrivere l'algoritmo per fare pattern matching con suffix-array:
Problema: pattern matching:
**input:** testo $M$, pattern $P$. $n=|M|, m=|P|$.
**soluzione:** trovare gli $i$ tali che $M[i:i+m-1]=P$
Prima considerazione: è sufficiente trovare la prima occorrenza del pattern nel testo, per ottenere le altre basta controllare le successive celle nell'array $LCP$ ed andare avanti fino a quando l'LCP tra 2 celle consecutive non diventa minore di $m$.
Prima soluzione: ricerca binaria del pattern nel suffix-array, complessità $O(mlogn)$, vogliamo abbassare la complessità a $O(m+logn)$.
#### Accelerante 1:
Se sto cercando il pattern nel suffix-array tra il suffisso $L$ ed il suffisso $R$, posso evitare di controllare i primi $LCP[L,R]$ in quanto saranno uguali per tutte le stringhe tra $L$ e $R$. **Problema:** conosciamo l'LCP solo di 2 celle consecutive.
#### Accelerante 2:
Definisco $l=LCP[L,P], r=LCP[R,P]$
Durante la ricerca binaria posso avere 3 casi:
- $l>r$:
- se $LCP[L,M]>l$ allora $L=M$
- se $LCP[L,M]<l$ allora $R=M, r=LCP[L,M]$
- se $LCP[L,M]=l$ confronto $P[l+1:]$ con $M[l+1:]$
- $l=r$:
- se $LCP[L,M]>l$ allora $L=M$
- se $LCP[M,R]>l$ allora $R=M$
- se $LCP[L,M]=LCP[M,R]=l$ confronto $P[l+1:]$ con $M[l+1:]$
- $l<r$: simmetrico al caso $l>m$

Facendo in questo modo in ogni iterazione della ricerca binaria l'unica parte che non ha costo in tempo costante è il confronto tra il pattern ed il testo. Possiamo però notare che durante tutto l'algoritmo ogni carattere del pattern risulterà in un match solo una volta, mentre il numero di mismatch è al più uguale al numero di iterazioni della ricerca binaria ($O(logn)$). In totale quindi l'algoritmo avrà complessità $O(logn+m)$. **Problema:** non abbiamo un modo efficiente per conoscere i valori di LCP di suffissi non consecutivi.
#### Accelerante 3:
Bisogna trovare un modo per calcolare $LCP(x,y)$ per i valori $L,M,R$ velocemente. L'osservazione chiave consiste nel notare che gli intervalli di una ricerca binaria sono fissati. All'iterazione $K$: $L=h\frac{n}{2^{k-1}}, R=(h+1)\frac{n}{2^{k-1}}$.
In tutte sono $O(n)$ intervalli(si possono pensare come i nodi di un albero binario completo con $n$ foglie). Per calcolare il generico $LCP[L1,R2]$ dove $(L1,R2)$ è l'unione delle due sue metà $(L1,R1)$$(L2,R2)$ possiamo utilizzare un approccio bottom-up dove partendo dagli intervalli più piccoli e risalendo possiamo comporre $LCP[L1,R2]$ come $min({LCP[L1,R1],LCP[L2,R2],LCP[R1,L2]})$, i primi 2 valori li avremo calcolati precedentemente mentre $LCP[R1,L2]$ lo troviamo nell'array $LCP$ originale.
### Descrivere l'algortimo Needleman-Wunsch(allineamento globale):
**input:** 2 sequenze, funzione $d:(\Sigma \cup \{-\}) \times (\Sigma \cup \{-\}) \to \mathbb{R}$
**funzione obiettivo:** {insieme sol. ammissibili} $\to \mathbb{R}$
Date 2 sequenze vogliamo capire quanto sono simili, l'allineamento consiste nell'inserimento di vari(eventualmente 0) indel all'interno delle due sequenze in modo da renderle della stessa lunghezza(è vietato inserire un indel nella stessa posizione in entrambe le stringhe), per ogni coppia di caratteri sappiamo quale è il loro score, dobbiamo quindi trovare l'allineamento che produce lo score massimo. Lo score di un allineamento di 2 stringhe corrisponde alla somma degli score delle singole coppie di caratteri nella stessa posizione.
**Algoritmo:** Si tratta di una programmazione dinamica, è dunque necessario individuare quale è l'ultima componente che possiamo aggiungere.
**Passo ricorsivo:** Supponiamo che le sequenze si chiamino $S$ e $T$ e che abbiamo già trovato la soluzione ottimale per le combinazioni di prefissi $S_1$, ..., $S_{i-1}$ e $T_1$, ..., $T_{j-1}$. Definiamo $all[i][j]$ come score migliore per allineare i prefissi $S_i$ e $T_j$, per allineare i prefissi $S_i$ e $T_j$ abbiamo solo 3 possibilità:
- Inserire $S[i]$ e $T[j]$.
- Inserire $S[i]$ e un indel.
- Inserire un indel e $T[j]$.
Scegliamo l'opzione con uno score migliore, :
$all[i][j] =max\begin{cases} all[i-1][j-1] + d(s[i], t[j]) \\ all[i-1][j] + d(s[i], -) \\ all[i][j-1] + d(-,t[j]) \end{cases}$

**Casi base:**
- $all[0][0] = 0$
- $all[i][0] = \Sigma_{x=1}^{i}d(S[x],-)$
- $all[0][j] = \Sigma_{x=1}^{j}d(T[x],-)$

**Complesità:** supponendo $n=|S|, m=|T|$, esistono $\Theta(nm)$ stati ognuno computabile in tempo costante tramite un algoritmo bottom-up, la complessità in spazio e tempo risulta quindi $\Theta(nm)$.
### Descrivere l'algoritmo di Smith-Waterman(allineamento locale):
**input:** 2 sequenze, funzione $d:(\Sigma \cup \{-\}) \times (\Sigma \cup \{-\}) \to \mathbb{R}$
**funzione obiettivo:** {insieme sol. ammissibili} $\to \mathbb{R}$
Date 2 sequenze $S$ e $T$ vogliamo individuare la sottostringa $S1$ di $S$ e $T1$ di $T$ tali che l'allinamento globale tra $S1$ e $T1$ sia massimo
**Algoritmo:** Si tratta di una programmazione dinamica, è dunque necessario individuare quale è l'ultima componente che possiamo aggiungere.
**Passo ricorsivo:** Supponiamo che abbiamo già trovato la soluzione ottimale per le combinazioni di prefissi $S_1$, ..., $S_{i-1}$ e $T_1$, ..., $T_{j-1}$. Definiamo $all[i][j]$ come score migliore allineamento locale per i prefissi $S_i$ e $T_j$, per allineare i prefissi $S_i$ e $T_j$ abbiamo solo 4 possibilità:
- Inserire $S[i]$ e $T[j]$.
- Inserire $S[i]$ e un indel.
- Inserire un indel e $T[j]$.
- L'allineamento locale dei 2 prefissi corrisponde a 2 sottostringhe vuote.
Scegliamo l'opzione con uno score migliore, :
$all[i][j] =max\begin{cases} all[i-1][j-1] + d(s[i], t[j]) \\ all[i-1][j] + d(s[i], -) \\ all[i][j-1] + d(-,t[j]) \\ 0\end{cases}$

**Casi base:**
- $all[i][j] = 0$ se $i*j=0$

**Complesità:** supponendo $n=|S|, m=|T|$, esistono $\Theta(nm)$ stati ognuno computabile in tempo costante tramite un algoritmo bottom-up, la complessità in spazio e tempo risulta quindi $\Theta(nm)$.
### Descrivere l'algoritmo per allineamento con gap:
**input:** 2 sequenze, funzione $d:(\Sigma \cup \{-\}) \times (\Sigma \cup \{-\}) \to \mathbb{R}$, $f: \mathbb{N} \to \mathbb{R}$
**funzione obiettivo:** {insieme sol. ammissibili} $\to \mathbb{R}$
Il problema è molto simile a quello dell'allineamento globale, anche qui abbiamo le due sequenze $S$ e $T$ da allineare, ma varia il costo di inserimento di indel consecutivi nella stessa stringa. In particolare abbiamo una generica funzione di costo $f: \mathbb{N} \to \mathbb{R}$ tale che:
- $\frac{\partial f}{\partial x} > 0$
- $\frac{\partial ^ 2f}{\partial x^2} \le 0$.

Come per l'allineamento globale cerchiamo di sfruttare la programmazione dinamica:
**Passo ricorsivo:** A differenza dell'allineamento globale consideriamo una serie di indel consecutivi(gap) come un'unica componente. Supponiamo di aver già trovato la soluzione ottimale per le combinazioni di prefissi $S_1$, ..., $S_{i-1}$ e $T_1$, ..., $T_{j-1}$. Definiamo $all[i][j]$ come score migliore per allineare i prefissi $S_i$ e $T_j$, per allineare i prefissi $S_i$ e $T_j$ abbiamo solo 3 possibilità:
- Inserire $S[i]$ e $T[j]$.
- Inserire un gap di lunghezza $l$ in $S$
- Inserire un gap di lunghezza $l$ in $T$

Scegliamo l'opzione con uno score migliore, :
$all[i][j] =max\begin{cases} all[i-1][j-1] + d(s[i], t[j]) \\ all[i-l][j] - f(l) \forall l \in \{1,..,i\} \\ all[i][j-l] - f(l) \forall l \in \{1,..,j\} \end{cases}$
**Casi base:**
- $all[0][0] = 0$
- $all[i][0] = -f(i)$
- $all[0][j] = -f(j)$

**Complessità:** Definendo $n=|S|, m=|T|$, per ogni cella $(i,j)$ abbiamo costo $O(i+j)$, in totale: $O(\Sigma_{i \le n} \Sigma_{j \le m}(i+j))$=$O(\Sigma_{i \le n} \Sigma_{j \le m}i+\Sigma_{i \le n} \Sigma_{j \le m}j)$=$O(m\Sigma_{i \le n}i+n\Sigma_{j \le m}m)$=$mO(n^2)+nO(m^2)$=$O(mn(n+m))$

### Descrivere l'algoritmo per allineamento con gap affine:
Nel caso in cui la funzione di penalità fosse una retta:
- $\frac{\partial ^ 2f}{\partial x^2} = 0$.
- $m > 0$
- $q \ge 0$

Possiamo sfruttare il fatto che costo di aggiungere un indel non dipende dal numero di indel già inseriti prima di lui(se quello corrente non è il primo). Quindi nella programmazione dinamica posso considerare come ultima componente: non inserire un indel, aprire un gap in $S$ aprirlo in $T$, prolungarlo in $S$ o prolungarlo in $T$.Definisco allora, usando $P_0$ come costo di inizio del gap e $P_e$ come costo del suo prolungamento:
-$M[i][j]:$ allineamento ottimo su $S_i, T_j$.
-$E_1[i][j]:$ allineamento ottimo su $S_i, T_j$ con estensione di gap in $S$.
-$E_2[i][j]:$ allineamento ottimo su $S_i, T_j$ con estensione di gap in $T$.
-$N_1[i][j]:$ allineamento ottimo su $S_i, T_j$ con apertura di gap in $S$.
-$N_2[i][j]:$ allineamento ottimo su $S_i, T_j$ con apertura di gap in $T$.

E calcolo:
$M[i][j]=max\begin{cases} M[i-1][j-1]+d(S[i],T[j]) \\ E_1[i][j] \\ E_2[i][j] \\ N_1[i][j] \\ N_2[i][j] \end{cases}$
$E_1[i][j]=max\begin{cases} E_1[i][j-1]+P_e \\ N_1[i][j-1]+P_e\end{cases}$
$E_2[i][j]=max\begin{cases} E_2[i-1][j]+P_e \\ N_2[i-1][j]+P_e\end{cases}$
$N_1[i][j]=M[i][j-1]+P_0+P_e$
$N_2[i][j]=M[i-1][j]+P_0+P_e$

Trovo la risposta in $M[n][m]$.
**Complessità:** $O(nm)$

### Descrivere l'algoritmo per allineamento con banda
Partendo dall'algoritmo di Needleman-Wunsch cerchiamo di capire se è ottimizzabile nel caso in cui le stringhe $S$ e $T$ siano molto simili tra loro. La prima considerazione da fare è che: maggiore è il numero di indel nell'allineamento globale e minore è la somiglianza tra le 2 stringhe. Inoltre osservando la matrice per la programmazio dinamica notiamo come ogni volta che un indel è inserto corrisponde ad uno spostamento dalla cella corrente a quella sotto o quella a destra nella ricostruzione. Ma allora possiamo dire che se l'allineamento globale utilizza $K$ indel è possibile per ogni riga $i$ muoverci solo nelle celle a distanza minore o uguale di $K$ dalla cella $(i,i)$, infatti tutte le altre celle non sono raggiungibili usando al più $K$ indel.
Sappiamo anche che il numero minimo di indel $d$ corrisponde a $|S|-|T|$, quindi possiamo procedere per raddoppi, usando all'i-esima iterazione una banda larga $2(d+2^{i-1})+1$, fino a trovare una banda di larghezza sufficiente.
**Complessità:** Supponiamo che l'allineamento globale abbia $K$ indel, allora saranno servire $logK$ iterazioni com complessità: $O(N), O(2N), O(4N), .., O(KN)$ la cui somma risulta essere $O(KN)$ dove, per ottimizzare, $N$ corrisponde alla lunghezza della stringa più corta.

### Descrivere l'algoritmo di Gusfield per la filogenesi perfetta:

**Input:** Matrice binaria $M$:
- $M[S_{i}][C_{j}] = 1$ se la specie $S_{i}$ contiene il carattere $C_{j}$,
- $M[S_{i}][C_{j}] = 0$ altrimenti.

**Assunzioni:** Filogenesi perfetta:
- Ogni carattere $C_{j}$ è acquisito solo una volta nell'albero.
- Ogni carattere $C_{j}$ non può essere perso una volta ottenuto.

**Output:** Un albero che spiega $M$, dove gli archi indicano l'acquisizione di un carattere (detto anche **cambio di stato**), e ogni nodo foglia rappresenta una specie diversa.
**Osservazioni:**
Definiamo $S(C_{j}) = \{S_{i} | M[S_{i}][C_{j}] = 1 \}$
Siano $C_{i}$, $C_{j}$ due caratteri in una filogenesi perfetta, cosa posso dire di $S(C_{i})$ e $S(C_{j})$?
1. $S(C_{i}) \subseteq S(C_{j}) \longrightarrow C_{i}$ acquisito nel sotto albero di $C_{j}$
2. $S(C_{i}) \supseteq S(C_{j}) \longrightarrow C_{j}$ acquisito nel sotto albero di $C_{i}$
3. $S(C_{i}) \cap S(C_{j}) = \emptyset \longrightarrow$ Nessuno dei due caratteri è discendente dell'altro.

Come si possono sfruttare questi 3 casi? Utilizzando un algoritmo di ordinamento sui caratteri.

**Soluzione:** Algoritmo Gusfield - Lineare
1. Radix Sort delle colonne in ordine decrescente rispetto al numero di 1, quindi se $S(C_{i}) \subseteq S(C_{j})$, compare prima $C_{j}$.
2. Costruire l'albero una specie alla volta a partire dagli archi più vicini alla radice scorrendo la matrice riga per riga.

### Piccolo problema di Filogenesi a partire da caratteri (massima parsimonia)
**Input:** Matrice $M$ con $n$ specie $S$ e $m$ caratteri $C$, in $M[S_{i}][C_{j}]$ c'è lo stato di $S_{i}$ sul carattere $C_{j}$.
Topologia albero $T$, le cui foglie corrispondono a $S$.
$\forall c \in C$, un costo $w_{c}$ per ogni coppia di stato.
**Funzione obiettivo:**
$min \Sigma_{c \in C} \Sigma_{(x,y) \in E(T)} (w_{c}(\lambda_{c}(x), \lambda_{c}(y)))$, dove $E(T)$ è l'insieme degli archi di $T$.
**Sol. Ammissibili:** $\forall c \in C$, un'etichettatura $\lambda_{c}$ che assegna ad ogni nodo uno degli stati possibili per $C$.

#### Algoritmo Sankoff:

- $P[x,z]$ : soluzione ottimale del sottoalbero di $T$ con radice $x$, sotto la condizione che $x$ abbia etichetta $z$.
- $P[x,z] = 0$ se $x$ è una foglia con etichetta $= z$.
- $P[x,z] = + \infty$ se $x$ è una foglia con etichetta $\neq z$.
- $P[x,z] = \Sigma_{f \in F(x)} min_{s}\{w(z,s) + P[f,s]\}$, dove $F(x)$ è l'insieme dei figli di $x$ in $T$, se $x$ è un nodo interno.

**Soluzione ottimale:** $min_{s}\{P[r,s]\}$ dove $r$ è la radice di $T$.
Gli $s$ possibili sono i possibili stati dei nodi.
**Osservazione:** Ogni carattere è gestito separatamente (sono indipendenti), poi si sommano pesi minimi di ogni singolo carattere.
**Complessità (su singolo carattere):**
$k$ possibili stati per ogni carattere e $n$ specie
$O(nk^{2})$ tempo per costruire $P$
$O(nk)$ spazio per contenere $P$
$\Sigma_{x \in T} |F(x)| \leq n - 1 \longrightarrow O(n)$ archi in $T$.
#### Algoritmo Fitch:
**Assunzioni:** Solo caso non pesato, albero $T$ binario.
**Soluzione:** $S(x)$ insieme stati ottimali per nodo $x$. Nessuna restrizione su insieme degli stati.
- $S(x) = \lambda_{c}(x)$, se $x$ è una foglia.
- $S(x) = S(f_{l}) \cap S(f_{r})$, dove $f_{l}$ e $f_{r}$ sono figli di $x$ in $T$, se $S(f_{l}) \cap S(f_{r}) \neq \emptyset$.
- $S(x) = S(f_{l}) \cup S(f_{r})$, dove $f_{l}$ e $f_{r}$ sono figli di $x$ in $T$, se $S(f_{l}) \cap S(f_{r}) =\emptyset$.

**Extra:** Come estendere Fitch ad albero generico (non pesato)?
Scelgo l'etichetta che minimizza i cambi di stato, ovvero prendo l'elemento dei possibili stati che compare più volte.

#### Unificazione dei 2 algoritmi:
Fitch è una forma più semplice di Sankoff.
$S(x)$ : insieme degli stati $z$ tali che $P[x,z]$ è minimo.

### Filogenesi a partire dalle distanze:

#### Descrivere l'algoritmo che costruisce l'orologio molecolare a partire dalle distanze ultrametriche:

**Input:** Matrice di distanze tra le coppie di specie $D[s1, s2]$ con $(s1, s2) \in S \times S$
Funzione distanza:
$d : S \times S \longrightarrow \mathbb{R}^{+}$ con le seguenti proprietà:
1. $d(a,b) \leq d(a,c) + d(c,b), \forall a, b, c \in S$
2. $d(a,b) = 0 \iff a = b, \forall a, b \in S$
3. $d(a,b) = d(b, a), \forall a, b \in S$

**Assunzioni:**
$\forall x$ nodo dell'albero risultante, la distanza fra $x$ ed ogni sua foglia discendente è la stessa.
Si ottiene **Distanza ultrametrica** con le seguenti proprietà:
- Le 3 proprietà precedenti sulla funzione distanza
- $\forall a,b,c \in S, max\{d(a,b),d(a,c),d(c,b)\}$ è ottenuto da almeno 2 elementi dell'insieme.

**Problema:** Costruzione orologio molecolare.

**Algoritmo:**
1. Si prende il valore più piccolo della matrice $D[i,j]$.
2. Le due specie indicate dall'indice avranno un antenato in comune e la distanza di ognuna delle foglie da questo antenato sarà $\frac{D[i,j]}{2}$, quindi si aggiungono gli archi mancanti per rispettare le distanze.
3. Rimuovo uno tra i due indici utilizzati $i$ e $j$.
4. Se $D \neq \emptyset$ (son rimasti almeno due indici), torna al passo $1$.
5. L'albero ottenuto rappresenta l'orologio molecolare della filogenesi.

#### Descrivere l'algoritmo che costruisce l'albero a partire da distanze additive:

**Proprietà:**
Sia $T$ un albero binario senza radice e sia $D$ la matrice delle distanze associate a $T$.
Allora $D$ soddisfa la *Condizione dei 4 punti*:
1. $D[x,y] + D[v,w]$
2. $D[x,v] + D[y,w]$
3. $D[v,y] + D[w,x]$

Il massimo dei tre valori è ottenuto esattamente da due dei tre casi sopra.
Se $D$ rispetta la condizione dei 4 punti $\longrightarrow \exists$ un albero che soddisfa perfettamente $D$.

**Input:** Matrice di distanze tra le coppie di specie $D[s1, s2]$ con $(s1, s2) \in S \times S$ che soddisfa la *Condizione dei 4 punti*.
**Output:** Albero $T$ che rappresenta la filogenesi ottenuta a partire da $D$.
**Soluzione:**
1. Si prende tripla $x, y, z \in S$ con minimo sbilancio, dove lo sbilancio della tripla è indicato come $D[x,z] + D[y,z] - D[x,y]$ ed è noto che risulterà sempre $\geq 0$.
2. Si vuole ottenere uno sbilancio pari a 0, quindi si diminuiscono tutti gli archi incidenti ad una foglia di una quantità $\delta$ che viene calcolata come $\frac{D(x,z)+D(y,z)-D(x,y)}{2}$
3. Si aggiorna la matrice $D$ sottraendo $2\delta$ ad ogni elemento della matrice e cancellando da $D$ riga e colonna della $z$ della tripla ottenuta al passo **1.** in quanto il suo arco è stato azzerato in questo passo.
4. Se $D$ non contiene solo 2 elementi, si rinizia dal passo *1*.
5. Si costruisce l'albero applicando il processo inverso alla matrice (si riaggiungono i $\delta$ rimossi a partire dall'ultimo), prendendo gli elementi rimossi dalla matrice e inseriti nell'albero in modo che vengano rispettate le distanze (sempre a partire dall'ultimo).

### Filogenesi attraverso Clustering Gerarchico
**Input:** Insieme di punti (ogni specie rappresenta un singolo cluster).
**Soluzione:** Si prendono due cluster e si fondono in un unico cluster, si continua la procedura fino ad avere un unico cluster rimanente.
**Differenze fra procedure di clustering:**
1. Quali cluster fondere nell'iterazione corrente.
2. Dove posizionare il centro del nuovo cluster.

#### Descrivere algoritmo di clustering UPGMA(Unweighted Pair Group with Arithmetic Mean):

- $D(C_{1},C_{2}) \longleftarrow \frac{1}{|C_{1}||C_{2}|} \Sigma_{i \in C_{1}} \Sigma_{j \in C_{2}}D(i, j)$
- All'inizio $h = 0$ per ogni cluster/specie.
- Fondi i due cluster $C_{1},C_{2}$ con minimo $D(\cdot,\cdot)$ ottenendo $C$.
- Per ogni cluster $C^{*} \neq C, D(C, C^{*}) = \frac{1}{|C||C^{*}|} \Sigma_{i \in C} \Sigma_{j \in C^{*}}D(i, j)$
- $h(C) \longleftarrow \frac{D(C_{1},C_{2})}{2}$
- Arco $(C, C_{1})$ con etichetta $h(C) - h(C_{1})$
- Arco $(C, C_{2})$ con etichetta $h(C) - h(C_{2})$
- UPGMA produce **Distanza Ultrametrica**
- Cerca di fondere coppia di cluster più vicina (più semplice, ma non sempre ottima).

#### Descrivere l'algoritmo di clustering gerarchico di Neighbor Joining:
- Fonde coppia di cluster più vicina, ma più lontana dagli altri cluster (più sicuro rispetto a UPGMA).
- $D(C_{1},C_{2}) \longleftarrow \frac{1}{|C_{1}||C_{2}|} \Sigma_{i \in C_{1}} \Sigma_{j \in C_{2}} D(i,j)$.
- $u(C) \longleftarrow \frac{1}{num.cluster - 2} \Sigma_{C_{3}} D(C, C_{3})$.
- Fondi i due cluster $C_{1}, C_{2}$ con minimo $D(C_{1}, C_{2}) - u(C_{1}) - u(C_{2})$, ottenendo $C$.
- Per ogni cluster $C^{*} \neq C, D(C,C^{*}) = \frac{1}{|C||C^{*}|} \Sigma_{i \in C} \Sigma_{j \in C^{*}}D(i, j)$.
- Arco $(C, C_{1})$ con etichetta $\frac{D(C_{1}, C_{2}) + u(C_{1}) - u(C_{2})}{2}$.
- Arco $(C, C_{2})$ con etichetta $\frac{D(C_{1}, C_{2}) - u(C_{1}) + u(C_{2})}{2}$.
- Non produce distanza ultrametrica.

**Proprietà di consistenza:**
$lim_{n \rightarrow +\infty}$ dell'albero costruito da Neighbor Joining è quello corretto, dove $n$ è la lunghezza delle sequenze.

### Assemblaggio del genoma:

**Regola:** Suffisso di una read può essere prefisso di un'altra read: si tratta di un overlap
La differenza di una singola base all'interno dell'overlap può essere giustificata da:
- Errore di sequenziamento
- Organismo Diploide

#### Descrivere l'algoritmo che risolve il problema "Shortest Superstring":
**Input:** Insieme $R$ di stringhe (dette *read*)
**Soluzione ammissibile:** Stringa $g$ tale che $\forall r \in R, g$ è superstringa di $r$
**Funzione obiettivo:** $min |g|$ (per il principio di massima parsimonia)

**Soluzione:** Si costruisce grafo di overlap $G = (V, E)$, dove
- $V = R$
- $\forall (v_{1}, v_{2}) \in E$, l'arco ha come etichetta il prefisso di $v_{1}$ che non fa parte dell'overlap di $v_{1}$ con $v_{2}$.

Si pone una soglia di overlap, ovvero un numero minimo di caratteri di overlap per evitare overlap non rilevanti.
Si produce il cosiddetto String Graph, rimuovendo gli archi transitivi.
- La stringa $g$ rappresenta un cammino
- Ogni nodo è attraversato esattamente una volta

**Sol. ammissibile:** $\exists$ un cammino che rispetta tutte le condizioni? $\rightarrow$ Problema di esistenza di un cammino Hamiltoniano (Problema NP-Hard).

Se aggiungiamo anche le seguenti condizioni:
- $G = (V, E)$ grafo completo
- Somma delle lunghezze delle etichette degli archi è minima (sommato alla lunghezza dell'$r$ finale)

**Sol. ottima:** Riconducibile al $TSP$ (Traveling salesman problem).

**Input(TSP):** $G' = (V', E')$ orientato e completo, archi pesati $w:E' \longrightarrow \mathbb{Q}^{+}$
**Sol. ammissibili:** permutazione $\pi = < \pi_{1}, ..., \pi_{n}>$ di $V'$
**Funz. obiettivo:** $min\{w(\pi_{n}, \pi_{1}) + \Sigma_{i=1}^{n-1} w(\pi_{i}, \pi_{i+1})\}$

**Caratteristiche:**
- Problema NP-Completo, ma risolvibile in pratica
- Costo cammino = sommatoria dei pesi di tutti gli archi attraversati

**Da Shortest Superstring a TSP:**
Creiamo altri due nodi $s, t$ ed un insieme di archi $E_{s,t}$ tali che:
- $\forall v \in V, (s, v) \in E_{s,t}, w(s,v) = 0$
- $\forall v \in V, (v, t) \in E_{s,t}, w(v,t) = |v|$
- $(s,t),(t,s) \in E_{s,t}, w(s,t) = + \infty,w(t,s) = 0$

Considerando anche il fatto che $G'=(V',E')$ sia completo, otteniamo:
- $V' = V \cup \{s,t\}$
- $E' = E \cup E_{s,t} \cup \{v_{1},v_{2} \in V | (v_{1},v_{2}) \notin E\}$
- E poniamo $w(v_{1}, v_{2}) = + \infty$ $\forall v_{1},v_{2} \in V | (v_{1},v_{2}) \notin E$

#### Descrivere l'algoritmo SBH che utilizza Grafi di De Bruijin:
**Input:**
- $\forall k$-mero (sequenza di $k$ basi), si sa se appare nel genoma di riferimento, con $k$ fissato.

**Sol. ammissibile:** Genoma $g$ che rispetta la presenza dei $k$-meri
**Funzione obiettivo:** $min |g|$
**Procedura:**
- Ogni $k$-mero viene diviso in $(k-1)$-meri
- Si crea grafo $G=(V,E)$ dove
- $V$ è composto da $(k-1)$-meri presenti nel genoma
- $E$ è composto da $k$-meri presenti nel genoma (collega i due $(k-1)$-meri che lo compongono)

**Problema computazionale:** Visitare una sola volta tutti gli archi (ricerca *Cammino Euleriano*):
**Algoritmo:** Dando per noti il concetto di grafo euleriano, grafo semi-euleriano e i teoremi a riguardo, si eseguono i seguenti passaggi:
1. Costruisco un cammino $P_{1}$ da $s \in V$ a $t \in V$, dove $s$ è la partenza del cammino euleriano e $t$ è la destinazione.
2. Cerco, se esiste, un arco non ancora visitato in $P_{1}$ a partire da un nodo $y \in P_{1}$ e lo visito per ottenere un ciclo $C$ da $y$, aggiorno $P_{1}$ inserendo il ciclo prima del primo arco in $P_{1}$ che parte da $y$.
3. Se $P_{1}$ non attraversa tutti gli archi, torno al passo **2.**
4. Il percorso ottenuto costituisce un cammino euleriano e la stringa $g$ che rappresenta il cammino sarà la soluzione ottima dell'assemblaggio del genoma.

### Descrivere l'algoritmo di ricostruzione di aplotipi da pedigree:
**Problema:** Ricostruzione di aplotipi
**Input:** Pedigree $P$, $g_{i}[j]$ (il genotipo dell'individuo $i$ nel locus $j$)
**Assunzioni:**
- Non ci sono dati mancanti
- Non ci sono ricombinazioni
- Caso biallelico

**Soluzione:** Ricostruzione degli aplotipi (quale allele appartiene a quale genitore).

Definiamo le seguenti variabili:
- $g_{i}[j]$ : Genotipo dell'individuo $i$ nel locus $j$, vale $0$ o $1$ se omozigote, $2$ altrimenti (alleli indicati come coppia ordinata)
- $w_{i}[j]$ : $0$ se locus $j$ dell'individuo è omozigote, $1$ altrimenti.
- $h_{x, i}$ : Se $x$ è genitore di $i$ e $x$ passa il suo aplotipo paterno a $i$, allora $h_{x, i} = 0$, altrimenti $h_{x, i} = 1$
- $p_{i}[j]$ : Aplotipo paterno dell'individuo $i$ nel locus $j$

Aplotipo materno: Trovandoci in $\mathbb{Z}_{2}$, abbiamo che si definisce così:
- $w_{i}[j] = 0 \implies p_{i}[j]$
- $w_{i}[j] = 1 \implies 1 - p_{i}[j] = 1 + p_{i}[j]$

Il tutto è riassumibile in: $p_{i}[j] + w_{i}[j]$ .
Consideriamo le equazioni dell'ereditarietà di Mendel:
- $p$ padre, $m$ madre, $f$ figlio/a, $x$ genitore
- $h_{p, f} = 0 \implies p_{f}[j] = p_{p}[j]$
- $h_{p, f} = 1 \implies p_{f}[j] = p_{p}[j] + w_{p}[j]$
- $h_{m, f} = 0 \implies p_{f}[j] + w_{f}[j] = p_{m}[j]$
- $h_{m, f} = 1 \implies p_{f}[j] + w_{f}[j] = p_{m}[j] + w_{m}[j]$

Le due equazioni su $h_{p, f}$ si possono riscrivere: $p_{f}[j] = p_{p}[j] + w_{p}[j] * h_{p, f}$
Mentre le due equazioni su $h_{m, f}$ si possono riscrivere: $p_{f}[j] + w_{f}[j] = p_{m}[j] + w_{m}[j] * h_{m, f}$

Le due ultime equazioni si possono riassumere nuovamente per ottenere:
$p_{f}[j] + d_{x, f} = p_{x}[j] + w_{x}[j] * h_{x, f}$ dove $d_{p, f} = 0$ e $d_{m, f} = w_{f}[j]$ .
Quindi il sistema ottenuto avrà le seguenti equazioni:
- $p_{f}[j] + d_{x, f} = p_{x}[j] + w_{x}[j] * h_{x, f}$ $\forall(x, f)$ coppia genitore-figlio
- $d_{p, f} = 0$ $\forall(p, f)$ coppia padre-figlio
- $d_{m, f} = w_{f}$ $\forall(m, f)$ coppia madre-figlio
- $p_{i}[j] = g_{i}[j]$ se $g_{i}[j] \neq 2$
- $w_{i}[j] = 1$ se $g_{i}[j] = 2$
- $w_{i}[j] = 0$ se $g_{i}[j] \neq 2$

Incognite:
- $p_{x, f}$
- $h_{x, f}$

Si risolve tramite eliminazione Gaussiana del sistema di equazioni lineari.

### Descrivere la ricostruzione di aplotipi da singolo individuo:

**Input:** $r$ read di un individuo
**Sottoproblema:** Partizionare l'insieme dei read in due insiemi, uno per ogni aplotipo di provenienza
**Soluzione:** Viene creato il grafo dei conflitti $G = (V, E)$ associato alle read
- $V$ = Elenco dei read
- $E$ = Elenco delle coppie di read non compatibili (due read sono non compatibili se non possono appartenere allo stesso aplotipo)
- Una soluzione $(V1, V2)$ è ammissibile se è bipartizione di $V$ tale che $(V1, V2)$ siano le due parti di un grafo bipartito.
- Un grafo $G = (V, E)$ è bipartito se divido i suoi vertici in due parti $L$ e $R$ ed ogni arco di $G$ connette un vertice in $L$ ed uno in $R$.

**Problema**: Dato un grafo $G = (V, E)$ individuare il minimo insieme di vertici la cui rimozione rende il grafo bipartito.
Il problema è riformulabile come: rimuovere il minimo insieme di read tale che l'insieme rimanente provenga da due aplotipi.
**Soluzione:** Si utilizza il concetto di $MEC$ (Minimum Error Correction): numero minimo di caratteri da modificare, tale che le read modificate siano compatibili con il fatto di essere state estratte da due aplotipi.

**Output:** Aplotipi ottenuti una volta applicato il $MEC$.