Giovanni Paolella » 7.Allineamento di sequenze mediante matrici di punti

Allineamento

L’allineamento è un problema molto frequente, e che può essere affrontato in modi diversi. Gli allineamenti servono in situazioni molto varie come la comparazione di geni di identica funzione in organismi diversi (ortologhi), la ricerca di sequenze di DNA o proteine in banche dati, l’identificazione di frammenti contigui parzialmente sovrapposti nella procedura di assemblaggio di sequenze, e molte altre. Due esempi di allineamenti sono riportati nelle figure:

• due proteine ortologhe allineate con il programma FASTA (A)
• allineamento multiplo di globine di tipo diverso (B)

Esistono vari algoritmi di allineamento che risultano utili in situazioni differenti e che portano in genere a risultati anche notevolmente diversi. Per questo motivo è importante conoscere i principi su cui essi sono basati e le principali difficoltà derivanti dall’applicazione di algoritmi inadatti al problema da risolvere.

Un semplice algoritmo di allineamento

Due sequenze possono essere allineate in diversi modi; la figura ne mostra alcuni per le due sequenze proposte. Definiamo allineamento ottimale quello che rispetta al meglio alcuni criteri.

La ricerca dell’allineamento ottimale può essere effettuata se è definito:

• a) l’insieme di tutti gli allineamenti possibili
• b) il metodo per calcolare un punteggio, che sia rappresentativo della qualità di un dato allineamento.

Se questi due aspetti sono definiti in maniera chiara, il problema è facilmente risolto applicando il metodo b) a tutti gli allineamenti indicati in a) e scegliendo quello che dà il punteggio migliore.

In sintesi, il metodo proposto consiste nell’allineare una delle sequenze contro l’altra, in tutte le possibili posizioni, e, per ciascuna, valutare il grado di similarità, contando, ad esempio, il numero di residui identici.

Ricerca di siti di restrizione

La procedura descritta è simile a quella usata, nella lezione precedente, per il riconoscimento dei siti di restrizione. Anche in quel caso si allinea la sequenza del sito in ogni posizione e si determina il punteggio contando il numero di residui identici (vedi figura).

Il caso dei siti di restrizione è più semplice, perchè l’identità richiesta è in genere del 100%, dato che in presenza di anche una sola differenza il sito non sarebbe riconosciuto dall’enzima. Per questo motivo è possibile applicare alcuni miglioramenti per ottenere una esecuzione più veloce. Ad esempio, per ogni posizione provata, nel caso si trovi una differenza di appaiamento, il confronto potrebbe essere interrotto proseguire, infatti, porterebbe comunque ad un grado di identità inferiore al 100%.

Quanto è veloce un metodo di allineamento

E’ importante avere una idea della velocità di un metodo di allineamento, perchè si tratta di operazioni che, su dati di grandi dimensioni, possono facilmente portare a tempi di esecuzione di ore o giorni o, talvolta, ancora più lunghi.

Il numero di confronti effettuato è un buon metodo per valutare l’efficienza di un algoritmo, perchè, indipendentemente dalla velocità della macchina utilizzata, un numero di confronti maggiore richiederà sempre un tempo più lungo. Per confronto intendiamo la singola operazione di confrontare due residui per vedere se sono identici oppure no.

Nell’algoritmo descritto per i siti di restrizione, il numero di confronti richiesto è uguale al prodotto delle lunghezze delle due sequenze. L’ottimizzazione proposta riduce notevolmente questo numero: infatti, trattandosi di sequenze di DNA, in tre casi su quattro la prima base sarà diversa e sarà l’unica ad essere confrontata perchè il calcolo viene interrotto; solo in un caso su quattro le due basi saranno identiche e sarà necessario procedere al confronto della seconda base.

Il ragionamento si ripete identico per ciascuna delle basi del sito di restrizione. Il numero di confronti (nc) sarà di poco superiore al numero delle basi della sequenza più lunga:

nc = n+1/4n+1/16n + ……

Quanti confronti sono necessari per allineare due sequenze ?

Per un generico allineamento di due sequenze l’ottimizzazione descritta non può essere usata, perchè sarebbe individuato il solo allineamento superiore descritto in figura A. Per identificare l’altro, è necessario confrontare sempre tutte le basi, il che porta il numero di confronti nc a:

nc=m*n

Dove m e n sono le lunghezze delle due sequenze.

