blast.ppt [modalità compatibilità] - unibo.it · 31/05/2007 2. Identità di sequenza e identità...
Transcript of blast.ppt [modalità compatibilità] - unibo.it · 31/05/2007 2. Identità di sequenza e identità...
31/05/2007
1
Evoluzione Molecolare e omologiaEvoluzione Molecolare e omologia
Evoluzione: Mutabilità e Selezione Naturale
Le sequenze degli organismi attuali hanno avuto origine dall’evoluzione di sequenze ancestrali
Le sequenze genomiche cambiano continuamente in modo casuale
L’ambiente seleziona gli individui in base al loro fenotipo
Se il prodotto del gene modificato non è funzionale (perde struttura o funzione) l’individuo muore e la modifica non si trasmette
NB. Le mutazioni sono casuali? Almeno la loro velocità, non sempre: SOS polimerasi di Radman
Evoluzione Molecolare e omologiaEvoluzione Molecolare e omologia
Omologia
Due sequenze sono dette omologhe se hanno un ancestore comune
Ortologhe in due specie differenti Paraloghe all’interno della stessa specie (duplicazione genica)
Similarità
Due sequenze sono dette simili se condividono buona parte della sequenza (molti amminoacidi uguali o simili): concetto NON evolutivo, ma di confronto tra sequenze
Omologia e SimilaritàOmologia e Similarità
Sequenze omologhe sono sempre simili?
Dipende dal grado di divergenza
Sequenze simili sono sempre omologhe?
Sequenze differenti possono essere evolute convergentemente verso sequenze simili (es non su sequenze ali di uccelli e ali di verso sequenze simili (es., non su sequenze, ali di uccelli e ali di pipistrello sono evoluzioni convergenti, a partire da da rettili e da mammiferi)
Di principio similarità e omologia non coincidonoesattamente. Tuttavia se due sequenze sono molto similisono probabilmente omologhe.
Per ora misuriamo la similarità in termini di identità disequenza
Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale
Quando la similarità di sequenza implica similiarità strutturale?
Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale
2.5
0 5
1.5
2.0
1.0
of b
ackb
one
atom
s in
cor
e
1.0
0.6
0.8
0.4
tion
of re
sidu
es in
cor
e w
ith
RM
SD <
0.1
nm
Fino a quanto due sequenze simili danno strutture uguali?
Chothia, C. & Lesk, A. M. (1986). The relation between the divergence of sequence and structure in proteins. EMBO J. 5, 823-826.
0.0
0.5
100 050
Rm
sd o
Percent identical residues in core
0.0
0.2
100 050Percent identical residues in core
Frac
t
•2 proteine sono sovrapposte e si esamina la percentuale di identità nel nucleo sovrapposto•Proteine con identità maggiore del 60% hanno il 90% dei residui sovrapposti a meno di 0.1 nm
.
60
80
100identity
di s
eque
nza
(%)
Identità di sequenza implica identità strutturale
Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale
0
20
40
0 50 100 150 200 250Numero di residui allineati
Iden
tità
d
Identitàdi sequenza NON implica identità strutturale
Rost B (1999). The twilight zone of protein alignments. Protein Engineering 12, 85-94.
31/05/2007
2
.
Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale
Quindi due sequenze più lunghe di 100 residui, checondividano il 30 % dei residui, hanno struttura simile
Per sequenze più corte la percentuale di identità deveessere più alta
N N l h d àQuesto NON implica che sequenze con identità minoreabbiano strutture differentiEsempio: Mioglobina di capodoglio e emoglobina batterica:
RMSD = 0.19 nm, Identità: 14%
Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale
Per sequenze più lunghe di 100 residui
Midnight zone:
contiene la maggior
Twilight zone:
alto numero di falsi iti i
Safe zone:
nessun falso positivot tt l contiene la maggior
parte delle proteine strutturalmente simili
positivi(sequenza simile
struttura diversa)
tutte le sequenze simili hanno la
stessa struttura
20% 30%Percentuale di identità
Identità di sequenza e funzioneIdentità di sequenza e funzione
Il limite di identità che determina la stessa funzione è piùdifficile da stabilire e dipende criticamente dalladefinizione di funzione.
Per enzimi, la classe funzionale maggiore (ossidoreduttasi,isomerasi, ligasi, liasi….) viene conervata per sequenze conpiù del 30% di identità. La funzione più specifica richiede il60% d d à60% di identità
Aspartase [1JSW]
CO2-
C
H
NH3+
HH
OO-
CO2-
H
H-O2C+ NH3
Histidase [1B8F]
N NH
CO2-
H
HH+NH3
HH CO2
-
NHN+ NH3
δ2-Crystallin [1AUW]
Avian eye lens protein
Dati: Torsten SchwedeUniversità di Basilea
Allineamento di sequenzeAllineamento di sequenze
Problema: date due sequenze, confrontarle in modo darilevare la loro similarità
•Definire una distanza tra le sequenze
•Cercare un algoritmo per trovare l’allineamento a minimadistanza
•Studiare metodi per validare la significativitàdell’allineamento
Distanza tra sequenzeDistanza tra sequenze
Quali eventi consideriamo?
MutazioneVa definito un punteggio per la sostituzione dell’amminoacidoi con l’amminoacido j
Matrici di sostituzione s(i,j)
A: ALASVLIRLITRLYPA: ALASVLIRLITRLYPB: ASAVHLNRLITRLYP
∑= ),(),( ii BAsBAScore
La matrice di sostituzione riflette se una mutazione èmediamente compatibile col folding e col mantenimento dellafunzione
31/05/2007
3
Nucleotidi: identità
Amminoacidi: identità + somiglianzaVLSSADKTNVKAAWGKVGAHAGEYGAEALERMFL
AGGCTGACCTGGGAAGGGAAACTCTCAAAACCATAGGATGAGCT-GGAAGGATA-CTCTCAAAAACAT*** *** ** ******* ** ******** ***
Identità e similaritàIdentità e similarità
VLSAADKANIKAAW-KVGGQAGDHGAEALERMPL***:*** *:**** ***: **: ******** *
Derivazione degli score da allineamenti di sequenze Derivazione degli score da allineamenti di sequenze omologheomologhe
Vogliamo misurare la probabilità di mutazione di ogni tipodi amminoacido in un insieme di sequenze omologhe
Date (molte) coppie di sequenze correlate, misuriamo lafrequenza della sostituzione iA->jB o iB->jA (indipendente dalladirezione): Pij
Es:A: ALASVLIRAILRLYPB: ALAVLLNRLILRALP
P(A,A)= N(AA,AB)/N = 2/15
P(A,L)= P(L,A)= [N(LA,AB)+N(AA,LB)]/N = 2/15
Qual è la probabilità che la sostituzione i->j sia casuale (e quindi non significativa)?
La sostituzione è significativa?La sostituzione è significativa?
Es: 1° insieme di sequenze omologhe
A: ALASVLIRAILRLYP B: ALAVLLNRLILRALP
2° insieme di sequenze omologhe
La probabilità che questa sostituzione sia casuale dipende dalle frequenze di occorrenza dei singoli amminoacidi Pi e Pj
2 insieme di sequenze omologheA: LLLLAALLLALLALL B: LALLAALLAALLALL
P(A,L)= 2/15 in entrambi i casi. Sono ugualmente significativi?
Per determinare il grado di “non casualità” della sostituzione bisogna confrontare Pij con il prodotto PiPj
Es: 1° insieme di sequenze omologheA: ALASVLIRAILRLYP
Sostituzione iA -> jB casuale significa che i 2 eventi:E1 = (i in A) e E2 = (j in B) sono INDIPENDENTI
Confronto con l’ipotesi di indipendenzaConfronto con l’ipotesi di indipendenza
B: ALAVLLNRLILRALPP(A)= 6/30, P(L) =10/30P(A,L) = 2/15 > 1/15 = P(A)P(L): sostituzione FAVORITA
2° insieme di sequenze omologheA: LLLLAALLLALLALL B: LALLAALLAALLALL
P(A)= 10/30, P(L) =20/30P(A,L) = 2/15 < 2/9 = P(A)P(L): sostituzione SFAVORITA
Score di sostituzioneScore di sostituzione
Il rapporto rij = Pij/PiPj determina se la sostituzione i -> j è più o meno frequente di quanto ci si aspetterebbe casualmente.
Dato un allineamento tra due sequenze:
A: SLDPIKHTYRALMNVDSLRTFPILB: SFGIKKHTKLAKLPVDTIKSWPIL
SCORE di SOSTITUZIONE: s(i,j) =int[K log(Pij/PiPj)]
Il logaritmo rende la quantità additiva sulla sequenza
Minima distanza = Massimo score (s)
la probabilità di sostituzione A->B sarà data dal prodotto degli rij : rSS rLF rDG rPI rIK … (indipendenza delle posizioni)
31/05/2007
4
ESERCIZIOESERCIZIO
Calcolare la matrice di sostituzione a partire dalle seguenti sequenze allineate
ACAGGTGGACCTACTGGTCGACTT
CTATATGGCTATATGGCCGGATCG
Matrici di sostituzione: PAMMatrici di sostituzione: PAM
In base a questo concetto, differenti matrici possonoessere derivate.La differenza fondamentale sta nell’insieme di allineamenticonsiderati per costruire le matrici.
PAMx: (Point Accepted Mutation). Numero di eventimutazionali pari a x%.Si costruisce la matrice:Si costruisce la matrice:
A1ij = P(j|i) = N(i,j)/N(i)
per sequenze con 1% di mutazioni.
PAM 1 = Log(A1ij /Pi)
Anij=(A1
ij)n
Es: n=2 P(i|j) = Πl P(i|l) P(l|j)
Matrici di sostituzione: PAMMatrici di sostituzione: PAM
Per derivare gli score relativi a sequenze in cui siano avvenutin eventi mutazionali ogni 100 residui:
NOTA BENE: n % eventi mutazionali: numero di mutazioni, NON di residui mutati. Possono essere rimutati posizioni già mutate. 100 eventi mutazionali indipendenti ogni 100 residui lasciano alcune posizioni invariate
PAM n = Log(Anij /Pi)
Relazione tra PAM e identità tra due sequenzeRelazione tra PAM e identità tra due sequenze
Il numero di eventi mutazionali (PAM) è differente dal numero di residui differenti tra due sequenze, quando le mutazioni si accumulano.
PAM10PAM10
Matrice molto stringente: nessun valore positivo fuori diagonale
PAM160PAM160
Iniziano valori positivi fuori diagonale: residui con valori di sostituzione positivi sono detti SIMILI
31/05/2007
5
PAM250PAM250
Molto usata
PAM500PAM500
Matrici di sostituzioneMatrici di sostituzione
Le matrici PAM ricavano ipotesi sulle mutazioni in sequenzelontane a partire dalle mutazioni osservate in sequenze moltosimili. Ipotesi molto stretta.
BLOSUMx: Famiglia di matrici ricavate direttamente dablocchi di allineamenti di sequenze con identità maggiore alx%.
Per sequenze molto relate vanno usate PAM basse o BLOSUMalte. Per sequenze lontane, viceversa.
BLOSUM62BLOSUM62
Molto usata
BLOSUM90BLOSUM90 BLOSUM30BLOSUM30
31/05/2007
6
Distanza tra sequenzeDistanza tra sequenze
Quali eventi consideriamo?
MutazioneDelezione e InserzioneAlcuni amminoacidi possono essere stati deleti o inseriti nelcorso dell’evoluzione
A: ALASVLIRLIT--YPB: ASAVHL ITRLYPB: ASAVHL---ITRLYP
)2()3(),(),( σσ ++= ∑ ii BAsBAScoreIl punteggio (negativo) di un gap dipende solo dal numero diposizioniσ(n) = -nd lineareσ(n) = -d - (n-1)e affine (d: apertura, e: estensione)
N.B. Tutti i punteggi sono indipendenti dalla posizionelungo la sequenza
Allineamento tra sequenzeAllineamento tra sequenze
Date due sequenze, qual è l’allineamento a punteggiomassimo?
Soluzione naïf: provare tutti gli allineamenti possibili escegliere quello a punteggio maggiore!
Per ogni allineamento, possiamo infatti calcolare il punteggiotramite la formulatramite la formula
)(),(),( gapgapi
ii nBAsBAScore σ∑∑ +=
Quanti sono i possibili allineamenti di due sequenze?Quanti sono i possibili allineamenti di due sequenze?
Scrivere TUTTI i possibili allineamenti senza gap interni delle sequenze:
A: tcaB: ga
Scrivere TUTTI i possibili allineamenti con gap p g pdelle medesime sequenze
Scrivere i punteggi di allineamento per ognuno degli allineamenti secondo la seguente matrice con penalità di gap LINEARE (d=2) A C T G
A 2 -1 -1 0C 2 0 -1T 2 -1G 2
Quanti sono i possibili allineamenti di due sequenze?Quanti sono i possibili allineamenti di due sequenze?
Caso senza Gap interni
--tca -tca tca tca tca- tca--ga--- ga-- ga- -ga --ga ---ga
Date due sequenze di lunghezza m e n, il numero dei possibili scorrimenti differenti è m +n
Uguale al primo
Caso con gap interni
--tca -tca -tca -tca t-caga--- ga-- g-a- g--a ga--gatca gtaca gtcaa gtcaa tgaca22111 21211 21121 21112 12211
tca tca tc-a tca tca-
Quanti sono i possibili allineamenti di due sequenze?Quanti sono i possibili allineamenti di due sequenze?
ga- g-a -ga- -ga --gatgcaa tgcaa tcgaa tcgaa tcaga12121 12112 11221 11212 11122
I possibili allineamenti sono uguali ai possibili modi diintercalare le due sequenze, mantenendo l’ordineDate due sequenze di lunghezze n e m, i possibili allineamenti sono (m+n)!/n!m!
Per n=m=80 ho 9•1042 possibili allineamenti !!!!!!!
Il calcolo per intero di tutti gli allineamenti è sovrabbondante
ALSKLASPALSAKDLDSPALSALSKIADSLAPIKDLSPASLT
Algoritmi di programmazione dinamica: idea baseAlgoritmi di programmazione dinamica: idea base
ALSKLASPALSAKDLDSPAL-SALSKIADSLAPIKDLSPASLT-
I due allineamenti sono per la maggior parte uguali.Lo score è additivo lungo l’allineamento. Col metodo naïf laprima parte dell’allineamento viene ricalcolata!
Si possono memorizzare i punteggi degli allineamenti parziali
31/05/2007
7
Complessità computazionaleComplessità computazionale
Numero di operazioni necessario per ottenere un risultato seguendo un algoritmo
Algoritmo naïfDate due sequenze di lunghezza n dobbiamo calcolare (2n)!/(n !)2 punteggi di allineamento. Ognuno richiede dalle n alle 2n operazioni.
Poiché n ! ≈ n n (2π n)1/2 e-n
Complessità ≈ O(22n n 1/2)
Algoritmo Needleman-WunschVanno calcolati (n +1)2 valori della matrice. Ognuno richiede 4 operazioni:Complessità ≈ (n 2)
Allineamenti globali e localiAllineamenti globali e locali
Algoritmi differenti, ma sostanzialmente simili, cercano similarità GLOBALI confrontando intere sequenze o similarità LOCALI, cercando i segmenti che meglio si allineano all’interno di due sequenze
L’annotazione si basa spesso sulla ricerca di domini comuni e elementi funzionali conservati…
Significatività di un allineamentoSignificatività di un allineamento
Dato un allineamento (globale o locale) che abbia ottenuto un punteggio S, come valutare se è significativo?Come sono distribuiti i punteggi di allineamenti di sequenze casuali? Con 100,000 allineamenti di sequenze scorrelate e randomizzate:
Gli allinementi significativi sono qua!
Score
Occ
orre
nza
Z=(S-<S>)/σs
S=Punteggio di allineamento<S>=Media dei punteggi di allineamento su un insieme randomσs=Deviazione dei punteggi di allineamento su un insieme random
Accuratezza dell’allineamento
ZZ--scorescore
Accuratezza dell allineamento
Z<3 non significativo
Lo Z-score di questo allineamento locale è 7.5 su 54 residuiL’identità è 25.9%. Le sequenze sono completamente differenti in struttura secondaria
Quanto è affidabile lo ZQuanto è affidabile lo Z--score?score?
Citrate synthase (2cts) vs transthyritin (2paba)
EE--valuevalue
Numero atteso di allineamenti random con punteggiomaggiore o uguale a un punteggio dato (s)
E’ reso possibile dal calcoli statistici
E=Kmn e-λs
m, n: lunghezze delle due sequenzeg qK, λ: Costanti di “scaling”
Il numero di allineamenti random a punteggio maggiore di scresce col crescere delle lunghezze delle sequenze (o deidata base con cui confrontiamo una sequenza) e calaesponenziamente al crecere di s
31/05/2007
8
La probabilità P di trovare un allineamento con score maggiore o uguale ad un certo valore S è data da:
( ) Ee=xSP −−≥ 1( ) exSP ≥ 1
Accuratezza dell’allineamentoLa significatività dell’E-value dipende dalla lunghezza della banca dati considerata. Per un numero di sequenze pari a quello di SwissProt
E> 10-1 non significativoE 10 3 i ifi ti
EE--valuevalue
E < 10-3 significativo
Ricerca di similarità in Banche DatiRicerca di similarità in Banche Dati
Data una sequenza, cercare se esistono sequenze simili in una banca dati
Di principio si potrebbero fare allineamenti tra la sequenza target e TUTTE le sequenze
Le sequenze da allineare sono troppe, e il processo non è fattibile in tempi brevi nemmeno usando l’algoritmo di NWfattibile in tempi brevi nemmeno usando l algoritmo di NW
Si utilizzano algoritmi euristici, che non assicurano il raggiungimento dell’allineamento ottimo
FASTABLAST
FASTAFASTA
Data una sequenza (Query), viene divisa in “parole” lunghe k-tup (generalmente k-tup = 2 per proteine, 6 per DNA)
ADKLPTLPLRLDPTNMVFGHLRI
Parole (indicizzate per posizione):AD, DK, KL, LP, PT, TL, LP, PR, RL, …,…,1 2 3 4 5 6 7 8 9 ….
Lo stesso elenco di parole indicizzato è compilato per ogni sequenza (Subject) del data base in cui si cercano sequenze.
E’ molto rapida la ricerca di parole uguali tra Query e Subject. La differenza degli indici determina la diagonale
FASTAFASTA
Query
Identificazione delle identità di “parole”: identità consecutive danno origine a diagonali più lungheSi selezionano le sequenze candidate
FASTAFASTA
Query
I punteggi delle regioni più lunghe sono valutati con una matrice di score (PAM o BLOSUM)
31/05/2007
9
FASTAFASTA
Query
Vengono cercate regioni ad alta similarità su diagonali vicine
Query
FASTAFASTA
Si procede ad un allineamento esatto (Smith-Waterman) su una banda stretta attorno alla diagonale di maggior similarità (solitamente banda larga attorno ai 32 residui)
Sequence similarity with FASTA BLASTBLAST
Data un data base di sequenze, questo viene indicizzato:per ogni tripletta di residui consecutivi si memorizza in quali sequenze e in quali posizioni questa tripletta viene trovata.
AAAAACAADAADACA.........
BLASTBLAST
Data una sequenza (Query), viene divisa in “parole” lunghe W (generalmente W = 3 per proteine)
LSHLPTLPLRLDPTNMVFGHLRI
LSH, SHL, HLP, LPT, PTL, TLR, …,…,
Per ognuna vengono generate le parole affini secondo la BLOSUM62 l t i T (T 11 13)BLOSUM62: parole con punteggio > T (T = 11--13)
LSH 16 ISH 14MSH 14VSH 13LAH 13LTH 13LNH 13
The BLAST Algorithm:Seeding (W and T)
Sequence 1
RGD 17
KGD 14
QGD 13
RGE 13
EGD 12
HGD 12
NGD 12
BLOSUM62 neighborhood
of RGD
• Speed gained by minimizing search space• Alignments require word hits• Neighborhood words• W and T modulate speed and sensitivity
Sequence 1
word hits
NGD 12
RGN 12
AGD 11
MGD 11
RAD 11
RGQ 11
RGS 11
RND 11
RSD 11
SGD 11
TGD 11
T=12
31/05/2007
10
The BLAST Algorithm:2-hit Seeding
• Alignments tend to have multiple word hits.
• Isolated word hits are frequently false
word clustersisolated words
frequently false leads.
• Most alignments have large ungapped regions.
• Requiring 2 word hits on the same diagonal (of 40 aa for example), greatly increases speed at a slight cost in sensitivity.
BLASTBLAST
Per ognuna delle parole affini vengono recuperate le sequenze del data base che la contengono (secondo l’indicizzazione)
La corrispondenza viene estesa (senza gap) a destra e a sinistra fino a che lo score rimane superiore a una soglia S. Durante l’estensione vengono tollerate perdite di score fino a una tolleranza X
Query:83 LMVAISNVGTDTLSHLEAQNKIKSASHNLSLTLQKSK+++AIS GT+++SH +AQ++IK+AS+ L L + ++
Subject:48 VILAISGFGTESMSHADAQDRIKAASYQLCLKIDRAE
HSP
The BLAST Algorithm: Extension
extension
alignment
• Alignments are extended from seeds in each direction.
• Extension is terminated when the maximum score drops below X.
The quick brown fox jumps over the lazy dog.The quiet brown cat purrs when she sees him.
X =
length of extension
trim to max
Text examplematch +1mismatch -1no gaps
>gi|23098447|ref|NP_691913.1| (NC_004193) 3-oxoacyl-(acyl carrier
protein) reductase [Oceanobacillus iheyensis]Length = 253
Score = 38.9 bits (89), Expect = 3e-05Identities = 17/40 (42%), Positives = 26/40 (64%)Frame = -1
Query: 4146 VTGAGHGLGRAISLELAKKGCHIAVVDINVSGAEDTVKQI 4027VTGA G+G+AI+ A +G + V D+N GA+ V++I
Sbjct: 10 VTGAASGMGKAIATLYASEGAKVIVADLNEEGAQSVVEEI 49
Sequence similarity with BLAST (Basic Local Alignment Search Tool)
31/05/2007
11
BLAST: i 4 parametri fondamentali
W: word size, maggiore è il numero, minore è il numero di parole generate, minore è il tempo di esecuzione. Ma la sensibilità decresce sensibilmente.
T: threshold, minore è il numero, maggiore è il numero di w-mers inclusi nella lista, maggiore è il tempo di esecuzione Si ha però un incremento di sensibilitàesecuzione. Si ha però un incremento di sensibilità.
S: score, minore è il numero, maggiore sarà la lunghezza degli HSP
X: maggiore è il numero, più estesamente sarà osservato l’intorno di una HSP, aumentando il tempo di esecuzione.
Le versioni di BLAST
blastp: cerca similarità in banche dati proteiche a partire da una query di amino acidi.
blastn: cerca similarità in banche dati di nucleotidi a partire da una query di nucleotidi.
blastx: cerca similarità in banche dati proteiche a partire d un qu r di nucl tidi ch vi n tr d tt in tutti i da una query di nucleotidi che viene tradotta in tutti i frame.
tblastn: cerca similarità in banche dati di nucleotidi a partire da una query di amino acidi, traducendo in amino acidi tutti i subject della banca dati, in tutti frame.
tblastx: cerca similarità in banche dati di nucleotidi a partire da una query di nucleotidi, traducendo in amino acidi tutti i subject della banca dati
The 5 Standard BLAST ProgramsProgram Database Query Typical Uses
BLASTN Nucleotide Nucleotide Mapping oligonucleotides, amplimers, ESTs, and repeats to a genome. Identifying related transcripts.
BLASTP Protein Protein Identifying common regions between proteins. Collecting related proteins for phylogenetic analysis.
BLASTX Protein Nucleotide Finding protein-coding genes in genomic DNA.
TBLASTN Nucleotide Protein Identifying transcripts similar to a known protein (finding proteins not yet in GenBank). Mapping a protein to genomic DNA.
TBLASTX Nucleotide Nucleotide Cross-species gene prediction. Searching for genes missed by traditional methods.
gapped-blast: porta avanti la fase di estensione delle HSP considerando la possibilità di inserzione dei gap.
PSI-BLAST: effettua una ricerca iterativa utilizzando le HSP per generare dei profili caratteristici della query.
PHI-BLAST: estensione di PSI-BLAST per la ricerca in banca dati di pattern proteici più che di query esattebanca dati di pattern proteici più che di query esatte.
BL2SEQ: adattamento di blast per l’allineamento a coppie
MegaBLAST: può concatenare molte queries tra loro per minimizzare il tempo di esecuzione dovuto a sequenze query troppo lunghe (è adatto a sequenze nucleotidiche molto simili tra loro)
FASTA vs BLAST
simili in strategia, molto diversi nei contenuti
Cerca parole “esatte”: può perdere similarità significative
supera il problema grazie all’introduzione dei w-mersN.B. i w-mers sono basati su una matrice quindi può
d h h i accadere che match esatti score S inferiori rispetto a match non esatti
Esempio, con Blosum62 - il match perfetto AIS-AIS dà score 12 - lo score inesatto LSH-MSH dà score 14
il mismatch è premiato più del match
FASTA vs BLAST
più tollerante per sequenze che presentano gaps, il loro inserimento è previsto già nelle prime fasi
inserisce i gaps solo in fase di allungamento
31/05/2007
12
La presenza nelle sequenze di regioni molto ripetitive (polyQ, stratch idrofobici,…) può falsare i risultati della ricerca: si ritrovano altre regioni simili in proteine non imparentate:
Sequenze “Low complexity”
Di default viene utilizzato il filtro per le regioni low complexity: nell’allineamento queste regioni vengono indicate come XXXXXX
60
Query: 61 XXXXGVNHLHGISSELVNXXXXXXXXXXXXXXXXXRRKIERDPNAPKKPLTVFFAYSAYV 120GVNHLHGISSELVN RRKIERDPNAPKKPLTVFFAYSAYV
Sbjct: 61 TLTSGVNHLHGISSELVNPIDDDKDAIIAAPVKAVRRKIERDPNAPKKPLTVFFAYSAYV 120
The best scores are: opt bits E(787946)gi|6320379|ref|NP_010459.1| High mobility group (HMG)-like protein; ( 246) 1581 320 2.7e-86 gi|65265|emb|CAA42523.1| (X59863) a xenopus upstream binding factor ( 701) 196 48 0.00053 gi|104205|pir||S17196 transcription factor UBF2 - African clawed fro ( 701) 196 48 0.00053 gi|136657|sp|P25980|UBF2_XENLA NUCLEOLAR TRANSCRIPTION FACTOR 2 (UPS ( 701) 196 48 0.00053 gi|729731|sp|P40626|HMGB_TETTH HIGH-MOBILITY-GROUP PROTEIN B gi|1023 ( 143) 180 44 0.0013 gi|7492240|pir||T38936 non-histone chromosomal protein high mobility ( 108) 176 43 0.0018 gi|1079088|pir||S47596 HMG1-like protein - fruit fly (Drosophila mel ( 216) 180 44 0.0018 gi|1174454|sp|P41848|SSRP_CAEEL PROBABLE STRUCTURE-SPECIFIC RECOGNIT ( 697) 186 46 0.002 gi|15218011|ref|NP_173492.1| high mobility group protein (HMG1), put ( 502) 184 45 0.0021
gi|2137073|pir||JC5112 ribosomal transcription factor UBF1 - Chinese ( 764) 176 44 0.0086 gi|1045008|gb|AAB38418.1| (L42570) putative [Cricetulus griseus] ( 764) 176 44 0.0086 i|85591| i ||A24019 hi t h l t i HMG T t t (f ( 172) 167 42 0 0089
score significativitàscoreLista
Ricerca FASTA
gi|85591|pir||A24019 nonhistone chromosomal protein HMG-T - trout (f ( 172) 167 42 0.0089 gi|12836542|dbj|BAB23701.1| (AK004961) putative [Mus musculus] ( 752) 175 44 0.0097 gi|112465|pir||B40439 UBF transcription factor, short form - rat ( 727) 174 44 0.011 gi|14772527|ref|XP_008365.2| hypothetical protein XP_008365 [Homo sa ( 727) 174 44 0.011 gi|14754719|ref|XP_047946.1| high-mobility group 20A [Homo sapiens] ( 313) 167 42 0.014 gi|730842|sp|Q04931|SSRP_RAT STRUCTURE-SPECIFIC RECOGNITION PROTEIN ( 561) 170 43 0.015 gi|15022805|ref|NP_080088.1| high mobility group 20A [Mus musculus] ( 346) 167 42 0.016
>>gi|6320379|ref|NP_010459.1| High mobility group (HMG)-like protein; Hmo1p (246 aa)
10 20 30 40 50 60 70 80
QUERY MTTDPSVKLKSAKDSLVSSLFELSKAANQTASSIVDFYNAIGDDEEEKIEAFTTLTESLQTLTSGVNHLHGISSELVNPI
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
gi|632 MTTDPSVKLKSAKDSLVSSLFELSKAANQTASSIVDFYNAIGDDEEEKIEAFTTLTESLQTLTSGVNHLHGISSELVNPI
10 20 30 40 50 60 70 80
Allineamenti
Score ESequences producing significant alignments: (bits) Valuegi|6320379|ref|NP_010459.1| High mobility group (HMG)-like ... 332 3e-90gi|7446209|pir||T12113 transcription factor - fava bean >gi... 50 1e-05gi|1731110|sp|Q09390|YR44_CAEEL HYPOTHETICAL 23.8 KD PROTEI... 48 8e-05gi|14550383|gb|AAK67237.1|U22831_8 (U22831) Hypothetical pr... 48 1e-04gi|4507241|ref|NP_003137.1| structure specific recognition ... 48 1e-04gi|11359753|pir||T43009 HMG protein 1.2 - Caenorhabditis el... 47 1e-04gi|14550384|gb|AAK67238.1|U22831_9 (U22831) Hypothetical pr... 47 1e-04gi|12857100|dbj|BAB30892.1| (AK017716) putative [Mus musculus] 46 2e-04gi|15022805|ref|NP_080088.1| high mobility group 20A [Mus m... 46 3e-04gi|8922633|ref|NP_060670.1| high-mobility group 20A [Homo s... 46 3e-04
Ricerca BLAST
gi|7446219|pir||JC6179 dorsal switch protein 1 - fruit fly ... 46 3e-04gi|1079089|pir||S50068 nonhistone chromosomal protein HMG1-... 46 3e-04gi|136657|sp|P25980|UBF2_XENLA NUCLEOLAR TRANSCRIPTION FACT... 45 4e-04gi|65265|emb|CAA42523.1| (X59863) a xenopus upstream bindi... 45 4e-04gi|587104|emb|CAA57212.1| (X81456) unnamed protein product ... 45 4e-04gi|3915056|sp|Q91731|SX11_XENLA TRANSCRIPTION FACTOR SOX-11... 37 0.11gi|14786454|ref|XP_030626.1| hypothetical protein XP_030626... 37 0.11gi|1431689|pdb|1AAB| Nmr Structure Of Rat Hmg1 Hmga Frag... 37 0.12gi|12836358|dbj|BAB23621.1| (AK004857) putative [Mus musculus] 37 0.13gi|576153|pdb|1HME| High Mobility Group Protein Fragment... 37 0.13gi|7446228|pir||T03375 high mobility group protein HMGd1 - ... 37 0.17gi|13559761|gb|AAK29965.1| (AC024859) Hypothetical protein ... 37 0.18
Allineamenti>gi|6320379|ref|NP_010459.1| High mobility group (HMG)-like protein; Hmo1p [SaccharomycesLength = 246
Score = 332 bits (850), Expect = 3e-90Identities = 191/220 (86%), Positives = 191/220 (86%)
Query: 1 MTTDPSVKLKSAKDSLVSSLFELSKAANQTASSIVDFYNAIGDDEEEKIEAFXXXXXXXX 60MTTDPSVKLKSAKDSLVSSLFELSKAANQTASSIVDFYNAIGDDEEEKIEAF
Sbjct: 1 MTTDPSVKLKSAKDSLVSSLFELSKAANQTASSIVDFYNAIGDDEEEKIEAFTTLTESLQ 60
Query: 61 XXXXGVNHLHGISSELVNXXXXXXXXXXXXXXXXXRRKIERDPNAPKKPLTVFFAYSAYV 120GVNHLHGISSELVN RRKIERDPNAPKKPLTVFFAYSAYV
Sbjct: 61 TLTSGVNHLHGISSELVNPIDDDKDAIIAAPVKAVRRKIERDPNAPKKPLTVFFAYSAYV 120......
Lambda K H
0.308 0.127 0.355
Gapped
Lambda K H
0.267 0.0410 0.140
Matrix: BLOSUM62
Gap Penalties: Existence: 11, Extension: 1
Statistiche basate su valori di λ e k precacolati per determinate matrici, composizione in residui e penalità per gap
E(DNA) vs E(Proteine)Valori attesi con la sequenza di DNA [Score, E(DNA)] e la sequenza proteica [E(prot)] per una ricerca in bancadati effettuata con la glutatione transferasi (GST) di drosofila(GST) di drosofila.
La ricerca che utilizza la sequenza proteica fornisce risultati più significativi ed è in grado di individuare omologhi della GST al di fuori del gruppo degli insetti
Allineamento di tutte le sequenze Allineamento di tutte le sequenze
ATTENZIONE: Non è allineamento multiplo ottimale
31/05/2007
13
1 Y K D Y H S - D K K K G E L - -2 Y R D Y Q T - D Q K K G D L - -3 Y R D Y Q S - D H K K G E L - -4 Y R D Y V S - D H K K G E L - -5 Y R D Y Q F - D Q K K G S L - -6 Y K D Y N T - H Q K K N E S - -7 Y R D Y Q T - D H K K A D L - -8 G Y G F G - - L I K N T E T T K 9 T K G Y G F G L I K N T E T T K10 T K G Y G F G L I K N T E T T K
A 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0C 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0D 0 0 70 0 0 0 0 60 0 0 0 0 20 0 0 0E 0 0 0 0 0 0 0 0 0 0 0 0 70 0 0 0F 0 0 0 10 0 33 0 0 0 0 0 0 0 0 0 0
Position
Profilo di sequenzaProfilo di sequenza
F 0 0 0 10 0 33 0 0 0 0 0 0 0 0 0 0G 10 0 30 0 30 0 100 0 0 0 0 50 0 0 0 0H 0 0 0 0 10 0 0 10 30 0 0 0 0 0 0 0K 0 40 0 0 0 0 0 0 10 100 70 0 0 0 0 100I 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0L 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 0M 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 0N 0 0 0 0 10 0 0 0 0 0 30 10 0 0 0 0P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Q 0 0 0 0 40 0 0 0 30 0 0 0 0 0 0 0R 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0S 0 0 0 0 0 33 0 0 0 0 0 0 10 10 0 0T 20 0 0 0 0 33 0 0 0 0 0 30 0 30 100 0V 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0W 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0Y 70 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0
Utilità del profilo di sequenzaUtilità del profilo di sequenza
Il profilo di sequenza dà una descrizione complessiva di tutte le sequenze:
evidenzia le zone più conservate o le mutazioni più frequentiposizione per posizione
Allineare una sequenza contro un profilo
I parametri di un allineamento sono generalmente identiciper tutte le posizioni. Allineare contro un profilo pesadifferentemente le mutazioni nelle differenti posizioni
Dal profilo di sequenza possiamo ricavare una matrice di Dal profilo di sequenza possiamo ricavare una matrice di score dipendente dalla posizionescore dipendente dalla posizione
A 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 C 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 D 0 0 70 0 0 0 0 60 0 0 0 0 20 0 0 0 E 0 0 0 0 0 0 0 0 0 0 0 0 70 0 0 0 F 0 0 0 10 0 33 0 0 0 0 0 0 0 0 0 0 G 10 0 30 0 30 0 100 0 0 0 0 50 0 0 0 0 H 0 0 0 0 10 0 0 10 30 0 0 0 0 0 0 0 K 0 40 0 0 0 0 0 0 10 100 70 0 0 0 0 100 I 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 L 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 0 M 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 0 N 0 0 0 0 10 0 0 0 0 0 30 10 0 0 0 0 P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Q 0 0 0 0 40 0 0 0 30 0 0 0 0 0 0 0 R 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Stimo se ogni residuo in ogni posizione è più o meno presente di quanto ci si aspetterebbe random: confronto la probabilità desunta dal profilo con la probabilità a priori di avere l’amminoacido in questione
SAA (pos) = int [K log (ProfAA(pos)/PAA) ]
R 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 S 0 0 0 0 0 33 0 0 0 0 0 0 10 10 0 0 T 20 0 0 0 0 33 0 0 0 0 0 30 0 30 100 0 V 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 W 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y 70 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0
PSIPSI--BLASTBLASThttp://www.ncbi.nlm.nih.gov/BLAST/
Sequenza
D B
BLASTProfilo delle
sequenze Data Base
qrintracciate
PSI-BLAST
Fino a convergenza
(1) PSI-BLAST takes as an input a single protein sequence and compares it to a protein database, using the gapped BLAST program
(2) The program constructs a multiple alignment, and then a profile, from any significant local alignments found. The original query sequence serves as a template for the multiple alignment and profile, whose lengths are identical to that of the query. Different numbers of sequences can be aligned in different template positions
(3) The profile is compared to the protein database, again seeking local
The design of PSI-BLAST
( ) p f p p , g galignments. After a few minor modifications, the BLAST algorithm can be used for this directly.
(4) PSI-BLAST estimates the statistical significance of the local alignments found. Because profile substitution scores are constructed to a fixed scale, and gap scores remain independent of position, the statistical theory and parameters for gapped BLAST alignments remain applicable to profile alignments.
(5) Finally, PSI-BLAST iterates, by returning to step (2), an arbitrary number of times or until convergence.