Allineamento ottimo

Nel back trace posso percorrere percorsi diversi alternativi ma

tutti validi, questo quando riesco a ottenere lo stesso punteggio

provenendo da caselle diverse. Quindi posso avere una soluzione unica

o soluzioni multiple.

Algoritmo in forma di equazioni

F è la matrice della procedura da riempire.

Numeriamo le celle da 0. La cella (0,0) ha 0.

La cella ij generica si ottiene dalla selezione del max tre le 3 opzioni:

spostamento orizzontale/verticale per cui prendo la cella di

provenienza e ci sommo d ovvero penalità del gap, oppure

spostamento diagonale per cui sommo s che è lo score

corrispondente alla sostituzione/corrispondenza tra i due caratteri.

Esempio semplice

Algoritmo per l allineamento locale ed esempi

Nell’allineamento locale, parto da quello globale con la logica delle

varie opzioni tra cui scegliere il max, ma c’è una quarta opzione

rappresentata da 0.

Quindi nella matrice ci saranno valori tutti positivi/0.

Qui il punteggio dell’allineamento ottimo è dato dal valore più alto

nella matrice indipendentemente dalla posizione e sarà il punto di

partenza del traceback.

Come è stata definita la matrice di sostituzione

La BLOSUM (BLOcks SUbstitution Matrices) è una delle matrici di

sostituzione +usate. Riguarda le sequenze amminoacidiche, che

presentano 20 caratteri diversi, quindi è una 20x20.

Come sono stati definiti i punteggi per la matrice di sostituzione?

E’ stata presa una collezione di sequenze amminoacidiche

appartenenti alla stessa famiglia, quindi simili, sono state allineate

in modo multiplo, sono stati estratti i blocchi, cioè le parti dell

allineamento prive di gap cioè le parti più conservate. Come è stato

fatto questo allineamento, se farlo ci serve per definire la matrice di

sostituzione? E’ stato usato uno schema grossolano, match=1 e

mismatch=0, per trovare questi blocchi.

Esempio: allineamento multiplo con 6 sequenze e 4 colonne. Usiamo un

alfabeto semplificato di 3 caratteri, A B C. Questo è uno dei tanti blocchi

estratti dal multiallineamento. Quello che si fa sul singolo blocco per

definire la blosum è stato contare le occorrenze dei vari caratteri per

ottenere le loro frequenze.

Ci sono 6 sequ per 4 posizioni (= colonne), 6*4=24 caratteri tot nel

blocco. Conto l occorrenza di ciascun carattere rispetto a tutto il

blocco, es B=4, e calcolo la frequenza di occorrenza di quascun

carattere sull intero blocco, es fB=4/24.

Poi bisogna contare la frequenza di occorrenza delle coppie di

caratteri intesi all interno della stessa colonna/posizione,

guardando tutte le colonne. In tot le coppie da osservare sono 4*(6 su

2)=60, ovvero abbiamo 4 colonne possibili e (6 su 2) =6!/(2!*4!) insiemi

da 2 possibili caratteri per ogni colonna. E poi bisogna contarle. Queste

sono le frequenze osservate delle coppie.

Le frequenze attese delle coppie sono date da: se i caratteri nella

coppia considerata sono uguali allora = (frequ oss sing caratt) ,

2

se i caratteri nella coppia sono diversi allora = (frequ oss sing car

1)* (frequ oss sing car 2) *2.

Poi faccio 2*log (frequ oss coppie/freq attese coppie) che poi viene

2

arrotondato all intero più vicino.

Così ho ottenuto una matrice di sostituz. E’ stata definita a partire da

sequenze reali quindi toglie un po di arbitrarietà e rispetta la realtà

biologica. occorrenza del carattere nel blocco

frequenza osservata del singolo carattere= numero totale dicaratteri delblocco

occorrenza della coppialungo≤colonne

frequ oss della coppia dicaratteri= numero tot dicoppie da osservare del blocco

{ 2

f oss car car uguali

frequ attesa della coppiadi caratteri= 2∗f oss car 1∗f osscar 2 car diversi

( )

f oss coppia

valore nella matrice di sostituzione=2∗log per ogni coppia

2 f attesa coppia

In questo modo attribuisco un punteggio maggiore alle corrispondenze e

alle sostituzioni che in natura sono osservate +frequentemente, e che

quindi sono quelle meno gravi.

E’ una matrice simmetrica perché se nelle coppie scambiamo i

caratteri è la stessa cosa.

Gli score negativi corrisponderanno a sostituzioni poco osservate in

natura e quindi le penalizzerò di più e questo accade per

amminoacidi con caratteristiche chimico-fisiche diverse. Al

contrario premieremo con punteggi positivi amminoacidi con

proprietà simili, es con stssa carica es acido glu e acido asp.

Blosum è seguita da un numero x, es blosum62. Il numero è riferito

a una soglia di % di identità. Blosum62 o 85 vuol dire che ho escluso

nell insieme di sequenze da valutare quelle che hanno identità

soprasoglia data da quel numero, 62% o 85%. Se queste hanno

identità superiore a quella percentuale vengono contate con un'unica

sequenza, le facciamo pesare meno. Se la % di soglia è alta, vuol dire

che ho tenuto anche seq molto simili, allora è adatta ad allineare