A.A. 2013-2014
CORSO INTEGRATO DI
INFORMATICA E
BIOINFORMATICA
per il CLT in BIOLOGIA MOLECOLARE
Scuola di Scienze, Università di Padova
Docenti: Dr. Mauro Conti (Informatica) e Dr.
Stefania Bortoluzzi (Bioinformatica)
WORKING WITH BIOSEQUENCES
Alignments and similarity search
WORKING WITH BIOSEQUENCES
Alignments and similarity search
•
•
•
•
•
Allineamento di sequenze
Allineamento globale e allineamento locale
Allineamento di sequenze a coppie o multiplo
Ricerca di similarita’
BLAST
ALLINEAMENTO DI SEQUENZE
Procedura per comparare due o piu’ sequenze,
volta a stabilire un insieme di relazioni biunivoche
tra coppie di residui delle sequenze considerate
che massimizzino la similarita’ tra le sequenze
stesse
L’allineamento tra due sequenze biologiche è
utile per scoprire informazione funzionale,
strutturale ed evolutiva
Cosa vuol dire allineare due sequenze
(proteine o acidi nucleici)?
Scrivere due sequenze orizzontalmente in modo
da avere il maggior numero di simboli identici o
simili in registro verticale anche introducendo
intervalli (gaps – inserzioni/delezioni – indels)
• seq1: TCATG
• seq2: CATTG
TCAT-G
.CATTG
4 caratteri uguali
1 inserzione/delezione
ALLINEAMENTO DI SEQUENZE
A COPPIE
AGTTTGAATGTTTTGTGTGAAAGGAGTATACCATGAGATGAGATGACCACCAATCATTTC
|||||||||||||||||||
|||||||| ||| | |||||| |||||||||||||||||
AGTTTGAATGTTTTGTGTGTGAGGAGTATTCCAAGGGATGAGTTGACCACCAATCATTTC
MULTIPLO
KFKHHLKEHLRIHSGEKPFECPNCKKRFSHSGSYSSHMSSKKCISLILVNGRNRALLKTl
KYKHHLKEHLRIHSGEKPYECPNCKKRFSHSGSYSSHISSKKCIGLISVNGRMRNNIKT-
KFKHHLKEHVRIHSGEKPFGCDNCGKRFSHSGSFSSHMTSKKCISMGLKLNNNRALLKRl
KFKHHLKEHIRIHSGEKPFECQQCHKRFSHSGSYSSHMSSKKCV---------------KYKHHLKEHLRIHSGEKPYECPNCKKRFSHSGSYSSHISSKKCISLIPVNGRPRTGLKTs
Allineamento GLOBALE o LOCALE
GLOBALE  considera la similarità tra due sequenze in tutta
la loro lunghezza
LOCALE  considera solo specifiche REGIONI simili tra
alcune parti delle sequenze in analisi
Global alignment
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK
||. | | | .|
.| || || | ||
TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
Local alignment
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK
||||||||.||||
TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHK
ALLINEAMENTO GLOBALE
ALLINEAMENTO LOCALE
Allineamento manuale basato sulla massimizzazione del
Numero possibili
numero residui identici allineati
allineamenti di
due seq lunghe N
seq1
AACCGTTGACTTTGACC
Seq2
ACCGTAGACTAATTAACC
AACCGTTGACT..TTGACC
| ||||.||||
||.|||
A.CCGTAGACTAATTAACC
Fattibile solo per poche sequenze molto brevi!
N=250  10149
Possono esistere più allineamenti “equivalenti”
AACCGAAGGACTTTAATC
AAGGCCTAACCCCTTTGTCC
AA..CCGAAGGACTTTAATC
AACCGAAGGACT
TTAATC
||
|..||...||||...|
|
|||.||
||..||
AAGGCTAAACCCCTTTGTCC
A
AGGCCTAACCCCTTTGTC
Un metodo molto semplice ed utile per la comparazione di due
sequenze è quello della MATRICE DOTPLOT
A|X
X
X
T|
X
X
G|
X
T|
X
X
C|
X
A|X
X
X
C|
X
T|
X
X
A|X
X
X
+------------------A T C A G T A
A T C A C T G T A
| | | |
| | |
A T C A - - G T A
• A DNA dot plot of a human
zinc finger transcription
factor, showing regional selfsimilarity
• The main diagonal
represents the sequence's
alignment with itself
• Lines off the main diagonal
represent similar or repetitive
patterns within the sequence
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:
ESEMPIO
Sequenze:
ATTCCGAG
AGAC
Possibile allineamento:
ATTCCGAG
|
||
A----GAC
Assegno i seguenti punteggi:
Match:
+2
Mismatch:
-1
GOP:
-5
GEP:
-2
MATCHES
MISMATCHES
SIMILARITY SCORE
3
1

