2 Le matrici per il confronto tra sequenze

DI LEVENSHTEIN - ALGORITMO edit distance

La distanza di Levenshtein, o edit distance, è una misura per la differenza fra due stringhe. La distanza di Levenshtein tra due stringhe A e B è il numero minimo di modifiche elementari che consentono di trasformare la A nella B. Per modifica elementare si intende la cancellazione di un carattere, la sostituzione di un carattere con un altro, o l'inserimento di un carattere.

Per esempio, per trasformare la parola "bar" in "biro" occorrono due modifiche:

1. "bar" -> "bir" (sostituzione di 'a' con 'i')
2. "bir" -> "biro" (inserimento di 'o')

Non è possibile trasformare la prima parola nella seconda con meno di due modifiche, quindi la distanza di Levenshtein fra "bar" e "biro" è 2.

Vediamo quest'altro esempio:

• Specie A: A W T V A S A V R T S IY A
• Specie B: A T V A A V R T S I A L Y
• Specie C: A

TVA AVTS IL'edit-distance è adatta nel caso degli allineamenti globali. Per l'edit distance deve valere la disuguaglianza triangolare. Se ho x, y e z e l'evento di mutazione da x a y ha un costo > dell'evento di mutazione x->z + z->y allora ogni volta che devo sostituire x con y devo effettuare due sostituzioni prima con z e poi con y perché al fine del punteggio finale "costano" meno. L'edit distance, infatti, prevede che si devono minimizzare i costi di eventi di mutazioni per passare da una sequenza all'altra. Prevale il concetto che l'evoluzione deve "risparmiare". Quindi, facendo riferimento all'esempio, da A si passa a B per mezzo di 2 mutazioni e da B si passa a C per mezzo di 1 mutazione. Quindi sommando 2 mutazioni + 1 mutazione otteniamo tre mutazioni che si sono susseguite nel corso dell'evoluzione per passare dalla sequenza A a quella C. Immaginiamo di passare da A a C

direttamente e poi da C a B. La trasformazione di A direttamente in C è resa possibile da 3 mutazioni; poi la trasformazione di C in B è resa possibile da 1 mutazione. Quindi 3 mutazioni + 1 mutazione = 4. Prima il punteggio era 2; ora è 4. Dovendo essere fedeli alla regola secondo la quale l'evoluzione deve risparmiare, prendiamo come vero il seguente passaggio A → B → C. Quindi la edit distance è pari a 2.

Quindi possiamo definire la Edit-distance come il numero minimo di editing (inserzione, delezione e sostituzione) necessarie per trasformare la prima sequenza nella seconda.

Può succedere che in un determinato sito di una sequenza avviene una sostituzione di un nucleotide con un altro nucleotide e dopo molti anni avviene nuovamente una sostituzione in quello stesso sito del "nuovo" nucleotide con quello che era presente originariamente. Oppure possono verificarsi retromutazioni (cioè un determinato fenotipo scompare a causa di una mutazione,

ma poi ricompare a causa di un’altramutazione che in questo caso si dice, appunto, retromutazione). In questi casi il numero di sostituzioni che viene osservato tra una coppia di sequenze è inferiore rispetto al numero di sostituzioni che effettivamente hanno avuto luogo. Quindi la edit distance non sempre coincide con la vera distanza tra due sequenze.

L’OROLOGIO MOLECOLARE DI ZUCKERKANDL E PAULING

Secondo Zuckerkandl e Pauling alcune sostituzioni amminoacidiche in alcune proteine avvengono a ritmo costante. Se questa ipotesi fosse corretta, essa costituirebbe un’importante strumento di indagine nello studio dell’evoluzione, poiché renderebbe possibile stimare l’epoca in cui è avvenuta la separazione delle linee filogenetiche di due gruppi ricorrendo semplicemente alla misura del numero delle sostituzioni (e quindi alla misura della edit distance) nella sequenza amminoacidica delle loro proteine. Per esempio, se si confronta la composizione in

aminoacidi dell'emoglobina di taxa diversi, il numero di differenze amminoacidiche fra due taxa qualunque deve essere proporzionale al tempo della loro divergenza se le differenze si sono accumulate a un ritmo costante. Quanto più numerose sono le differenze nelle sequenze amminoacidiche, tanto più lontana nel tempo è l'epoca della separazione dei due taxa. Questa teoria prende il nome di ipotesi dell'orologio molecolare. La disponibilità di un numero sempre maggiore di sequenze e anche di vari genomi completi ha permesso di verificare che non esiste un orologio molecolare universale: in realtà ogni proteina e ogni gene ha una propria dinamica evolutiva e spesso si osservano accelerazioni e decelerazioni in questa dinamica evolutiva.

COME CALCOLARE LA SIMILARITÀ TRA DUE SEQUENZE

Prima di andare avanti RICORDA:

Similarità: è un aspetto quantitativo che indica un livello di somiglianza tra le sequenze

Omologia: è un

Un aspetto qualitativo che riguarda più propriamente la funzione delle sequenze e indica un'origine filogenetica comune. Ci sono due tipi di omologia: ortologia e paralogia. Per comprendere la differenza tra geni ortologhi e paraloghi partiamo con il presupposto secondo il quale il processo chiamato duplicazione genica porta alla formazione di copie di un determinato gene all'interno di un determinato genoma. Le copie dei geni che si formano con questo processo hanno sequenza nucleotidica simile (o in alcuni casi identica) alla sequenza del gene genitore. Alla base della duplicazione genica c'è il meccanismo del crossing-over diseguale, derivante da piccoli errori d'appaiamento dei cromosomi omologhi durante la meiosi. Le copie multiple di un gene possono subire diverse mutazioni le quali possono non alterare il fenotipo dell'individuo. Oppure può succedere che le copie multiple di un determinato gene accumulano tante mutazioni che portano alla loro inattivazione.

