Esempio 2: calcolo della sottosequenza con somma massima

Esistono una varietà di metodi che assegnano un punteggio locale a ciascun elemento di una sequenza (sia proteica che nucleotidica) a cui si assegna un preciso significato. Per esempio, nel paragrafo precedente il valore assegnato ad un determinato residuo amminoacidico, rappresenta la sua propensione locale (secondo l'intorno) ad essere più o meno in una fase apolare, mentre nel caso di sequenze nucleotidiche esistono metodi che assegnano a ciascuna base un punteggio che rappresenta la probabilità di essere all'interno di una zona codificante.

Un interessante problema che emerge dal fatto di avere sequenze biologiche rappresentate da liste di numeri reali, è quello di trovare la sottosequenza con la massima somma ([15]). In modo più formale, se abbiamo una sequenza di numeri reali $A=[a_0,a_1,a_2,...a_N]$, il problema della massima sottosequenza è quello di determinare la sottosequenza $S=[a_s,a_{s+1},..a_{e}]$ tale per cui la somma degli elementi $a_s+a_{s+1}+ ... +a_{e}$ sia massima, ossia

$$S=\max_{0 \leq s \leq e < L} \sum_{k=s}^{e} a_k$$

Un primo metodo che può essere utilizzato per la soluzione del presente problema è l'algoritmo descritto in Figura . Questo approccio conduce alla soluzione corretta, come si può verificare eseguendo il codice, ma non è sicuramente la soluzione migliore. Con maxsum3, si ha infatti che per ogni posizione della sequenza (punto (1)), si riparte da capo a calcolare dall'inizio (punto (2)) la somma (thisSum), che in realtà viene valutata solo quando l'indice del secondo loop $j$, diviene maggiore o uguale all'indice corrente della sequenza (punto (3)).

Figura: maxsum3: Ricerca la sottosequenza di somma massima

Possiamo comunque calcolare la complessità computazionale dell'algoritmo esposto in Figura , ed è

$$Comp_{spazio}(maxsum3)= O(N)$$

dove con $N$ si é indicata la lunghezza della sequenza, (il calcolo si esegue considerando la massima occupazione durante l'esecuzione), mentre il tempo impiegato sarà

$$T_{maxsum3}(N)= punto(1)punto(2)punto(3) =O(N^3)$$

dove il tempo totale è calcolato come prodotto dei loops ((1),(2) e (3)) in quanto sono tutti e tre annidati.

Una maniera più "furba" per ottenere il medesimo risultato è mostrata in Figura . Come si può notare un ciclo è stato rimosso tenendo conto dell'inutilità evidenziata con maxsum3. Con maxsum2 per ogni posizione $i$ della sequenza, si calcola il nuovo segmento che puó ripartire da quella posizione e andare fino al termine della sequenza. Analogamente a quanto fatto sopra si può verificare che adesso

$$T_{maxsum2}(N)= punto(1)punto(2) =O(N^2)$$

mentre lo spazio occupato rimane il medesimo.

Figura: maxsum2: Ricerca la sottosequenza di somma massima

È possibile però fare ancora meglio! Esiste la possibilità infatti di risolvere il problema con un algoritmo il cui tempo di esecuzione sia lineare nella dimensione della sequenza (Figura ).

L'idea di base è la seguente: siccome siamo interessati solo a valori la cui somma siamo maggiore di $0$, implica che ci basta tenere traccia soltanto della migliore sottosequenza trovata da $0$ fino alla posizione $i$ della nostra sequenza, e considerare sottosequenze nuove solo se la loro somma è $> 0$ (#(2)). In questo caso caso, possiamo confrontarla alla migliore trovata fino a questo momento (#(3) ) e valutare se sia o meno il caso di tenere la nuova sequenza come la mogliore ("best"). Se invece, la somma (o il valore attuale) è $<0$, non interessa per nulla continuare a calcolare la somma attuale, e si procede ripertendo da $0$ (#(2)).

Come si può notare dal fatto che adesso esiste solo un ciclo (punto (1)), la complessità è

$$T_{maxsum1}(N)= punto(1) =O(N)$$

Questo paragrafo aveva lo scopo di mostrare l'affermazione fatta all'inizio di questo capitolo, per cui dato un problema, possono esistere numerose soluzioni non sempre equivalenti. In casi reali la scelta di un algoritmo errato può rendere il tempo di esecuzione inacettabile, e quindi trasformare il problema in non risolubile. Purtroppo esistono numerosi problemi, molti dei quali veramente rilevanti nell'ambito della bioinformatica, che non hanno una soluzione polinomiale, ossia il miglior algoritmo trovato richiede tempi di esecuzione esponenziali o fattoriali nel numero dei dati (es. $O(e^N)$ o $O(N!)$). Questi problemi vengono trattati utilizzando algoritmi aprossimati o stocastici (per una trattazione più dettagliata vedere [2], [4], [7], [9], [10], [11]).

Figura: maxsum1: Ricerca la sottosequenza di somma massima