1) Algoritmi di allineamento

2) Algoritmi di ricerca in database

similarità allineamento

abbiamo visto che per generare e valutare il miglior allineamento di due sequenze di lunghezza m e n, è necessario effettuare m x n confronti

il numero di operazioni da effettuare cresce e i tempi di calcolo di conseguenza si allungano se si vogliono considerare anche i possibili gap in tutte le posizioni (e di tutte le lunghezze possibili) di entrambe le sequenze

IPLMTRWDQEQESDFGHKLPIYTREWCTRG            |||||||||| CHKIPLMTRWDQQESDFGHKLPVIYTREW

IPLMTRWDQEQESDFGHKLP-IYTREWCTRG   ||||||||| |||||||||| |||||| CHKIPLMTRWDQ-QESDFGHKLPVIYTREW

gli allineamenti possono essere visualizzati graficamente in modo rapido (con algoritmi dell’ordine di mxn) con matrici di punti (dot plots)

noi VOGLIAMO considerare i gap, ma non POSSIAMO permetterci algoritmi che considerino tutti i possibili gap in tutte le possibili posizioni

identità finestra = 5 finestra = 15

• punteggi diversi per ogni possibile coppia di residui allineati (matrici di sostituzione)

• gap penalties e

•gap extension penalties per valutare penalizzazioni dovute all’introduzione di gap nelle sequenze allineate

abbiamo definito un modo formale di valutare il punteggio di un allineamento, che tenga conto di

NG

ki

L

iiAB kbasS

11

1)(),(

che algoritmi possiamo usare?

PROGRAMMAZIONE DINAMICA

razionalizzare il problema:considerare anche i gap pur continuando ad

utilizzare un algoritmo dell’ordine di n2)

spesso l’output mostra più allineamenti DIVERSI col massimo del punteggio

ci mette TROPPO TEMPO per effettuare una ricerca esaustiva

scegliere una matrice di sostituzione per valutare gli appaiamenti tra residui

definire dei punteggi di penalizzazione per i gaps

algoritmi di allineamento che utilizzano una tecnica di programmazione dinamica:

Needleman e Wunsch (1970)Smith e Waterman (1981)

3 passi successivi

1) consideriamo le due sequenze da allineare in una specie di dot plot : nelle caselle scriviamo i punteggi in rosso derivati dalla matrice di sostituzione scelta

QERTY|||:QERS

allineamento punteggio

QQ + EE + RR + TS =

4 + 4 + 6 + 1 = 15

cominciamo a calcolare la matrice di questo allineamento usata nell’algoritmo di programmazione dinamica

Q E R T YQ 4 2 1 -1 -4E 2 4 -1 0 -4R 1 -1 6 -1 -4S -1 0 0 1 -3

2) ricerca del percorso che consente di ottenere il massimo punteggio in base a delle regole stabilite, tenendo anche conto dei gaps

se una sequenza è scritta da sinistra a destra e l’altra dall'alto in basso, allora qualsiasi percorso valido deve mantenere sempre una direzione tendenziale che va dall'angolo in alto a sinistra a quello in basso a destra

Misura della similarità:i punteggi in diagonale si SOMMANOfuori dalla diagonale, si PENALIZZA di 5 punti

evidenzieremo in grigio il migliore percorso all’interno della matrice, secondo le regole e i punteggi stabiliti

il migliore allineamento globaleglobale per le sequenze in matrice risulta quindi il seguente:

TFDERILGVQ-TYWAECLA || | | | . || QTFWECIKGDNATY

per ricostruire l’allineamento migliore si può memorizzare il percorso disegnato riempiendo la matrice

alla fine bisogna partire dalla casella a punteggio maggiore e ricostruire il percorso a ritroso seguendo le freccette

TFDERILGVQ-TYWAECLA || | | | . ||QTFWECIKGDNATY

Qual è il tipo di allineamento che consideriamo più interessante dal punto di vista biologico?

date due sequenze, per esempio:

1) LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK2) TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG

Allineamento globale:

LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||.  | |  |  .|     .|  ||  || | || TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG

Allineamento locale:

TGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK        ||||||||.|||||      TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG

Allineamento globale o locale?

Allineamento globale o locale?

a livello di DNA, troviamo regioni con similarità locali che riflettono situazioni interessanti: ad esempio introni/esoni, inserzioni/delezioni, transposoni, regioni promotore…

esoni introni

allineamenti globali:

confrontare accuratamente due sequenze la cui similarità sia estesa per tutta la lunghezza

(es. Proteine omologhe)

Usando matrici di sostituzione contenenti esclusivamente valori esclusivamente valori positivipositivi il valore massimo della matrice si trova sempre nell’ultima riga o nell’ultima colonna

ne consegue che l’allineamento ottenuto è un allineamento globale

il numero di operazioni effettuate è proporzionale a m x n

abbiamo considerato tutti i possibili allineamenti tra le due sequenze e tutte le possibili posizioni per i gap

se le matrici contenessero sia valori positivi che negativi (come le PAM o le BLOSUM), i valori più alti potrebbero trovarsi anche in porzioni INTERNE alla matrice

Come ottenere un allineamento locale?

ogni percorso che totalizza un punteggio negativo viene azzerato e può venire considerato come l’inizio di un nuovo allineamento locale