In altri casi può succedere che queste mutazioni generano nuovi geni diversi da quello originario. I geni così generati (evoluzione divergente) sono detti geni paraloghi. Ad esempio, i geni umani delle globine alfa e beta derivano da un unico gene ancestrale che ha subito duplicazione genica. I geni paraloghi si distinguono da quelli ortologhi, che sono geni omologhi presenti in specie diverse ma correlati. I geni ortologhi codificano per proteine che hanno funzione simile. I geni ortologhi si generano non per eventi di duplicazione genica, ma si generano in seguito a eventi di speciazione (separazione della specie). La similarità tra due sequenze è generalmente dovuta ad una origine evolutiva comune, per cui molto spesso i termini similarità e omologia si confondono. Quando non si è certi di una origine comune si dovrebbe parlare di similarità. Analogia: strutture con funzione simile, ma che si sono evolute indipendentemente. Per il DNA non hamolto senso parlare di residui simili ed in genere si preferisce fare riferimento all'identità, perché l'alfabeto del DNA è troppo semplice (solo 4 lettere) per consentire sfumature. Quando due sequenze (sia se si tratti di sequenze nucleotidiche che di sequenze amminoacidiche) vengono confrontate attraverso un allineamento, è sempre possibile misurare la loro percentuale di identità, un parametro quantitativo che esprime il rapporto, espresso in percentuale, tra il numero di residui identici nelle due sequenze rispetto al totale dei residui allineati. Se la percentuale di identità è minore o uguale al 50% (nel caso di sequenze nucleotidiche) le sequenze sono evolutivamente NON correlate. Nel caso di sequenze amminoacidiche, esse sono evolutivamente NON correlate se la percentuale di identità è minore o uguale al 20%. Se la percentuale di identità ha un valore altissimo (es. 95%), si può affermare con buonaidentici. Un modo comune per rappresentare l'allineamento di sequenze di DNA è utilizzare il tag

 per mantenere la formattazione del testo. Inoltre, è possibile utilizzare il tag  per evidenziare le parole chiave come "omologhe" e "identità". Ecco come potrebbe apparire il testo formattato:

probabilità che le sequenze considerate sono omologhe. In alcuni casi le sequenze svolgono funzioni simili, ma non sono omologhe. Questo accade quando le sequenze sono sottoposte a pressioni che le indirizzano a svolgere la medesima funzione. Si parla, in questo caso, di evoluzione convergente od omoplasia. In questo caso, quindi, la percentuale di identità potrebbe essere alta ma i geni non sono omologhi. Anche nel caso in cui sia avvenuto un trasferimento orizzontale di materiale genetico, si può avere un valore elevato della percentuale di identità ma i geni non sono omologhi. La trasmissione orizzontale prevede che parte del materiale genetico di un organismo appartenente a una data specie viene trasferito, solitamente attraverso un vettore virale, a una specie differente. Si formano, così, geni xenologhi. Quindi per l'allineamento di sequenze di DNA si preferisce un metodo che indichi se i due residui di due sequenze allineate siano identici o non identici.
Identici come fa il metodo delle matrici a punti.

DELLE MATRICI A PUNTI (DOT PLOT O DOT-METODO MATRIX)

Un sistema relativamente semplice che è capace di identificare le zone di somiglianza locale tra due sequenze è il metodo detto matrice a punti (o dot plot o dot matrix). Di seguito vengono riportati alcuni esempi per comprendere come funziona questo metodo.

ESEMPIO 1

Confrontiamo la stringa LABIOINFORMATICAEBELLAEUTILE con se stessa. Scriviamo una stringa sull'asse delle X e una sull'asse delle Y e tracciamo tante righe e tante colonne quanti sono i simboli delle stringhe. Quindi:

Poniamo una X nel punto in cui due caratteri coincidono. Si nota che questa semplice regola genera subito una mappa della posizione dei caratteri identici corrispondenti nelle due stringhe (in questo caso nella stessa stringa). Si noti anche la presenza di X sparse nell'area della matrice al di fuori della diagonale principale dovute alla presenza di lettere uguali in posizioni diverse.
della stringa.
ESEMPIO 2
Un esempio meno banale potrebbe essere rappresentato dal confronto tra le stringhe:

LA BIOINFORMATICA E' BELLA E UTILE
LA BIONFORMATICA UTILE E BELLA E'

Quindi si avrà la seguente tabella:
In questo caso si osserva che la diagonale principale non è continua (differentemente dal caso precedente) ma una parte è spezzettata in due piccole diagonali parallele tra loro e distanziate dalla diagonale principale. Anche in questo caso bisogna evidenziare il "rumore di fondo", cioè le X distribuite sul piano della matrice al di fuori delle diagonali e che deriva dal fatto che, dato un insieme finito di caratteri componenti le stringhe, è inevitabile osservare corrispondenze casuali di simboli.
>>LE DIAGONALI RAPPRESENTANO LE ZONE DI SOMIGLIANZA SIGNIFICATIVA<<
>>QUANDO LA DIAGONALE E' SPEZZETTATA VUOL DIRE CHE