applicazioni biologiche per alberi dei suffissi

Le sequenze di informazioni biologiche sono comunemente archiviate in locazioni contigue della memoria del computer. Questo metodo di stoccaggio non risulta efficiente per un certo numero di applicazioni. Il nodo del problema sta nel fatto che i dati archiviati in modo sequenziale devono in buona sostanza essere processate in modo sequenziale.

Invece, spesso, il valore informativo all’interno della sequenza risulta essere caratterizzato dalla presenza di certe sottosequenze, ripetute o meno; come può capitare in sequenze di DNA codificanti per una determinata proteina. Risulta ovvio come il dover necessariamente accedere sequenzialmente ad ogni stringa dati - quando si cerca una determinata sottosequenza all’interno di un intero dataset, risulta inefficace e dispersivo; specie se il volume di dati da analizzare cresce in modo esponenziale come è avvenuto negli ultimi anni con la genomica e la proteomica. Il tempo di accesso diventa il fattore limitante. Quello che allora serve è un sistema di indicizzazione delle sequenze efficiente. Un sistema che permetta di accedere ad una sequenza in termini di cosa contenga, senza dover specificare dove essa sia contenuta. L’albero dei suffissi.

Lo stesso Dan Gusfield, in un suo breve scritto “Suffix trees (and relatives) come of age in bioinformatics”, mette l’accento su quante possano essere le applicazioni in bioinformatica di questa struttura dati.

• All’atto in cui divenne disponibile l’intera sequenza genomica di due organismi filogeneticamente omologhi, una delle prime questioni che venne posta fu la necessità di compiere un allineamento genomico.

Esistono molti, sofisticati algoritmi adatti per l’allineamento di due sequenze, includendo i famosi metodi di Needleman & Wunsch e di Smith & Waterman. Essi funzionano bene quando si tratta di allineare sequenze relativamente brevi (singole proteine, per esempio), ma spesso risultano o troppo lenti o necessitano di troppa memoria quando si tratta di allineare sequenze di milioni di nucleotidi.

Gli algoritmi standard ottimali di programmazione dinamica hanno un funzionamento con tempo e spazio proporzionale a O(n^2); invece tecniche euristiche come Fasta e Blast sono mediamente più veloci, ma sono anch’esse basate su una strategia “match and extend”, dove la seconda parte prende anch’essa un tempo O(n^2). Risulta quindi conveniente utilizzare una struttura come l’albero dei suffissi, che risulta in tali situazioni molto più efficace.

Vedremo poco più avanti come questo problema sia affrontato da due software, il MUMmer e il MGA, quali siano i diversi approcci e a quali risultati giungono.

 

¨ Una seconda applicazione molto interessante degli alberi dei suffissi è quella di individuare una eventuale contaminazione del DNA.

Il problema che si pone è meno banale di quanto si creda, se si pensa a quante possano essere le fonti di contaminazione all’atto di sequenziare (il classico problema dell’individuazione del DNA di un dinosauro). Generalizzando il problema, si tratta di riuscire confrontare due sequenze, e distinguere all’interno della prima sequenza la presenza di possibili sottostringhe della seconda.

Per risolvere efficacemente la questione, si può optare per costruire un albero dei suffissi generalizzato contenente le sequenze S1 (quella del presunto dinosauro) e la sequenza S2 (quella dell’elemento contaminante; il DNA del tecnico che ha lavorato sui dati, per esempio). Si marcano quindi i nodi interni che presentano nel relativo sottoalbero sia suffissi di S1 che di S2, ed infine si selezionano, tra questi, i nodi che presentano una profondità di stringa superiore ad una determinata soglia.

 

¨ Strutture ripetitive in sequenze biologiche. E’ noto che, specialmente per gli eucarioti, sono state individuate migliaia di famiglie di sequenze ripetitive di DNA.

Esse giocano un ruolo fondamentale per alcune funzioni biologiche, e per l’interesse che generano nello studio dell’evoluzione. Usualmente si distinguono tre strutture ripetitive: ripetizioni locali, ripetizioni singole (le cui funzioni sono meno chiare), ripetizioni complesse. Un esempio di architettura biologica molto importante e strutturate come ripetizioni locali sono le forcine (hairpin) che hanno una tipica struttura palindrome, o anche i siti di taglio degli enzimi di restrizione. Una palindrome è una stringa dati che può essere letta ugualmente in avanti o indietro. Strutture palindrome sono comuni nelle sequenze di DNA; sequenze di DNA sono palindrome complementari, ove A-T e C-G sono complementi, se ogni carattere in metà della stringa è cambiato con il suo carattere complementare, per esempio: AGCTCGCGAGCT.

Il problema dell’individuazione in tempo lineare di tutte le “maximal repeats” è risolvibile proprio con gli alberi dei suffissi.

¨ Altre applicazioni citate in rete sono il “Circular DNA Sequences Problems”. Ovvero, data una sequenza circolare S di lunghezza n è definita come una sequenza nella quale il carattere n è considerato precedente al carattere 1.

I caratteri nella sequenza sono numerati sequenzialmente da 1 ad n, partendo da un punto arbitrario di S. Date due sequenze della medesima lunghezza, un albero dei suffissi può essere usata per compararle, per determinare se sono uguali, in tempo lineare. Si può operare tagliando la prima sequenza circolare S₁ in un punto arbitrario e quindi ottenere una sequenza lineare L₁. Duplicando L₁, si crea la sequenza L₁L₁. A questo punto, si costruisce l’albero dei suffissi T₁ per L₁L_1.

Quindi si attraversa T₁ secondo la regola per cui, ad ogni nodo, l’attraversamento segue l’arco il cui primo carattere è lessicalmente il più piccolo di tutti i primi caratteri dei vari archi del nodo. Il percorso continua finchè il path P₁ attraversato ha una profondità di sequenza n.

Dopo di che si ripete l’operazione per la sequenza S₂ fino a raggiungere il path P₂. Infine si comparano P₁ and P₂ per verificare la loro eventuali uguaglianza.

 

¨ Il problema del “The k-mismatch (error)”, che tratta la ricerca di sequenze con errori. In special modo, ci si riferisce al match di sequenze con un dato (k) numero di errori.

Per esempio, dato un set di stringhe, si cerchino tutte le occorrenze del pattern P, tipo sequenza aminoacidica, permettendo un solo errore. P può presentarsi differentemente come P’ in ognuna delle stringhe, seguendo una dei tre possibili errori: inserzione, cancellazione, o sostituzione. Per risolvere questo problema, abbiamo bisogno di generare ogni possibile stringa P’ che può essere derivata da P cambiando un solo carattere. Si costruisce quindi l’albero dei suffissi generalizzato contenente la sequenza proteica di base e tutte queste stringhe. Infine si attraversa l’albero per individuare tutte le locazioni di partenza di tutte le possibili occorrenze di P’. Questa ricerca può essere effettuata in tempo lineare ed è proporzionale alla lunghezza di P’.