WORKING WITH BIOSEQUENCES
Alignments and similarity search
IV LEZIONE
• Allineamento locale
• Ricerca di similarita’
• BLAST
Allineamento locale. Perchè?
• Sequenze diverse possono presentare una o piu’ brevi
regioni di similarità pur essendo diverse nelle restanti
regioni. Queste potrebbero risultare non allineabili con
un metodo per allineamento globale di sequenze.
• Esempio:
– I geni Homeobox mostrano una regione di
sequenza altamente conservata, codificante
l’Homeodominio, un dominio legante il DNA.
– Un allineamento globale tra sequenze di fattori di
trascrizione diversi con omeodominio potrebbe non
individuare la corrispondente regione di similarità,
mentre un allineamento locale risulta estremamente
utile.
An Introduction to Bioinformatics Algorithms
www.bioalgorithms.info
ALGORITMO DI SMITH & WATERMAN PER L’ALLINEAMENTO LOCALE
Local
Example
Lo scopo Alignment:
degli algoritmi di allineamento
locale di due sequenze
e’ trovare la regione piu’ lunga della prima sequenza che
produce un allineamento ottimale, dati certi parametri, con una
regione della seconda.
Local alignment
Global alignment
Compute a “mini”
Global Alignment to
get Local
ALGORITMO DI SMITH & WATERMAN PER L’ALLINEAMENTO LOCALE
 Anche il metodo di Smith and Waterman utilizza una matrice per
comparare le due sequenze
 Il valore numerico contenuto in ciascuna cella rappresenta il
punteggio dell’allineamento locale che termina ai due residui
corrispondenti
 I valori inferiori a 0 vengono posti a 0
 Cosi’, l’identificazione dei punteggi piu’ alti nella matrice permette di
trovare i migliori allineamenti locali tra le due sequenze.
Per misurare la bonta’ degli allineamenti si definiscono due funzioni:
• SIMILARITY SCORE
dipende dal PUNTEGGIO PER IL MATCH di residui e dal numero di
matches
• GAP PENALTY
dipende dal numero e dalla lunghezza dei gaps
The Smith-Waterman algorithm implements a very straightforward variation
of the Needleman-Wunsch algorithm, which is to replace the overall score
of the alignment by zero if it takes on negative values for all alternative
pathways.
Forward algorithm of the Needleman and Wunsch algorithm to recursively
compute the entries of the alignment matrix. The grey box represents the
additional parcel of the Smith Waterman algorithm
CALCOLO DEL PUNTEGGIO PER UN ALLINEAMENTO
GAPS
MATCHES
MISMATCHES
Data una coppia di sequenze Sa e Sb
Per ogni coppia di elementi ai e bj di Sa e Sb si definisce un punteggio s(ai,bj)
s(ai,bj) = 
s(ai,bj) = 
se ai = bj
se ai  bj , con  > 
SIMILARITY SCORE
Ad ogni ogni gap viene assegnato un punteggio dato da:
Wk =  + (k-1)
Dove Wk e’ una funzione lineare che assegna una penalita’ constante alla
presenza del gap (, ad es. -10) e una penalita’ proporzionale alla lunghezza
del gap meno uno.
 (gap opening penalty, GOP)
 (gap extension penalty, GEP)
GAP PENALTY
Il punteggio complessivo risultera’:
 (s(ai,bj) ) +  (Wk)