3x2=6
1 x –1 = -1
6 –1 = 5
GAPS 1 (lungo 4 nucleotidi)
GOP
-5
GAP PENALTY

GOP + GEP X 3
GEP
-2 x 3
-5 + (3 x –2) = -11
PUNTEGGIO FINALE
5 – 11 = -6
MISURE DI IDENTITA’ E DI SIMILARITA’
Il modo più semplice per definire le relazioni di similarità tra
nucleotidi è basato solo su IDENTITA’ e DIVERSITA’.
La piu’ semplice matrice di similarità per i nucleotidi è la
“UNITARY SCORING MATRIX”, matrice che assegna
punteggio 1 a coppie di residui identici e 0 ai mismatch.
A C G T
--------A | 1 0 0 0
C | 0 1 0 0
G | 0 0 1 0
T | 0 0 0 1
Possono esserci altri criteri per dare un peso diverso da zero a
matches tra residui non identici (ad.es. pesare in modo diverso
transizioni e transversioni)
MISURE DI IDENTITA’ E DI SIMILARITA’
• E’ possibile misurare la similarità tra aminoacidi tenendo conto
delle loro proprietà chimico-fisiche
ad. es. l‘acido glutammico è più simile all’acido aspartico che alla
fenilalanina
• Un altro modo per misurare la similarità tra aminoacidi è fondato
sulle frequenze osservate di specifiche sostituzioni amminoacidiche
in opportuni gruppi di allineamenti.
La similarità tra due specifici aminoacidi (ed es. A e G) e’
proporzionale alla frequenza con cui si osserva la sostituzione
corrispondente (A->G).
Le MATRICI DI SOSTITUZIONE piu’ conosciute ed utilizzate sono
le matrici PAM (o Dayhoff Mutation Data (MD) Matrices) e le matrici
BLOSUM.
Matrici di sostituzione
• Le matrici di sostituzione si basano su
evidenze biologiche
• Le differenze che si osservano tra sequenze
omologhe negli allineamenti sono riconducibili
ad eventi di mutazione
• Alcune di queste mutazioni hanno effetti
trascurabili sulla struttura/funzione della
proteina
LE PROTEINE : 20
AMMINOACIDI proteinogenici
Esempio di matrice di sostituzione
A
R
N
N
K
A
R
K
A
5
-2 -1 -1
R
-
7
-1 3
N
-
-
7
0
K
-
-
-
6
• Nonostante K e R siano
due amminoacidi diversi ,
hanno uno score positivo.
• Perchè? Sono entrambi
amminoacidi carichi
positivamente.
MATRICI PAM
(Dayhoff et al. 1978)
Sono basate sul concetto di mutazione puntiforme accettata,
Point Accepted Mutation (PAM)
Le prime matrici PAM sono state compilate in base all’analisi
delle sostituzioni osservate in un dataset costituito da diversi
gruppi di proteine omologhe:
•1572 sostituzioni osservate in 71 gruppi di sequenze di
proteine omologhe con similarità molto alta (85% di
identità)
La scelta di proteine molto simili era motivata dalla semplicità
dell’allineamento, senza necessità di introdurre correzioni per
multiple hits, ovvero sostituzioni quali A->G->A or A->G->N.
L’analisi degli allineamenti mostrò come diverse sostituzioni
aminoacidiche si presentassero con frequenze anche molto
differenti:
le sostituzioni che non alterano “seriamente” la funzione
della proteina, quelle “accettate” dalla selezione, si osservano
piu’ di frequente di quelle “distruttive”.
La frequenza osservata per ciascuna specifica sostituzione
(es. aaJ aaK) sul totale delle sostituzioni viene usata per
stimare la probabilità della transizione corrispondente in un
allineamento di proteine omologhe.
Le probabilità di tutte le possibili sostituzioni sono riportate
nella matrice PAM
La matrice PAM1 di base definisce la probabilità di transizione
di un aminoacido in un altro aminoacido che consente di
conservare il 99% della sequenza.
Matrici BLOSUM - Blocks Substitution Matrix
(Henikoff and Henikoff, 1992)
• Matrici di sostituzione derivate dallanalisi di oltre 2000
blocchi di allineamenti multipli di sequenze, che
riguardavano regioni conservate di sequenze correlate.
• Per ridurre il contributo di coppie di amminoacidi di
proteine altamente correlate, gruppi di sequenze molto
simili sono state trattate come se fossero sequenze singole
ed e’ stato calcolato il contributo medio di ciascuna posizione.
• Utilizzando diversi cut-off per il raggruppamento di
sequenze simili si sono ottenute diverse matrici BLOSUM
(BLOSUM62, BLOSUM80, …)  Il nome della matrici indica la
distanza evolutiva (BLOSUM62 è stata creata usando
sequenze che non avevano più del 62% di identità)
BLOSUM62 Substitution Matrix
BLOSUM62
C
S
T
P
A
G
N
D
E
Q
H
R
K
M
I
L
V
F
Y
W
C
9
-1
-1
-3
0
-3
-3
-3
-4
-3
-3
-3
-3
-1
-1
-1
-1
-2
-2
-2
S
-1
4
1
-1
1
0
1
0
0
0
-1
-1
0
-1
-2
-2
-2
-2
-2
-3
T
-1
1
4
1
-1
1
0
1
0
0
0
-1
0
-1
-2
-2
-2
-2
-2
-3
P
-3
-1
1
7
-1
-2
-2
-1
-1
-1
-2
-2
-1
-2
-3
-3
-2
-4
-3
-4
A
0
1
-1
-1
4
0
-2
-2
-1
-1
-2
-1
-1
-1
-1
-1
0
-2
-2
-3
G
-3
0
1
-2
0
6
0
-1
-2
-2
-2
-2
-2
-3
-4
-4
-3
-3
-3
-2
N
-3
1
0
-1
-1
-2
6
1
0
0
1
0
0
-2
-3
-3
-3
-3
-2
-4
D
-3
0
1
-1
-2
-1
1
6
2
0
1
-2
-1
-3
-3
-4
-3
-3
-3
-4
E
-4
0
0
-1
-1
-2
0
2
5
2
0
0
1
-2
-3
-3
-2
-3
-2
-3
Q
-3
0
0
-1
-1
-2
0
0
2
5
0
1
1
0
-3
-2
-2
-3
-1
-2
H
-3
-1
0
-2
-2
-2
-1
-1
0
0
8
0
-1
-2
-3
-3
-3
-1
2
-2
R
-3
-1
-1
-2
-1
-2
0
-2
0
1
0
5
2
-1
-3
-2
-3
-3
-2
-3
K
-3
0
0
-1
-1
-2
0
-1
1
1
-1
2
5
-1
-3
-2
-2
-3
-2
-3
M
-1
-1
-1
-2
-1
-3
-2
-3
-2
0
-2
-1
-1
5
1
2
1
0
-1
-1
I
-1
-2
-2
-3
-1
-4
-3
-3
-3
-3
-3
-3
-3
1
4
2
3
0
-1
-3
L
-1
-2
-2
-3
-1
-4
-3
-4
-3
-2
-3
-2
-2
2
2
4
1
0
-1
-2
V
-1
-2
-2
-2
-2
0
-3
-3
-3
-2
-2
-3
-3
-2
1
3
4
-1
-1
-3
F
-2
-2
-2
-4
-2
-3
-3
-3
-3
-3
-1
-3
-3
0
0
0
-1
6
3
1
Y
-2
-2
-2
-3
-2
-3
-2
-3
-2
-1
2
-2
-2
-1
-1
-1
-1
3
7
2
W
-2
-3
-3
-4
-3
-2
-4
-4
-3
-2
-2
-3
-3
-1
-3
-2
-3
1
2
11
I punteggi rappresentano il log-odds score per ciascuna sostituzione:
 logaritmo del rapporto tra la probabilità di osservare la sostituzione in
