Bioinformatica

ESEMPIO: S=HARFYAAQIVL T= VDMAAQIA

S T

A 2,6, 4,5,

7 8

F 4 -

H 1 -

I 9 7

L 11 -

Q 8 6

R 3 -

V 10 1

Y 5 -

Creo un vettore di spostamento

2-4= 2-5= 2=8= 6-4= 6-5= 6-8= 7-4= 7-5= 7-8= 9-7= 8-6 = 10-1=

in generale, l’offset può andare da 1-n a m-1 e se la k-tupla comune comincia nella posizione s[i] e

t[j], l’offset è dato da i-j

Ogni entry dell’offset vector riporta quindi quante volte si è verificato un dato offset. Il valore

massimo del vettore degli offset, determina l’allineamento ottimale

L’offset può essere visto come la diagonale di una matrice dotplot (metodo della diagonale)

FASTP unisce 2 o più k-tuple quando non sono molto lontane tra di loro sulla stessa

diagonale (lo spostamento non deve essere troppo grande), vengono individuate le

diagonali che presentano la più alta densità di k-tuple identiche. le k-tuple identiche

vengono assegnate alla medesima regione di similarità se sono separate da un

numero di residui inferiore ad un valore soglia prestabilito nell’algoritmo. In questo modo vengono

create delle regioni (ovvero allineamenti locali senza gap) a cui viene assegnato uno score a

seconda dei matches e dei mismatches in essi contenuti.

Vengono selezionate le prime 5 (10 in FASTA) regioni di similarità localizzate anche su differenti

diagonali (best initial regions) a cui si attribuiscono punteggi che vengono ricalcolati utilizzando

• per le sequenze nucleotidiche, un punteggio positivo per le identità e negativo per le

differenze

• per le sequenze proteiche, una matrice di sostituzione (ad esempio PAM250 o BLOSUM62)

Tra tutte le regioni diagonali di similarità quella che totalizza il massimo punteggio di similarità

viene definita regione primaria di similarità e il punteggio corrispondente é denominato init1 (initial

score)

I valori di init1 (uno per ogni sequenza del database) vengono utilizzati per stilare una graduatoria

delle migliori similarità trovate in banca dati e per decidere su quali e quante sequenze continuare

con le fasi successive dell’analisi.

La terza fase consiste nel generare regioni più estese di similarità. Questa ricongiunzione viene

effettuata se la penalità di ricongiungimento, proporzionale alla distanza tra le regioni di similarità,

é inferiore al contributo dato al punteggio di similarità dalla regione di similarità che viene

ricongiunta nell'allineamento.

Il punteggio di similarità relativo all'allineamento così determinato viene denominato punteggio initn

e viene usato per ordinare le sequenze della banca dati secondo il grado di similarità decrescente

con la sequenza sonda in esame.

Nella quarta ed ultima fase, l'allineamento precedentemente ottenuto viene ulteriormente

ottimizzato utilizzando una variante della procedura di allineamento locale esatto (Smith e

Waterman) all'interno di una banda diagonale di dimesioni predeterminate. Il punteggio di similarità

calcolato in quest'ultima fase viene denominato punteggio opt.

Limitatamente ai migliori allineamenti, FASTA fornisce anche lo score dell’allineamento usando

l’algoritmo di Smith e Waterman su tutto lo spazio della matrice di allineamento

Il programma FAST comprende anche un sistema per determinare la significatività di uno score.

Vengono determinati gli score di allineamento esatto tra una delle due sequenze e permutazioni

casuali dell’altra viene determinata la media e la deviazione standard della distribuzione (supposta

normale) dei punteggi derivati dagli allineamenti con sequenze scrambled viene calcolato un

paramentro di qualità per lo score opt. Per un buon allineamento opt~Z-score

l’analisi inizia con la ricerca di parole esatte: maggiore è il valore di ktup, più basso è il tempo di

esecuzione, ma maggiore il rischio di non rilevare similarità. il valore di ktup deve essere impostato

in modo da trovare il giusto compromesso tra accuratezza della ricerca e velocità di esecuzione.

BLAST algoritmo utilizza l’allineamento locale

BLAST è stato messo a punto da Karlin e Altschul (NCBI) a partire dal 1990.

Idea di fondo: l’allineamento ottimale tra due sequenze omologhe, anche se altamente divergenti,

ha un’alta probabilità di contenere una o più coppie di allineamenti caratterizzati da un punteggio di

similarità piuttosto elevato e tale da consentire una affidabile distinzione tra sequenze correlate da

relazione di omologia e sequenze non correlate. Allineamento locale è un approccio utile per

database di ricerca perché molte sequenze di query hanno domini, siti attivi o altri motivi che

hanno locale ma non una somiglianza globale. Inoltre, i database hanno in genere frammenti di

DNA e proteine sequenze che possono essere allineati localmente a una query.

Data una query sequence, BLAST ritorna tutti gli allineamenti tra la query e le sequenze del

database che hanno un punteggio superiore ad una certa soglia S. il parametro S può essere

scelto dall’utilizzatore (molti server hanno dei valori di default)

Fase 1: creazione e scoring di un elenco di parole (seeds)

Genero tutte le parole di una lunghezza definita W e le annilo

tutte con la query. Ovvero per ogni segmento lungo W (ad es.:

W=3-4) sulla sequenza query, si genera la lista di high-scoring