CALCOLO DEL PUNTEGGIO PER UN ALLINEAMENTO
Sequenze:
ATTCCGAG
AGAC
Possibile allineamento:
ATTCCGAG
|
||
A----GAC
Assegno i seguenti punteggi:
Match:
+2
Mismatch:
-1
GOP:
-5
GEP:
-2
MATCHES
3
MISMATCHES 1
SIMILARITY SCORE
GAPS
GOP
GEP
GAP PENALTY
3x2=6
1 x –1 = -1
6 –1 = 5
1 (lungo 4 nucleotidi)  GOP + GEP X 3
-5
-2 x 3
-5 + (3 x –2) = -11
PUNTEGGIO FINALE
5 – 11 = -6
RICERCA DI SIMILARITÀ
Una sequenza “da sola” non e’ informativa, deve essere analizzata
comparativamente al contenuto dei database perche’ possano essere
formulate delle ipotesi sulla sue relazioni evolutive con sequenze simili
o sulla sua funzione.
Domande cui si puo’ rispondere con una ricerca di similarita’:
• Data una sequenza, ci sono cose simili nel database?
• Ho trovato un nuovo gene o una nuova proteina?
• Il gene ha somiglianze con qualche altro gene nella stessa specie o in
altre specie?
• Fare ipotesi sulla funzione di una proteina
• Trovare le regione di sovrapposizione tra sequenze contigue
• Trovare la regione genomica codificante un trascritto
• Studiare l’evoluzione di popolazioni o specie
RICERCA DI SIMILARITÀ
SIMILARITA’ ? OMOLOGIA
OMOLOGIA proprieta’ di caratteri (sequenze) dovuta alla loro
derivazione dallo stesso antenato comune
SIMILARITA’ “grado” di somiglianza tra 2 sequenze
• La similarita’ osservata tra due sequenze PUO’ indicare che esse siano
omologhe, cioe’ evolutivamente correlate
• La similarita’ e’ una proprieta’ quantitativa, si puo’ misurare
• L’omologia e’ una proprieta’ qualitativa, non si puo’ misurare.
• La similarita’ tra sequenze si osserva, l’omologia tra sequenze si puo’
ipotizzare in base alla similarita’ osservata.
Percentuale di similarita’
Ricerca di similarita’
OMOLOGIA E OMOPLASIA
Omologia
Omoplasia
similarita’ dovuta a derivazione dallo stesso antenato
comune
similarita’ dovuta a convergenza, stessa pressione selettiva
su due linee evolutive puo’ condurre a caratteri simili
ORTOLOGIA E PARALOGIA
OMOLOGIA
ANTENATO COMUNE
ORTOLOGIA
PARALOGIA
PROCESSO DI SPECIAZIONE
DUPLICAZIONE GENICA
Descrivo le relazioni tra geni di una famiglia
intraorganismo (paralogia)
o tra diversi organismi (ortologia)
 Dimensioni delle banche dati
 Ripetitività delle ricerche
 Lentezza degli algoritmi “esatti”