quando i tre percorsi di possibile provenienza per una casella risultano negativi, il punteggio associato alla casella sarà pari a zero

3 -3

-3 9

3 0

0 12

-7 -6

0 -2

0 0

1 0

Gli algoritmi per il Database similarity searching

•FASTA

•BLAST

Prerequisiti dei metodi di Database similarity searching

• Velocità• Sensibilità • Selettività

Fissata una soglia minima di similarità se

• TP = positivi veri• PP = positivi predetti (falsi e veri)• AP = actual positives ( n.reale di

sequenze omologhe presenti nel db indipendentemente dalla soglia)

Prerequisiti dei metodi di Database similarity searching

Database similarity searching

• Sensibilità = TP/AP• Selettività =TP/PP

• La scelta della soglia e’ fatta su basi statistiche ed e’ determinante.

• Alta sensibilità bassa selettività e viceversa

Database similarity searching

Ambedue i metodi (FASTA e BLAST) effettuano ricerche di similarità mediante applicazioni di metodi per allineamenti locali e, dal confronto di una sequenza anonima con set di sequenze a funzione nota, selezionano le sequenze con punteggi di similarità (scores) superiore ad una certa soglia (threshold), valutata su basi statistiche e dinamicamente in correlazione con il dataset sotto studio.

Database searching

Ambedue i metodi ottengono una elevata velocità di esecuzione grazie alla trasformazione delle sequenze in vettori

Scelta la dimensione w della stringa su cui operare per la ricerca delle similarità, le sequenze da confrontare sono trasformate in vettori di dimensione Dw, in ogni cella dei quali sono riportate le posizioni in cui la i-esima "stringa" di dimensione w ricorre nella sequenza

Database searchingDatabase searching

FASTA Ammette i gaps e produce una sola

regione di miglior similarità per ogni coppia analizzata (query seq. vs. db seq)

Database searchingDatabase searching

BLAST Non ammette(va) i gaps e produce più regioni di similarità per ogni coppia analizzata

FASTA

Fissato il parametro ktup ( il numero di residui

contigui identici), consideriamo due sequenze, S1 e

S2, e cerchiamo le k-tuple perfettamente identiche

il cui inizio é localizzato rispettivamente nelle posizioni i e j; nell'ipotetica matrice dot-plot relativa a queste due sequenze tale identità sarà localizzata nella diagonale m=i-j.

FASTA

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 (Pearson, 1990).

Vengono selezionate le prime dieci regioni di similarità localizzate anche su differenti diagonali.

FASTA fase 2Il punteggio di similarità relativo alle regioni precedentemente considerate viene calcolato prendendo in considerazione tratti di sequenza identici più corti di ktup, eventuali sostituzioni conservative e consentendo anche l’introduzione di piccoli gaps.Per le sequenze proteiche PAM-250 Per le sequenze nucleotidiche punteggio positivo alle identità e negativo alle differenze. 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

FASTA fase 3

Le regioni di similarità precedentemente determinate vengono potenzialmente ricongiunte per formare un unico allineamento.

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.

FASTA fase 3

Il punteggio di similarità relativo

all'allineamento che così viene 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.

FASTA fase 4

Nella quarta ed ultima fase, l'allineamento precedentemente ottenuto viene ulteriormente ottimizzato utilizzando la procedura di allineamento descritta da Chao et al. (1992) che utilizza un algoritmo per l'allineamento di due sequenze all'interno di una banda diagonale di dimesioni predeterminate. Il punteggio di similarità calcolato in quest'ultima fase viene denominato punteggio opt.

Le coppie di segmenti, presenti nella stessa coppia di sequenze, che totalizzino un punteggio di similarità statisticamente significativo, superiore ad una soglia S, vengono definiti HSP (High scoring Segment Pairs).

Nella stessa coppia possono esserci più HSP di cui é anche possibile calcolare la probabilità di occorrenza (Karlin & Altschul, 1993).

BLAST(Basic Local Alignment Search

Tool)

Una volta individuata una stringa coincidente (matching word), questa viene estesa verso entrambe le direzioni. 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.

BLAST(Basic Local Alignment Search

Tool)

L’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 segmenti 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.

Un algoritmo in grado di individuare in modo estremamente rapido tutte le coppie di segmenti per cui il punteggio di similarità risulta statisticamente significativo.

BLAST(Basic Local Alignment Search

Tool)

La peculiare strategia di BLAST é di cercare esclusivamente coppie di segmenti che contengano una coppia di “stringhe” di lunghezza w il cui relativo punteggio di similarità sia almeno pari ad una soglia T. Il valore della soglia T (≤S) viene stimato sulla base della dimensione di w.

BLAST(Basic Local Alignment Search

Tool)

BLAST(Basic Local Alignment Search

Tool) S(a,b) utilizza matrici BLOSUM o PAM per le sequenze

aminoacidiche o un punteggio pari a +5 per le identità e -4 per le differenze per sequenze nucleotidiche

Si definisce MSP (Maximal scoring Segment Pair) la coppia di segmenti, di eguale lunghezza, che realizza il massimo punteggio di similarità nel confronto di due sequenze; l’algorimo ne valuta in modo rigoroso la significatività statistica (Karlin & Altschul, 1990, 1993).