words è composta di w-mers che abbiano uno score (calcolato

ad esempio usando una matrice di sostituzione) maggiore di

una soglia T quando allineati con il segmento W sulla

sequenza query. Abbassando la lunghezza della parola (w) si

ha lo stesso effetto di quando abbassiamo la soglia (T).

Specificando una dimensione più piccola parola induce un rallentamento e una ricerca più

accurata.

Fase 2: ricerca di corrispondenze esatte (hits)

L’algoritmo analizza tutte le sequenze del database ricercando la presenza di w-mers

corrispondenti esattamente alle parole della lista prodotta dall’analisi della sequenza query. Ogni

corrispondenza trovata (hit) potrebbe rappresentare una porzione di un possibile allineamento più

esteso.

Fase 3: verifica dell’estendibilità di ogni hit (HSP)

si cerca di estendere l’allineamento in entrambe le direzioni, senza considerare la possibilità di

inserire gap si ottiene un allineamento locale, non ulteriormente estendibile, che viene definito

High-scoring Segment Pair (HSP). Il processo di estensione termina quando il punteggio scende

sotto una soglia. Un HSP è ritenuto degno di attenzione se i suo score è maggiore di una soglia S

predefinita. Al di sotto della soglia scarto.

La procedura di estensione viene arrestata in una delle due direzioni quando il punteggio di

similarità relativo alla coppia di segmenti in esame viene decrementato, di un certo valore

prestabilito, rispetto a quello relativo ad una minore estensione della stessa coppia di segmenti

L’algoritmo BLAST utilizza 4 parametri principali:

1. W: lunghezza della parola da ricercare (W=3, 4)

2. T: soglia del punteggio di allineamento tra i w-mers. È generalmente impostato dal

programma sulla base dello schema di punteggio adottato (ad es.: matrice di sostituzione).

T piccoli implicano molti w-mers da ricercare e quindi un elevato tempo computazionale.

Per alti valori di T si rischia però di non identificare alcun High-scoring Segment Pair

3. S: soglia del punteggio di allineamento HSP 4. X: misura della perdita di score

indotta dal trovare score negativi

durante l’estensione di un HSP. Più

è basso maggiore sarà il tempo e

viceversa.

FIGURA 4.11. Schematica della algoritmo

BLAST originale. Nel prima fase una

sequenza di interrogazione è analizzata

con una data dimensione della parola w , e

un elenco di parole viene compilato avere

un punteggio soglia T. Le possibili parole

derivate dalla sequenza di interrogazione

sono elencati in figura. Per una

determinata parola, come la porzione della

query sequenza costituito LWG, un elenco

di parole viene compilato con i punteggi

maggiore o uguale ad alcuni soglia T (ad

esempio, 11).

In questo esempio 15 parole sono

mostrate insieme con i loro punteggi

provenienti da un Matrice BLOSUM62;

dieci di questi sono sopra la soglia, e cinque sono qui sotto. Nella fase 2, un database viene

acquisito per trovare le voci che corrispondono l'elenco di parole compilato. In fase 3, i colpi di

database sono esteso in entrambe le direzioni per ottenere una coppia segmento alto punteggio

(HSP). Se il punteggio HSP supera un particolare punteggio di taglio S, è riportato nell'output

BLAST.

È possibile mettere in relazione il valore della soglia S con il numero atteso a priori di HSP (definito

E-value o E) che raggiungono tale soglia in una banca di sequenze casuali della stessa grandezza

di quella considerata.

Qui, E si riferisce al valore atteso, che è il numero di diversi allineamenti con punteggi equivalenti o

migliori rispetto S che si pensa che accada per caso in una ricerca di database. Ciò fornisce una

stima del numero di falsi risultati positivi da una ricerca BLAST.

m è la lunghezza della sequenza query, n la lunghezza totale

delle sequenze nel database, K è una costante e λ è calcolata

risolvendo un’equazione che tiene conto della probabilità di ogni

carattere nella banca dati e della matrice di costo adottata. Aumentando S diminuisce ovviamente

E.

Dalla equazione si vede che il valore E dipende dal punteggio di λ, che è un parametro che scala il

sistema di punteggio. Inoltre, E dipende dalla lunghezza della sequenza di interrogazione (m) e la

lunghezza del database (n). Il parametro K è un fattore di scala per lo spazio di ricerca costante.

I valori più elevati di S corrispondono a allineamenti migliori; i risultati BLAST sono classificate in

base al punteggio. Così, un punteggio elevato su una ricerca BLAST corrisponde ad un valore

basso E. E se si avvicina a zero, indica che la probabilità che l'allineamento si è verificato per caso

sia nulla o quasi nulla.

Normalmente il valore di E viene impostato dall’utente mentre quello di S viene ricavato dalla

formula riportata sopra. Molto spesso si imposta un valore di E piuttosto piccolo (ad es.: 0.1) per

evitare che il programma restituisca allineamenti con score bassi.

Per il calcolo di λ e K, invece di usare sequenze casuali della stessa composizione e lunghezza

della sequenza query, BLAST utilizza un insieme di sequenze casuali con una composizione

standard, il procedimento non viene quindi ripetuto per ogni sequenza query, ma λ e K vengono

calcolati una sola volta per ciascuna banca dati e per ciascuna matrice di scoring.

Le matrici di sostituzione

Abbiamo visto che p