Esempio 1: calcolo di un grafico di idropatia

Come primo esempio per valutare la complessità computazionale prenderemo in considerazione il calcolo di un grafico di idropatia.

Uno dei metodi più utilizzati per valutare le regioni polari o idrofobiche di una sequenza proteica, è quello di utilizzare una "scala", chimico-fisica o statistica. Questa scala assegna a ciascun residuo amminoacidico un valore, che rappresenta la propensione di tale residuo per una fase polare o apolare. Siccome il collasso idrofobico è ritenuto la causa principale del folding di una proteina, ci si può aspettare che un grafico, che assegni valori di idropatia ai vari residui lungo la catena possa essere particolarmente informativo. Per esempio possiamo aspettarci che regioni

• molto polari indichino zone di esposizione al solvente fisiologico (ritenuto fortemente polare),
• oppure per proteine che si inseriscono in una membrana lipidica, ci si aspetta che le regioni ad alta idrofobicità siano indicative delle zone che attraversano il doppio strato.

Nel corso del tempo un numero molto elevato di scale è stato derivato (per una lista parziale con relativi valori e referenze si veda [12]).

Se comunque si graficano direttamente i valori di una scala lungo la sequenza proteica non si ottiene di solito un grafico molto comprensibile. Ciò è dovuto al fatto che vi sono alte variabilità da posizione a posizione, e che inoltre il valore di ciascun residuo è indipendente da dove esso è locato all'interno della sequenza. Un modo molto pratico e utilizzato ampiamente in tutti i tipi di analisi di sequenze primarie, è quello di associare a ciascun residuo la media dei valori di tutti i primi vicini, definiti da una finestra (di solito simmetrica) centrata sul residuo da calcolare.

Figura: Scala di Kyte-Doolittle

Supponendo quindi di avere una scala di idropatia (ad esempio quella definita in figura ), i cui valori positivi indichino propensione ad una fase apolare, mentre valori negativi siano associati ad una tendenza a favorire ambienti polari, vogliamo valutare la media su una finestra mobile dell'intorno di ciascun residuo. Più formalmente, se $h(a)$ rappresenta il valore associato al residuo di tipo $a$, quello che vogliamo calcolare per ogni posizione $i$ della nostra sequenza è

$$< h(i) > =1/(2l+1)\sum_{k=-l}^{+l} h(a_i)$$ (5.1)

Dove con finestra si intende il valore $W=(2l+1)$, e $h(a_i)$ è il valore della scala associato al tipo di residuo in posizione $i$-ma.

È da notare che quando siamo agli estremi (per esempio con $i=0$, o $i=L-1$), l'equazione , non può essere calcolata, per cui la media agli estremi deve essere valutata in modo differente. La figura , riporta una possibile soluzione.

Figura: Funzione per il calcolo di un plot di idropatia

La domanda adesso diviene: qual'è la complessità computazionale asintotica nello spazio e nel tempo della funzione in figura (o la corrispondente equazione )?

Per quanto riguarda l'occupazione spaziale massima, si ha che:

• sequence ha dimensione della lunghezza della catena $L$
• av_val ha la stessa dimensione $L$ (vedi #(2))
• le altre variabili sono a dimensione costante (esempio $C$) e indipendenti dalla dimensione dei dati dell'input (sequenza)

Da cui si deduce che la funzione occupa

$$Comp_{spazio}=2L + C \Rightarrow Comp_{spazio}=O(L)$$

Considerando come si è detto in precedenza che ciascuna operazione elementare abbia lo stesso costo (costo = 1), allora la complessità nel tempo sarà:

• (1) e (1') vengono eseguite una volta sola ($t_1=O(1)$)
• (2) è una assegnazione proporzionale alla sequenza, per cui il tempo $t_2$ è proporzionale a $L$ ($t_2=O(L)$)
• il test (3) e le operazioni (4),(4'),(4") e (7) richiedono un tempo proporzionale a $L$ ($t_3=O(L)$)
• il test (5) e le operazioni (6) e (6'), richiedono un tempo proporzionale alla dimensione della finestra $W$ moltiplicata per la lunghezza della sequenza $L$ ($t_4=O(WL)$)

Da cui si ricava che il tempo richiesto per il calcolo diviene

$$T(L)= 2O(1)+5O(L)+3O(WL) = O(WL)$$

Dove se $W$ è costante (di solito è anche $<< L$) allora $\Rightarrow$

$$T(L)=O(L)$$