sequenze evolutivamente correlate e la probabilità di osservarla per caso
L’utilizzo della matrice di similarità appropriata per ciascuna
analisi è cruciale per avere buoni risultati.
Infatti relazioni importanti da un punto di vista biologico
possono essere indicate da una significatività statistica anche
molto debole.
Sequenze
poco divergenti

molto divergenti
BLOSUM80
BLOSUM62
BLOSUM45
PAM1
PAM120
PAM250
ALGORITMI PER L’ALLINEAMENTO DI
SEQUENZE
Algoritmo di Needleman & Wunsch
 allineamento globale
Algoritmo di Smith & Waterman
 allineamento locale
Utilizzano la PROGRAMMAZIONE
DINAMICA!
ALGORITMO DI NEEDLEMAN & WUNSCH
PER L’ALLINEAMENTO GLOBALE
• Questo metodo permette di determinare l’allineamento globale
ottimale attraverso un’interpretazione computazionale della
matrice dotplot: le sequenze vengono comparate attraverso una
matrice 2D, le celle rappresentanti matches hanno punteggio 1
(0 per i mismatches)
• L’allineamento ottimale viene calcolato ricorsivamente per
sottosequenze via via più lunghe, cosa possibile in virtù
dell’indipendenza e dell’additività dei punteggi di
“sottoallineamenti”
• L’algoritmo prevede una serie di somme successive dei
punteggi contenuti nelle celle, che dà luogo ad una matrice di
punteggi, la cui analisi permette la costruzione
dell’allineamento finale
ALGORITMO DI NEEDLEMAN & WUNSCH
PER L’ALLINEAMENTO GLOBALE
Questo metodo permette di determinare l’allineamento
globale ottimale attraverso un’interpretazione computazionale
della matrice dotplot.
Tre fasi
1. Determinazione residui identici
2. Per ogni cella, cercare il valore massimo nei
percorsi che dalla cella stessa portano
all’inizio della sequenza e dare alla cella il
valore del maximum scoring pathway
3. Costruire l’allineamento ottimale, andando
indietro dalla cella con il punteggio piu’ alto
fino all’inizio della matrice
Needleman-Wunsch Algorithm – FASE 1
Similarity values
• valore 1 oppure 0
ad ogni cella, in
base alla
similarita’dei
residui
corrispondenti
• Nell’esempio:
– match = +1
– mismatch = 0
M P R
P
1
B
R
1
C
K
C
R
1
N
J
C
J
A
C L C Q R J N C B A
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Needleman-Wunsch Algorithm – FASE 2
• Procedo da “in alto sinistra”
verso “in basso a destra” nella
matrice
• Per ogni cella, voglio
determinare il valore massimo
possibile per un allineamento
che termini in corrispondenza
della cella stessa
• Cerco le celle appartenenti alla
colonna e alla riga precedenti
a quelle della cella per trovare
il valore massimo in esse
contenuto
• Aggiungo questo valore al
valore della cella corrente
Needleman-Wunsch Algorithm – FASE 2
P
B
R
C
K
C
R
N
J
C
J
A
M
0
0
0
0
0
0
0
P
1
0
0
0
0
0
0
R
0
1
2
1
1
1
2
C
0
1
1
3
2
3
2
L
0
1
1
2
3
3
3
C
0
1
1
3
3
4
3
Q
0
1
1
2
3
3
4
R
0
1
2
2
3
3
?
J
0
1
1
2
3
3
N
0
1
1
2
3
3
C
0
1
1
3
3
4
B
0
2
1
2
3
3
A
0
1
2
2
3
3
1
1
1
1
1
1
Needleman-Wunsch Algorithm – FASE 3
Costruisco l’allineamento
• Il punteggio
dell’allineamento e’
cumulativo (posso sommare
lungo i percorsi nella
direzione stabilita)
• Il miglior allineamento ha il
massimo punteggio (ovvero
il massimo numero di
matches)
• Questo massimo numero di
matches si ritrovera’ nelle
ultime righe o colonne
• L’allineamento si costruisce
andando indietro alla
cella1,1 a partire dalla cella
imn basso a destra con
punteggio massimo.
MP-RCLCQR-JNCBA
| || | | | | |
-PBRCKC-RNJ-CJA
P
B
R
C
K
C
R
N
J
C
J
A
M
0
0
0
0
0
0
0
0
0
0
0
0
P
1
0
0
0
0
0
0
0
0
0
0
0
R
0
1
2
1
1
1
2
1
1
1
1
1
C
0
1
1
3
2
3
2
2
2
3
2
2
L
0
1
1
2
3
3
3
3
3
3
3
3
C
0
1
1
3
3
4
3
3
3
4
3
3
Q
0
1
1
2
3
3
4
4
4
4
4
4
R
0
1
2
2
3
3
5
4
4
4
4
4
J
0
1
1
2
3
3
4
5
6
5
6
5
N
0
1
1
2
3
3
4
6
5
6
6
6
C
0
1
1
3
3
4
4
5
6
7
6
6
B
0
2
1
2
3
3
4
5
6
6
7
7
A
0
1
2
2
3
3
4
5
6
6
7
8
Needleman-Wunsch Algorithm – FASE 3
P
B
R
C
K
C
R
N
J
C
J
A
M
0
0
0
0
0
0
0
0
0
0
0
0
P
1
0
0
0
0
0
0
0
0
0
0
0
R
0
1
2
1
1
1
2
1
1
1
1
1
MP-RCLCQR-JNCBA
| || | | | | |
-PBRCKC-RNJ-CJA
C
0
1
1
3
2
3
2
2
2
3
2
2
L
0
1
1
2
3
3
3
3
3
3
3
3
C
0
1
1
3
3
4
3
3
3
4
3
3
Q
0
1
1
2
3
3
4
4
4
4
4
4
R
0
1
2
2
3
3
5
4
4
4
4
4
J
0
1
1
2
3
3
4
5
6
5
6
5
N
0
1
1
2
3
3
4
6
5
6
6
6
C
0
1
1
3
3
4
4
5
6
7
6
6
B
0
2
1
2
3
3
4
5
6
6
7
7
A
0
1
2
2
3
3
4
5
6
6
7
8
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.
Local alignment:
homeodomains
of 5 proteins
The 5 proteins
show similarity
only in their
Homeodomain
regions
These domains are
combined with one
or more different
domains in
different proteins
An Introduction to Bioinformatics Algorithms
www.bioalgorithms.info
ALGORITMO DI SMITH & WATERMAN PER
L’ALLINEAMENTO LOCALE
Local Alignment: Example
Lo scopo degli algoritmi di allineamento locale di due sequenze
e’ trovare la regione più 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
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
Significatività di un allineamento
Sequenze allineate
Osservazione
Ipotesi alternative
ATTGCCCACGTTCGCGATCG
ATAGGGCACTTT-GCGATGA
** * *** ** *****
OMOLOGIA?
CASO?
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
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
WWW BLAST
http://blast.ncbi.nlm.nih.gov
WWW Blast: Risultati
…
Allineamento multiplo di sequenze
>Hs_jun-B
MCTKMEQPFYHDDSYTATGYGRAPGGLSLHDYKLLKPSLAVNLADPYRSLKAPGARGPGPEGGGGGSYFS
GQGSDTGASLKLASSELERLIVPNSNGVITTTPTPPGQYFYPRGGGSGGGAGGAGGGVTEEQEGFADGFV
KALDDLHKMNHVTPPNVSLGATGGPPAGPGGVYAGPEPPPVYTNLSSYSPASASSGGAGAAVGTGSSYPT
TTISYLPHAPPFAGGHPAQLGLGRGASTFKEEPQTVPEARSRDATPPVSPINMEDQERIKVERKRLRNRL
AATKCRKRKLERIARLEDKVKTLKAENAGLSSTAGLLREQVAQLKQKVMTHVSNGCQLLLGVKGHAF
>Pt
MCTKMEQPFYHDDSYTTTGYGRAPGGLSLHDYKLLKPSLAVNLADPYRSLKAPGARGPGPEGGGGGSYFS
GQGSDTGASLKLASSELERLIVPNSNGVITTTPTPPGQYFYPRGGGSGGGAGGAGGGVTEEQEGFADGFV
KALDDLHKMNHVTPPNVSLGATGGPPAGPGGVYAGPEPPPVYTNLSSYSPASASSGGAGAAVGTGSSYPT
TTISYLPHAPPFAGGHPAQLGLGRGASTFKEEPQTVPEARSRDATPPVSPINMEDQERIKVERKRLRNRL
AATKCRKRKLERIARLEDKVKTLKAENAGLSSTAGLLREQVAQLKQKVMTHVSNGCQLLLGVKGHAF
>Bt
MCTKMEQPFYHDDSYAAAGYGRTPGGLSLHDYKLLKPSLALNLSDPYRNLKAPGARGPGPEGNGGGSYFS
SQGSDTGASLKLASSELERLIVPNSNGVITTTPTPPGQYFYPRGGGSGGGAGGAGGGVTEEQEGFADGFV
KALDDLHKMNHVTPPNVSLGASGGPPAGPGGVYAGPEPPPVYTNLSSYSPASAPSGGAGAAVGTGSSYPT
ATISYLPHAPPFAGGHPAQLGLGRGASAFKEEPQTVPEARSRDATPPVSPINMEDQERIKVERKRLRNRL
AATKCRKRKLERIARLEDKVKTLKAENAGLSSTAGLLREQVAQLKQKVMTHVSNGCQLLLGVKGHAF
>Clf
MCTKMEQPFYHDDSYAAAGYGRAPGGLSLHDYKLLKPSLALNLADPYRSLKAPGARGPGPEGSGGSSYFS
GQGSDTGASLKLASSELERLIVPNSNGVITTTPTPPGQYFYPRGGGSGGGAGGAGGGVTEEQEGFADGFV
KALDDLHKMNHVTPPNVSLGASSGPPAGPGGVYAGPEPPPVYTNLNSYSPASAPSGGAGAAVGTGSSYPT
ATISYLPHAPPFAGGHPAQLGLGRGASTFKEEPQTVPEARSRDATPPVSPINMEDQERIKVERKRLRNRL
AATKCRKRKLERIARLEDKVKTLKAENAGLSSTAGLLREQVAQLKQKVMTHVSNGCQLLLGVKGHAF
Allineamento multiplo di sequenze
Clustal Omega
Jalview