In realtà, il numero è più alto. Se guardiamo l’allineamento in alto in figura B, la seconda parte, che non appare identica, lo è se si confronta ciascuna base con quella precedente della sequenza inferiore, come indicato. Questo allineamento può essere indicato come riportato in basso introducendo un gap (-) nella sequenza inferiore, a significare che quella base è assente in seguito a mutazioni o errori di sequenziamento. Prevedere questa eventualità significa però aumentare il numero di confronti di un fattore n pari alla lunghezza della seconda sequenza (nc=m*n*n). Prevedere gap più lunghi o multipli porta ad ulteriori incrementi, con numeri che rapidamente diventano non gestibili, anche su computer di elevata potenza.

Matrici di punti

Un modo di risolvere il problema è di utilizzare per la comparazione una matrice bidimensionale, come riportato in prima figura, in cui le due sequenze sono scritte una in alto, da sinistra a destra, e l’altra a sinistra, dall’alto in basso. La matrice viene riempita confrontando ciascuna delle basi della sequenza in alto con la prima base della sequenza di sinistra, e inserendo nella casella corrispondente il simbolo * ogni volta che le due basi sono uguali. Si procede poi come indicato nel movie per generare la matrice completa.

In una matrice di questo tipo, sequenze identiche sui due assi, generano una linea definita da ‘*’ disposti in diagonale. Prova a cercare diagonali di similarita’ all’interno della matrice riportata in seconda figura. Controlla qui il risultato.

La diagonale trovata corrisponde all’allineamento con gap descritto nella pagina precedente. Nota che la linea di similarità si interrompe circa a metà e passa su una diagonale parallela, in corrispondenza del gap. Esercitati a vedere la corrispondenza tra l’allineamento e la diagonale.

Window di dimensioni diverse

L’identificazione della diagonale non è sempre agevole perchè il numero di caselle occupate è piuttosto elevato, come si osserva in figura A. L’effetto è dovuto al fatto che l’alfabeto costituito dalle basi del DNA è composto di sole quattro lettere (ACGT) e la probabilità che una data base sia identica alla corrispondente sull’altra sequenza è pari a 1/4. Questo porta a riempire in maniera casuale circa un quarto delle caselle.

Un modo di ampliare l’alfabeto consiste nel procedere al confronto di coppie di lettere su una sequenza con coppie di lettere sull’altra. In questo modo solo 1/16 delle caselle risulterà pieno in maniera casuale. Perchè?

E’ possibile usare anche gruppi di lettere (window) di dimensioni più grandi per ridurre ulteriormente l’effetto di background. Nota però che anche la diagonale si riduce anche se in maniera minore. Verifica nelle altre figure il riempimento della matrice per window di dimensioni diverse.

Confronto di una sequenza di DNA con se stessa

Nelle figure è rappresentato un confronto a matrice di una sequenza di DNA di circa 800 basi con se stessa, il confronto è stato eseguito mediante il programma dottup del package EMBOSS. In questo caso la similarità è indicata da punti. La linea di similarità, appena visibile in A, diviene progressivamente più evidente all’aumentare (da 1 a 6) della window a causa della riduzione del background. Nota le due piccole linee parallele ai due lati della diagonale. Cosa potrebbero essere?

Prova a generare matrici tu stesso seguendo le istruzioni indicate qui.

Mismatch e gap

Le differenze (mismatch) tra residui corrispondenti delle due sequenze vengono visualizzati come interruzioni della diagonale, mentre i gap vengono visualizzati come salti da una diagonale a una successiva. Nella figura è riportato un esempio in cui una inserzione nella sequenza di DNA riportata a sinistra genera un gap nell’allineamento intorno al nucleotide in posizione 400.

Duplicazioni

La presenza di tratti di diagonali parallele come quelle mostrate in figura indicano duplicazioni di sequenza: il segmento di sequenza compreso tra i residui 500 e 700 della sequenza di sinistra, è presente due volte nella sequenza in basso (tra 500 e 700 e tra 700 e 900).

Matrici in EMBOSS

Il package EMBOSS, introdotto nella lezione 5, contiene, tra i programmi dedicati all’allineamento di sequenze, un gruppo di programmi, mostrato in figura, per la generazione allineamenti mediante matrici di punti. Di questo gruppo fanno parte programmi come dottup, dotmatcher e polydot.