Allineamento e similarità di sequenze PDF

Allineamento e similarità di sequenze Allineamento di Sequenze  L’allineamento tra due o più sequenza può aiutare a trovare regioni simili per le quali si può supporre svolgano la stessa funzione;  La similarità tra due o più sequenza può essere definita in...

Allineamento e similarità di sequenze Allineamento di Sequenze  L’allineamento tra due o più sequenza può aiutare a trovare regioni simili per le quali si può supporre svolgano la stessa funzione;  La similarità tra due o più sequenza può essere definita in base a una funzione distanza: Tanto più simili sono le sequenze, tanto meno distanti sono;  Esistono diversi algoritmi di allineamento ciascuno dei quali definisce una funzione distanza;  Dato un allineamento possiamo assegnare uno Score che indica il grado di similarità delle due sequenze. Confrontare sequenze Il confronto fra sequenze, nucleotidiche o aminoacidiche, è uno dei compiti fondamentali della bioinformatica. Perché è possibile confrontare sequenze? Perché generalmente in natura le strutture molecolari non vengono create ex-novo ma per modificazione di modelli preesistenti. Obiettivi del confronto: – Filogenesi molecolare – Evoluzione dei singoli genomi – Caratterizzazione di proteine con funzione sconosciuta Confrontare sequenze (2) Filogenesi molecolare La filogenesi molecolare, attraverso il paragone tra sequenze nucleotidiche o aminoacidiche, consente di costruire alberi filogenetici che illustrino le distanze ed i rapporti evolutivi tra le molecole analizzate. A differenza della filogenesi classica, che prende in considerazione le caratteristiche morfologiche dei vari organismi per delinearne l’evoluzione, la filogenesi molecolare non consente lo studio evolutivo degli organismi ma permette di identificarne le relazioni evolutive molecolari. Caratterizzazione di proteine con funzione ignota Il confronto di una proteina a funzione ignota con una famiglia di proteine a funzione nota può permettere di formulare ipotesi sulla funzione della prima.  Similarità e omologia Tra due o più sequenze può esserci un certo grado di similarità. Tale similarità può essere misurata in modi diversi, anche a seconda del tipo di sequenze in esame (Nucleotidiche o aminoacidiche). A volte una similarità tra sequenze implica una similarità strutturale e, conseguentemente, una similarità funzionale. L’omologia tra sequenze indica invece una comune origine evolutiva tra di esse. Due sequenze si dicono omologhe quando discendono entrambe da una sequenza ancestrale comune. Due o più sequenze simili tra loro possono quindi essere omologhe o meno.   OMOLOGIA= indica che due entità (es. 2 sequenze) hanno una stessa origine filogenetica, cioè derivano da un antenato comune. È un carattere QUALITATIVO.  SIMILITUDINE (analogia)= indica che due entità (es. 2 sequenze), in relazione ad un certo criterio comparativo, hanno un certo grado di somiglianza. È un carattere QUANTITATIVO. SIMILARITA’: é un dato che prescinde da eventuali ipotesi sulla causa della similarità stessa. Ad esempio: l’ala di un uccello e l’ala di un pipistrello si sono evolute indipendentemente e di conseguenza non sono omologhe. La similarita’ osservata tra due sequenze PUO’ indicare che esse siano omologhe, cioe’ evolutivamente correlate La similarita’ tra sequenze si osserva, l’omologia tra sequenze si puo’ ipotizzare in base alla similarita’ osservata.  Omologia e Analogia, Ortologia e Paralogia OMOLOGIA (ANTENATO COMUNE) ORTOLOGIA PARALOGIA Elementi omologhi derivanti da Elementi omologhi derivanti da un un Processo di speciazione Processo di duplicazione genica per esempio, la catena  dell’ emoglobina e’ un paralogo della catena  dell’ emoglobina e della mioglobina, dal momento che ambedue si sono evolute dallo stesso gene ancestrale attraverso ripetuti eventi di duplicazione genica.  Allineamento di sequenze Per poter procedere al confronto tra sequenze nucleotidiche o tra sequenze proteiche è necessario che queste sequenze vengano allineate. Questo è un esempio di allineamento multiplo di 5 brevi sequenze aminoacidiche.  Allineamento di Sequenze  GLOBALE: Si cerca la corrispondenza ottimale tra tutti gli amminoacidi (nucleotidi) di entrambe le sequenze.  LOCALE: Si cerca di individuare regioni locali di similarità. Globale Globale LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||. ||. || || ||.|.|.|.| || || || || || || || TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG Locale Locale LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||||||||.|||| ||||||||.|||| TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG Modularità... Allineamento A coppie(Pairwise Alignment) – Matrici Dot Plot  Si crea una matrice in cui vengono confrontati tutti i possibili appaiamenti di ogni carattere delle due sequenze da allineare.  Si riempie la matrice, annerendo le caselle che hanno nella corrispondente riga e colonna la stessa lettera.  Il programma  DOTLET (http://myhits.isb-sib.ch/cgi-bin/dotlet) , date due sequenze in input permette di disegnare facilmente la relativa matrice Dot Plot.  https://dotlet.vital-it.ch/ MIRROR Allineamento Pairwise – Matrici Dot Plot margaretqaklerdayhqff m a * * * r * * ** Duplicazione g * a * * * *Inversione r e * * * * * t d * * a * * * y h Similarità * * q f ** f * Allineamento Pairwise – Matrici Dot Plot FILTRAGGIO –Window Size  E’ chiaro che il numero di punti della matrice è influenzato dalla natura della sequenza;  Se confrontiamo due sequenze di nucleotidi (o proteine) costituite da 100 residui, assumendo che ciascun nucleotide (o aminoacido) occorra con la stessa probabilità, il numero totale di punti della matrice sarà mediamente pari a 2500 (500 nel caso di aminoacidi) su 10000 celle totali;  Quando confrontiamo sequenze nucleotidiche il rumore di fondo sara più elevato;  Possiamo confrontare finestre costituite da w residui contigui;  In tal caso metteremo un “dot” nella cella (i,j) solo nel caso in cui le stringhe ( ai ,a i+1 ,...,a w ) ( b j ,b j+1 ,... ,b w ) risultino identiche per s residui su w. DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet  Preleviamo la sequenza proteica della calmodulina umana con accession Number CAA36839;  Confrontate la sequenza con se stessa per mezzo di DotLet;  Lasciare come parametri iniziali la matrice Blosum62 ed una finestra di 15 residui per il confronto DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet  Il grafico riporta la distribuzione degli score ottenuti da tutte le coppie di finestre di sequenza confrontate (usando le matrici di score).  Si noti che la maggior parte dei punteggi ricade nella distribuzione a sinistra a basso Num di score con punteggio, mentre una piccola quel punteggio popolazione a punteggio elevato si trova a destra.  Spostando i cursori si variano i punteggi limite al di sotto dei quali la cella assume il colore nero e al di sopra il colore bianco. Tra i due limiti le celle assumono un tono di grigio Punteggio ottenuto proporzionale al punteggio che contengono. DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet  Cliccando sulla matrice si attiva un reticolo che può essere spostato sulla superficie della matrice stessa con il puntatore del mouse;  In basso viene riportato l’allineamento tra i due segmenti della proteina corrispondenti alla posizione del centro del reticolo sulla matrice; 22 Bioinformatica DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet Esempio: Domini Ripetuti.  Matrice Dot Plot calcolata sulla stessa sequenza di Drosophila Melanogaster (proteina SLIT).  Parametri: Blosum 62, Zoom 1:5, grayscale: 53%,30% SLIT_DROME (P24014): MAAPSRTTLMPPPFRLQLRLLILPILLLLRHDAVHAEPYSGGFGSSAVSSGGLGSVGIHIPGGGVGVITEARCPRVCSCT GLNVDCSHRGLTSVPRKISADVERLELQGNNLTVIYETDFQRLTKLRMLQLTDNQIHTIERNSFQDLVSLERLDISNNVI TTVGRRVFKGAQSLRSLQLDNNQITCLDEHAFKGLVELEILTLNNNNLTSLPHNIFGGLGRLRALRLSDNPFACDCHLSW LSRFLRSATRLAPYTRCQSPSQLKGQNVADLHDQEFKCSGLTEHAPMECGAENSCPHPCRCADGIVDCREKSLTSVPVTL PDDTTDVRLEQNFITELPPKSFSSFRRLRRIDLSNNNISRIAHDALSGLKQLTTLVLYGNKIKDLPSGVFKGLGSLRLLL LNANEISCIRKDAFRDLHSLSLLSLYDNNIQSLANGTFDAMKSMKTVHLAKNPFICDCNLRWLADYLHKNPIETSGARCE SPKRMHRRRIESLREEKFKCSWGELRMKLSGECRMDSDCPAMCHCEGTTVDCTGRRLKEIPRDIPLHTTELLLNDNELGR ISSDGLFGRLPHLVKLELKRNQLTGIEPNAFEGASHIQELQLGENKIKEISNKMFLGLHQLKTLNLYDNQISCVMPGSFE HLNSLTSLNLASNPFNCNCHLAWFAECVRKKSLNGGAARCGAPSKVRDVQIKDLPHSEFKCSSENSEGCLGDGYCPPSCT CTGTVVACSRNQLKEIPRGIPAETSELYLESNEIEQIHYERIRHLRSLTRLDLSNNQITILSNYTFANLTKLSTLIISYN KLQCLQRHALSGLNNLRVVSLHGNRISMLPEGSFEDLKSLTHIALGSNPLYCDCGLKWFSDWIKLDYVEPGIARCAEPEQ MKDKLILSTPSSSFVCRGRVRNDILAKCNACFEQPCQNQAQCVALPQREYQCLCQPGYHGKHCEFMIDACYGNPCRNNAT CTVLEEGRFSCQCAPGYTGARCETNIDDCLGEIKCQNNATCIDGVESYKCECQPGFSGEFCDTKIQFCSPEFNPCANGAK CMDHFTHYSCDCQAGFHGTNCTDNIDDCQNHMCQNGGTCVDGINDYQCRCPDDYTGKYCEGHNMISMMYPQTSPCQNHEC KHGVCFQPNAQGSDYLCRCHPGYTGKWCEYLTSISFVHNNSFVELEPLRTRPEANVTIVFSSAEQNGILMYDGQDAHLAV ELFNGRIRVSYDVGNHPVSTMYSFEMVADGKYHAVELLAIKKNFTLRVDRGLARSIINEGSNDYLKLTTPMFLGGLPVDP AQQAYKNWQIRNLTSFKGCMKEVWINHKLVDFGNAQRQQKITPGCALLEGEQQEEEDDEQDFMDETPHIKEEPVDPCLEN KCRRGSRCVPNSNARDGYQCKCKHGQRGRYCDQGEGSTEPPTVTAASTCRKEQVREYYTENDCRSRQPLKYAKCVGGCGN QCCAAKIVRRRKVRMVCSNNRKYIKNLDIVRKCGCTKKCY 24 Bioinformatica Allineamento di stringhe Cominciamo con l’affrontare il problema più generale dell’allineamento di una coppia di stringhe. Date due stringhe acbcdb e cadbd, in che modo possiamo stabilire quanto sono simili? La similarità scaturisce dall’allineamento ottimale delle due stringhe. Ecco un possibile allineamento: a c - - b c d b - c a d b - d - Il carattere speciale “-” rappresenta l’inserimento di uno spazio, che sta a significare una cancellazione nella sequenza o, equivalentemente, un’inserzione nell’altra sequenza (Mutazioni/Operazioni di INDEL). Similarità e distanza a c - c b c d b - c a d b - d - Possiamo valutare il grado di correlazione tra stringhe calcolandone la similarità o la distanza. Due stringhe che presentano alta similarità sono poco distanti, due stringhe che presentano bassa similarità sono molto distanti.  Distanza di editing E’ possibile calcolare la distanza tra due stringhe utilizzando, per esempio, la distanza di editing. La distanza di editing è definita come il minimo numero di operazioni da eseguire (inserimenti, cancellazioni, sostituzioni) per trasformare una stringa in un’altra. a - c c t g a a g c t t - a In questo caso per trasformare la prima stringa nella seconda dobbiamo inserire una g, sostituire una c con una t e cancellare una g. La distanza di editing tra le due stringhe è dunque 3.  La scoring function: similarità a c - c b c d b a c a d b - d - In generale è possibile valutare il grado di similarità o la distanza tra due stringhe, assegnando un punteggio (score) all’allineamento utilizzando un’opportuna scoring function. Per esempio, se assegniamo un punteggio di +2 per ogni match esatto e un punteggio di -1 per ogni mismatch o indel, la similarità tra le due sequenze secondo l’allineamento considerato sarà: S= 4 ⋅ 2+ 4 ⋅ ( −1 )=4 La scoring function: distanza a c - c b c d b a c a d b - d - Se assegniamo uno score pari a 0 nel caso di matches, pari ad 1 in caso di sostituzione di caratteri e pari a 2 in caso di allineamento con uno spazio, la distanza tra le due stringhe precedenti secondo l’allineamento considerato è: d= 4 ⋅0+ 1⋅1+3 ⋅ 2=7  La scoring function Più formalmente: Se x e y sono singoli caratteri o spazi, allora con il simbolo σ ( x,y )denotiamo lo score dell’allineamento di x con y; σ è la scoring function. Ovviamente possiamo costruire delle scoring function ad hoc per ogni problema; se, ad esempio, volessimo costruire una scoring function per il confronto di aminoacidi, faremmo in modo da tenere presenti le similarità chimico-fisiche e le differenze tra gli aminoacidi stessi.  Pairwise alignment Sia S una sequenza. Con il simbolo |S| denotiamo la lunghezza di S e con S[i] indichiamo l’i-esimo carattere di S. Se ad es. S = acbcdb, avremo |S|=6 e S=b. Siano S e T due sequenze. Un allineamento A associa ad S e T le sequenze S’ e T’, che possono contenere simboli di spazio “-”, in modo che – a: |S’|=|T’| – b: Rimuovendo gli spazi da S’ e T’ otteniamo S e T.  Ricerca miglior allineamento Lunghezza: s1=6 s2=6 Numero confronti s1+s2-1 = 11 Caratteri confrontati s1*s2 = 36 ILVVIV ILVVIV ILVVIV | 1 || 1 ||| 0 VLVVII VLVVII VLVVII ILVVIV ILVVIV ILVVIV |||| 0 ||||| 2 |||||| 4 VLVVII VLVVII VLVVII ILVVIV ILVVIV ILVVIV ||||| 1 |||| 2 ||| 2 VLVVII VLVVII VLVVII ILVVIV ILVVIV || 0 | 1 VLVVII VLVVII Ordine di un Algoritmo  Pairwise alignment (2) Lo score dell’allineamento di una coppia di sequenze è dato da: l ∑ σ ( S' [ i ] ,T' [ i ] ) i=1 Dove l =|S’|=|T’|. L’allineamento ottimale di S e T è quello che massimizza la similarità tra le sequenze o che minimizza la loro distanza. Nel seguito utilizzeremo il termine score per indicare il grado di similarità tra sequenze.  Allineamento di proteine: Matrici di sostituzione Nella valutazione di un allineamento di sequenze ci chiediamo se tale allineamento è casuale o biologicamente significativo, ed in questo caso ci chiediamo quanto è biologicamente significativo. Abbiamo visto che la scoring function associa un valore numerico ad ogni coppia di caratteri. Le matrici di sostituzione associano un valore numerico ad ogni possibile coppia di aminoacidi, tenendo conto delle similarità chimiche tra di essi. Tali matrici possono quindi essere utilizzate come scoring function per l’allineamento di proteine.  Le matrici di punteggio Matrice identità Matrice BLAST Matrice transizione trasversione A T C G A T C G A T C G A 1 0 0 0 A 5 -4 -4 -4 A 1 -5 -5 -1 T 0 1 0 0 T -4 5 -4 -4 T -5 1 -1 -5 C 0 0 1 0 C -4 -4 5 -4 C -5 -1 1 -5 G 0 0 0 1 G -4 -4 -4 5 G -1 -5 -5 1  Similarità tra aminoacidi Gli aminoacidi possono essere classificati in base alle loro proprietà chimico-fisiche. Nel confronto di proteine si può tenere conto di queste proprietà.  Matrici PAM Le matrici PAM (Point Accepted Mutations) furono sviluppate alla fine degli anni ’70 esaminando le mutazioni all’interno di superfamiglie di sequenze aminoacidiche strettamente correlate tra loro. Si notò che le sostituzioni che occorrevano tra sequenze strettamente correlate non erano casuali. Si concluse che alcune sostituzioni di aminoacidi occorrono più facilmente di altre, probabilmente a causa del fatto che tali sostituzioni non alterano significativamente la struttura e la funzione di una proteina. Ciò significa che proteine omologhe non devono necessariamente avere gli stessi aminoacidi in ogni posizione. Unità e matrici PAM Usiamo le unità PAM per misurare la distanza tra sequenze aminoacidiche. Due sequenze S1 ed S2 distano 1 unità PAM se S1 può essere trasformata in S2 con una media di 1 mutazione puntuale ogni 100 aminoacidi. In una sequenza la stessa posizione può mutare più volte e tornare quindi al carattere originario; dunque due sequenze che distano 1 PAM possono differire di meno dell’1%. Le matrici PAM Esistono diversi tipi di matrici PAM. Ognuna di esse è utilizzata per confrontare due sequenze che distano un certo numero di unità PAM l’una dall’altra. Ad es. la PAM120 può essere utilizzata per confrontare sequenze che distano 120 unità PAM. La entry (i,j) della matrice PAM120 contiene lo score assegnato alla coppia di aminoacidi (Ai,Aj); tale score è proporzionale alla frequenza con cui ci si aspetta che Ai sostituisca Aj in due sequenze che distano 120 unità PAM. Tutte le matrici della serie sono derivate per moltiplicazione della matrice unitaria (PAM1): PAM1 X PAM1 = PAM2 PAM30 = 30 sostituzioni su 100 siti (~ 75% identità) PAM120 = 120 sostituzioni su 100 siti (~ 40% identità) PAM250 = 250 sostituzioni su 100 siti (~ 20% identità) Nb alcune sostituzioni riportano al dato originale!  PAM 0 1 30 80 110 200 250 % identità 100% 99% 75% 60% 50% 25% 20% se due sequenze sono filogeneticamente distanti è opportuno usare matrici PAM con indici più alti, e viceversa  Matrice PAM 120 A 2 R -2 6 N 0 0 2 D 0 -1 2 4 C -2 -4 -4 -5 12 Q 0 1 1 2 -5 4 E 0 -1 1 3 -5 2 4 G 1 -3 0 1 -3 -1 0 5 H -1 2 2 1 -3 3 1 -2 6 I -1 -2 -2 -2 -2 -2 -2 -3 -2 5 L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6 K -1 3 1 0 -5 1 0 -2 0 -2 -3 5 M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6 F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9 P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6 S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2 T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3 W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17 Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10 V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4 A R N D C Q E G H I L K M F P S T W Y V   Matrici BLOSUM  (Henikoff e Henikoff 1992)  Derivano, usando lo stesso metodo usato per quelle PAM, dalla banca dati BLOCKS contenente gli allineamenti delle regioni più conservate di famiglie di proteine.  Per ogni tipo di matrice BLOSUM si eliminano tutte le sequenze che hanno una percentuale di identità superiore ad una soglia.  BLOSUM62 = derivata da un allineamento in cui le sequenze che abbiano più del 62% di amminoacidi identici vengono considerate come una sola sequenza  BLOSUM construction Example: – AAACDA- - -BBCDA – DABCDA- A -BACBB – BACDDABA -BDCAA Observed frequency q(i, j) of i and j being on the same position as a result of evolution is calculated from the alignment. q(i, j) is observed frequency for a pair of amino acids in the same column to be {i, j} – Example has 8 columns with 3 pairs each. Only two pairs 2 are {C, D}, hence q(C, D) = 2 / (8 * 3)  BLOSUM construction p(i) is the frequency of occurrence of i in {i, j} pair – p(i) = q(i, i) + sum of q(i, j) / 2 for i j Random frequency derived from distribution of amino acids – p(i, j) = 2 * p(i) * p(j) if i j – p(i, i) = p(i) * p(i) BLOSUM-X (i, j) = 2 * log2 (q(i, j) / p(i, j))  I valori nelle matrici di sostituzione determinano il punteggio di un allineamento Score allineamento: 15 Seq1 V D S - C Y Seq2 V E S L C Y Score 4 2 4 -11 9 7 Blosum62 Punteggio totale= ∑ somiglianze − ∑ penalità gap  Pairwise alignment (2) Lo score dell’allineamento di una coppia di sequenze è dato da: l ∑ σ ( S' [ i ] ,T' [ i ] ) i=1 Dove l =|S’|=|T’|. L’allineamento ottimale di S e T è quello che massimizza la similarità tra le sequenze o che minimizza la loro distanza. Nel seguito utilizzeremo il termine score per indicare il grado di similarità tra sequenze. Derivation of the dynamic programming algorithm 1. Score of new = Score of previous + Score of new alignment alignment (A) aligned pair V D S - C Y V D S - C Y V E S L C Y V E S L C Y 15 = 8 + 7 2. Score of = Score of previous + Score of new alignment (A) alignment (B) aligned pair V D S - C V D S - C V E S L C V E S L C 8 = -1 + 9 3. Repeat removing aligned pairs until end of alignments is reached  Formal description of dynamic programming algorithm i -x Si - x,j - wx Si –1, j- 1 + s(ai , bj) i -1 i Si, j - y - wy Si, j i -y j -1 j This diagram indicates the moves that are possible to reach a certain position (i,j) starting from the previous row and column at position (i -1, j-1) or from any position in the same row or column Diagonal move with no gap penalties or move from any other position from column j or row i, with a gap penalty that depends on the size of the gap  Formal description of dynamic programming algorithm For two sequences a = a1, a2,..ai and b = b1, b2,..bj, where Sij = S ( a1,…ai, b1, …bj) then Sij = max { Si – 1, j – 1 + s(aibj), max (Si – x, j - wx), x1 max (Si j- y - wx), y1 } where Sij is the score at position at i in sequence a and j in sequence b, s(aibj) is score for aligning the character at positions i and j, wx is the penalty for a gap of length x in sequence a, and wx is the penalty for a gap of length y in sequence b. Note that Sij is a type of running best score as the algorithm moves through every position in the matrix  An optimal alignment -- an alignment of maximum score Let A=a1a2…am and B=b1b2…bn. Si,j: the score of an optimal alignment between a1a2…ai and b1b2…bj With proper initializations, Si,j can be computed s i −1, j +w ( a i , − ) as follows. s i,j =max { s i,j −1 +w ( −,b j ) s i −1, j −1 +w ( ai ,b j ) 56 }  Computing Si,j j w(ai,bj ) w(ai,-) i w(-,bj) Sm,n 57  Match= +8 Initialization Mismatch= -5 Gap= -3 C G G A T C A T 0 -3 -6 -9 -12 -15 -18 -21 -24 -3 C -6 T -9 T A -12 A -15 C -18 T -21  S3,5 = ？ Match= +8 Mismatch= -5 Gap= -3 C G G A T C A T 0 -3 -6 -9 -12 -15 -18 -21 -24 C -3 8 5 2 -1 -4 -7 -10 -13 T -6 5 3 0 -3 7 4 1 -2 T -9 2 0 -2 -5 ? A -12 A -15 C -18 T 59 -21  S3,5 = ？ C G G A T C A T 0 -3 -6 -9 -12 -15 -18 -21 -24 -3 8 5 2 -1 -4 -7 -10 -13 C -6 5 3 0 -3 7 4 1 -2 T -9 2 0 -2 -5 5 2 -1 9 T A -12 -1 -3 -5 6 3 0 10 7 A -15 -4 -6 -8 3 1 -2 8 5 optimal C -18 -7 -9 -11 0 -2 9 6 3 score T -21 -10 -12 -14 -3 8 6 4 14 60 C T T A A C – T C G G A T C A T 8 – 5 –5 +8 -5 +8 -3 +8 = 14 C G G A T C A T 0 -3 -6 -9 -12 -15 -18 -21 -24 -3 8 5 2 -1 -4 -7 -10 -13 C -6 5 3 0 -3 7 4 1 -2 T -9 2 0 -2 -5 5 2 -1 9 T -12 -1 -3 -5 6 3 0 10 7 A A -15 -4 -6 -8 3 1 -2 8 5 C -18 -7 -9 -11 0 -2 9 6 3 T -21 -10 -12 -14 -3 8 6 4 14 Global Alignment vs. Local Alignment global alignment: local alignment: 62  An optimal local alignment Si,j: the score of an optimal local alignment ending at ai and bj With proper initializations, Si,j can be computed as follows. 0 s i,j =max { } s i −1, j +w ( ai ,− ) s i,j −1 +w ( −,b j ) si −1, j −1 +w ( ai ,b j ) 63 Match: 8 Mismatch: -5 local alignment Gap symbol: - 3 C G G A T C A T 0 0 0 0 0 0 0 0 0 0 8 5 2 0 0 8 5 2 C 0 5 3 0 0 8 5 3 13 T 0 2 0 0 0 8 5 2 11 T A 0 0 0 0 8 5 3 ? A 0 C 0 T 0 64 Match: 8 Mismatch: -5 local alignment Gap symbol: - 3 C G G A T C A T 0 0 0 0 0 0 0 0 0 0 8 5 2 0 0 8 5 2 C 0 5 3 0 0 8 5 3 13 T 0 2 0 0 0 8 5 2 11 T A 0 0 0 0 8 5 3 13 10 A 0 0 0 0 8 5 2 11 8 the 0 8 5 2 5 3 13 10 7 best C score T 0 5 3 0 2 13 10 8 18 65 A – C - T A T C A T 8-3+8-3+8 = 18 C G G A T C A T 0 0 0 0 0 0 0 0 0 0 8 5 2 0 0 8 5 2 C 0 5 3 0 0 8 5 3 13 T 0 2 0 0 0 8 5 2 11 T (not always at A 0 0 0 0 8 5 3 13 10 the corner) A 0 0 0 0 8 5 2 11 8 the 0 8 5 2 5 3 13 10 7 best C score T 0 5 3 0 2 13 10 8 18 66  Schemi di peso per i gap  Linear score  f(g)= -gd con d gap-open penalty e g lunghezza del gap  Un peso dei gap dipendente dalla sola lunghezza comporta che due gap isolati diano lo stesso costo di due consecutivi  Affine score  f(g)= -d –(g-1)e con d gap-open penalty, e gap-extension penalty e g lunghezza del gap  Modello di transizione da una sequenza all’altra biologicamente più significativo, dal momento che inserzioni e cancellazioni di più di un residuo non sono eventi poco comuni tra sequenze proteiche omologhe Significato strutturale ALFAELICAUNO-----ALFAELICADUE |||||||||||| |||||||||||| ALFAELICAUNOLOOOPALFAELICADUE Loop Alfa elica Alfa elica  Allineamento globale vs locale L’allineamento di due o più sequenze può essere globale o locale Globale: l’intera sequenza viene allineata Locale: solo frammenti della sequenza vengono allineati  Allineamento locale: esempio LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKA LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKA  Allineamento locale E’ meglio avere molte coincidenze sparse o averne meno, ma concentrate? Allineamento locale Date S e T trovare due sottostringhe v e w di S e T rispettivamente la cui similarità (allineamento ottimo) sia massima su tutte le coppie di sottostringhe di S e T.  Significato Biologico Allineamento globale Allineamento locale Ordine di un Algoritmo Confronto di sequenza query e l'intera banca dati FASTA – per allineamenti globali BLAST- per allineamenti locali FASTA Sistema di ricerca in banca dati di sequenze simili ad una di nostro interesse FASTA: usa le lookup tables Tabelle formate dalle differenze in posizione di singoli aminoacidi Procedura simile alla costruzione di dot-plot ma meno richiestiva sul calcolo Lookup: O (n+m) Matrice: O (n*m) Matrice di parole A G W W R A A W A A R G W A G A G * * * W * * * * W * * * * R * * A * * * * * * * G * * * W * * * * A * * * * * * A * * * * * * * Matrice di parole 13 Coppie di parole identiche di lunghezza 2 A G W W R A A W A A R G W A G A G * * * W * * * * W * * * * * R * * * A * * * * * * * Parola 2 G * * * W * * * * A * * * * * * A * * * * * * * Matrice di parole 13 Coppie di parole identiche di lunghezza 2 A G W W R A A W A A R G W A G A G W W * R * A Parola 2 G W A A  FastA -------- Sequenza A -------------> -------- Sequenza A -------------> -------- Sequenza B -----------> -------- Sequenza B -----------> Matrice di punti Matrice di parole di lunghezza 2  Unione parole contigue -------- Sequenza A -------------> -------- Sequenza A -------------> -------- Sequenza B -----------> -------- Sequenza B ----------->  Calcolo similarità -------- Sequenza A -------------> -------- Sequenza A -------------> -------- Sequenza B -----------> -------- Sequenza B ----------->  Inserimento gaps -------- Sequenza A -------------> -------- Sequenza A -------------> -------- Sequenza B -----------> -------- Sequenza B ----------->  Calcolo Opt -------- Sequenza A -------------> -------- Sequenza B -----------> FASTA- pipeline  Parole con errori LTAGARIDEDWEDISLHDWRTDW Nessuna parola identica di lunghezza 3 TSGCRKDEWWTWDSIHSTQWSD E D W Parole lunghezza 3 E D W L Parole lunghezza 4 E W W Identiche con 1 Errore E W W A Identiche con 2 Errori LTAGARIDEDWEDISLHDWRTDW 10 Parole lunghe 3 con 1 errore TSGCRKDEWWTWDSIHSTQWSD ammesso LTAGARIDEDWEDISLHDWRTDW 18 Parole lunghe 4 con 2 T S G C R K D E W W T W D S I H S T Q W S D errori ammessi  Ricerca per similarità Una delle operazioni più comuni ed utili su una base di dati biologica è la ricerca di sequenze simili ad una sequenza data in input. Il tool più popolare per questo tipo di ricerche è BLAST (Basic Local Alignment Search Tool). BLAST esegue confronti fra coppie di sequenze alla ricerca di regioni di similarità, piuttosto che un allineamento globale tra le intere sequenze. BLAST può eseguire migliaia di confronti fra sequenze in pochi minuti e in poco tempo è possibile confrontare una sequenza query con l’intero database per ricercare tutte le sequenze simili ad essa.  Come funziona BLAST? Ecco i passi dell’algoritmo di BLAST: 1. 1- Si estraggono tutte le possibili word di m lettere dalla sequenza query (m=3 per le proteine, m=11 per il DNA). 2. 2 Per ogni word della sequenza da esaminare viene costruita una lista di possibili words che, se confrontate con la sequenza in questione, hanno un punteggio superiore ad un valore- soglia T (compreso fra 11 e 15) calcolato di volta in volta in base alla composizione e alla lunghezza della sequenza in esame.  Come funziona BLAST? (2) 1. Si confronta la lista di words con le sequenze contenute nel database alla ricerca di matches esatti: 2. Quando viene riscontrata una corrispondenza (hit), essa viene estesa a monte e a valle per vedere se è possibile definire un tratto di sequenza in grado di raggiungere un punteggio superiore ad un valore-soglia S. Come funziona BLAST? (3)  NCBI BLAST L’implementazione più popolare dell’algoritmo BLAST si trova sul sito dell’NCBI: http://www.ncbi.nlm.nih.gov/BLAST Sono disponibili numerosi tipi di BLAST; tra cui vale la pena di citare: – BLASTN (Nucleotidi – Nucleotidi); – BLASTP (Proteine - Proteine); – TBLASTN (Translated BLAST Nucleotide); – BL2SEQ (Blast 2 sequences).  BLASTN: Esempio con BCL2 Selezioniamo nucleotide blast Inseriamo la sequenza (o scegliamo un file da uploadare) Scegliamo database e organismo Scegliamo il programma giusto (blastn)  BLASTN: Esempio BCL2 BLAST fornisce in output la distribuzione dei matches trovati, assegnando a colori diversi i diversi scores: ovviamente uno score maggiore indica un match più significativo. Cliccando sulle barre colorate si ottiene l’allineamento corrispondente.  BLASTN: Esempio BCL2 L’allineamento migliore mostra un match del 100%: abbiamo ritrovato lo stesso BCL2 nel database. Abbiamo il link alla sequenza trovata ed alla pagina corrispondente in Gene. Un trattino indica il match dei caratteri delle due sequenze. BLASTN: Esempio BCL2 L’assenza del trattino invece indica un mismatch: Punteggio sequenze random Numero Sequenzec asuali 70 60 50 40 Opt = 1070 30 20 10 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 Punteggio OPT Punteggio sequenze random Numero Sequenzec asuali 70 60 50 40 Opt = 1070 30 20 10 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 Punteggio OPT Significatività statistica Numero Sequenzec asuali 70 60 50 40 Opt = 1070 30 20 10 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 Punteggio OPT Significatività statistica Numero Sequenzec asuali 70 60 50 40 E = 1.21*10-21 30 20 10 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 Punteggio E value = OPT Numero atteso per caso di sequenze con punteggio > opt