Sistemi rapidi ma
approssimati di
allineamento
Metodi euristici per l’allineamento
• gli algoritmi esatti effettuano delle ricerche esaustive ed esplorano
tutto lo spazio degli allineamenti possibili (programmazione dinamica)
• si tratta comunque di algoritmi di ordine n2, ovvero per allineare due
sequenze lunghe ognuna 1000 residui, effettuano 1000x1000 = un
milione di confronti: troppo lenti!!!!
• la crescita esponenziale delle dimensioni delle banche dati di
sequenze biologiche ha portato allo sviluppo di programmi (come
FASTA e BLAST) in grado di effettuare velocemente ricerche di
similarità, grazie a soluzioni euristiche che sono basate su assunzioni
non certe, ma estremamente probabili. In pratica la ricerca è resa più
veloce a scapito della certezza di avere veramente trovato la soluzione
migliore
BLAST
Basic Local Alignment Search Tool
(Altschul 1990)
L’ algoritmo di BLAST e’ euristico e opera:
1 Tagliando le sequenze da comparare in piccoli pezzi (parole)
2 Ignorando tutte le coppie di parole (sequenza query/database) la cui
comparazione da’ un punteggio inferiore ad un limite fissato
3 Cercando di estendere tutte le hits rimanenti sino a che l’allineamento
locale raggiunge un certo punteggio
Dati una SEQUENZA QUERY ed un DATABASE DI SEQUENZE, BLAST
ricerca nel database “parole” di lunghezza almeno “W” con un punteggio di
similarita’ di almeno “T” una volta allineate con la sequenza “query” (HSP,
High Scoring Pairs).
Le “parole” selezionate vengono estese, se possibile, fino a raggiungere un
punteggio superiore a “S” oppure un “E-value” inferiore al limite specificato.
1- Seeding
• In sequenze di DNA
W=7
• In sequenze
proteiche W = 2-3
Two-hits algorithm
• Le word-hits tendono a clusterizzare lungo le diagonali
• L’algoritmo two-hits richiede che le word-hits siano entro una
distanza prestabilita
2 - Extension
• La fase successiva comporta l’estensione dei seed
• L’estensione avviene in entrambe le direzioni
• Blast ha un meccanismo per decidere quando
fermare l’estensione
3 - Evaluation
The quick brown fox jumps over the lazy dog
||| |||
|||||
|
|
||
The quiet brown cat purrs when she sees him
The
|||
The
Score -> 123
drop off score -> 000
quick
|||
quiet
45654
00012
Estensione verso destra >>>>
• Diamo punteggio
+1 a ciascun match
–1 a ciascun mismatch.
• Calcoliamo il drop off score
a partire dal massimo
raggiunto (punteggio 9).
• Quando il drop off raggiunge
5, si interrompe l’estensione.
brown
|||||
brown
56789
10000
fox jump
|
cat purr
876 5654
123 4345
Il risultato di una ricerca di similarita’ e’ una lista dei migliori allineamenti,
tra la sequenza query e le sequenze “estratte” dal database.
La SIGNIFICATIVITA’ di ciascun allineamento si calcola come P value o
E value
P value e’ la probabilita’ di ottenere un allineamento con punteggio
uguale o migliore di quello osservato
Si calcola mettendo in relazione il punteggio osservato (S) con la
distribuzione attesa di HSP quando si comparano sequenze random
della stessa lunghezza e composizione di quella in analisi (query
sequence)
Piu’ il P value e’ vicino a 0 piu’ e’ significativo
2x10-245 e’ meglio do 0.001 !!!
E value e’ il numero atteso di allineamenti con punteggio uguale o
migliore di quello osservato
Piu’ e’ basso piu’ e’ buono
Significatività di un allineamento
Sequenze allineate
Osservazione
Ipotesi alternative
ATTGCCCACGTTCGCGATCG
ATAGGGCACTTT-GCGATGA
** * *** ** *****
OMOLOGIA?
CASO?
Significatività di un allineamento
Sequenze
originali
Allineamento
Seq1
Seq2
Seq1
Seq2
V D C - C Y
V E C L C Y
Score
4
V D C C Y
V E C L C Y
(matrice Blosum62, gap=-11)
2
9-11 9 7
Sequenze
randomizzate
Allineamento
Seq1
Seq2
Seq1
Seq2
C D V Y C
C V Y L E C
Score = 20
(matrice Blosum62, gap=-11)
Score
C D V Y - C
C V E Y L C
9 -3 -2 7 -11 9
Score = 9
Ripetere (es. 10.000 volte)
salvando tutti i punteggi
Distribuzione
score casuali
Score allineamento (20)
Score
Usare BLAST
Sequenza query
OPZIONI
nucleotidica
proteica
(sequenza in formato FASTA, GenBank
Accession numbers o GI numbers)
Database
database di seq. nucleotidiche
database di seq. proteiche
Programma
Standard BLAST (blastn)
Standard protein BLAST (blastp)
translated blast (blastx, tblastn, tblastx)
MEGABLAST
PSI-BLAST
PHI-BLAST
…
Blast selection table
http://www.ncbi.nlm.nih.gov/BLAST/producttable.shtml
Usare BLAST
database di seq. nucleotidiche
nr
est
est_human
est_mouse
htgs
yeast
mito
vector
month
alu
dbsts
chromosome
All GenBank+EMBL+DDBJ+PDB sequences (but no EST, STS,
GSS, or phase 0, 1 or 2 HTGS sequences). No longer "nonredundant".
Database of GenBank+EMBL+DDBJ sequences from EST
division.
Unfinished High Throughput Genomic Sequences
Saccharomyces cerevisiae genomic nucleotide sequences
Database of mitochondrial sequences
Vector subset of GenBank(R), NCBI, in
All new or revised GenBank+EMBL+DDBJ+PDB sequences
Select Alu repeats from REPBASE, suitable for masking Alu
repeats from query sequences.
Database of GenBank+EMBL+DDBJ sequences from STS
division.
Searches Complete Genomes, Complete Chromosome, or contigs
form the NCBI Reference Sequence project.
Usare BLAST
PROGRAMMI
Blastn Nucleotide query - Nucleotide db
Blastp Protein query - Protein db
Translating BLAST attraverso la traduzione concettuale della query
sequence o dei database permette di comparare una sequenza
nucleotidica con database di proteine o viceversa.
Translated query - Protein db
blastx
Protein query - Translated db
tblastn
Translated query - Translated db tblastx
MEGABLAST usa un algoritmo greedy (ingordo) veloce ed ottimizzato per
comparare sequenze che differiscono poco
Search for short nearly exact matches blastn con parametri scelti in modo
da ottimizzare la ricerca di matches quasi esatti e brevi. Questi si
trovano spesso per caso, percio’ utilizza alto E-value, piccola
dimensione della parola e filtering
PSI-BLAST
Find members of a protein family or build a custom positionspecific score matrix
PHI-BLAST
Find proteins similar to the query around a given pattern