Allineamento globale $O(n)$ in spazio

A volte può essere utile utilizzare il minimo spazio possibile di memoria, se per esempio abbiamo a che fare con sequenze particolarmente lunghe. Ricordandoci che per ogni posizione della nostra matrice di score noi valutavamo per tutti i tipi di algoritmi di allineamento presentati sopra, soltanto 3 posizioni adiacienti, ossia:

a)

immediatamente sopra $\downarrow$,

b)

sopra a sinistra $\searrow$,

c)

al fianco sinistro $\rightarrow$

della posizione da calcolare. È chiaro che non necessitiamo dell'intera matrice di score per ottenere il punteggio di un allineamento ottimo, ma ci è sufficiente un vettore lungo come il numero di colonne e due variabili aggiuntive. L'algoritmo presentato in Figura , ne è una implementazione diretta. Se lo confrontiamo con il precedente di Figura , si nota che adesso la complessità computazionale nello spazio è stata ridotta da una matrice ad un vettore, mentre quella nel tempo rimane quadratica. Più in generale se le numghezze delle due sequenze sono comparabili e circa uguali a $n$, allora l'algoritmo di linear_cost ha una complessità computazionale $C_{space}=O(n)$ e $C_{time}=O(n^2)$. Se però abbiamo bisogno di rintracciare un allineamento espicito con il punteggio ottenuto, allora le cose si complicano, e la soluzione più semplice ci porta ad un aumento di complessità computazionale nel tempo da $O(n^2)$ a $O(n^3)$, se vogliamo mantenere lo spazio occupato lineare. Se infatti utilizziamo l'algoritmo riportato in Figura , vediamo che necessitiamo di un ciclo ($O(n)$) della funzione linear_cost che richiede $O(n^2)$ da cui abbiamo che la complessità nel tempo è cresciuta a $O(n^3)$. Abbiamo inoltre bisogno di due funzioni, che sono get_align_from_path e backrow. La prima come dice il nome ricostruisce l'allineamento scelto in base alla traiettoria (lista nel nostro caso) che indica le operazioni da compiere (colonna, diagonale o riga). La secoda, invecie ci serve per sapere da quale posizione ricavata dalla riga precedente (più in basso di uno) dobbiamo partire.

In pratica on3_linear_align, calcola tutti gli allineamenti (numero pari alla lunghezza della prima sequenza) che si ottengono allineando tutti i prefissi la prima sequenza contro la seconda. I prefissi partono dall'intera sequenza e poi scalano di un simbolo alla volta, così noi allineiamo l'intera sequenza, poi tutta meno l'ultimo simbolo, poi tutta meno gli utlimi due e così via fino all'esaurimento dalla prima sequenza. Ogni ciclo valutiamo i vettori con i punteggi e i l backtrace della prima sequenza contro la seconda, in modo da ricostruire riga per riga il percorso a ritroso che ci porta la sequenza di operazioni che determinano un allineamento con punteggio ottimo.

Figura: Calcolo dello score di un allineamento con occupazione $O(n)$

Figura: Calcolo di un allineamento globale in spazio $O(n)$ e tempo $O(n^3)$