Ricerche in database e allineamenti a coppie 1 È un errore madornale elaborare teorie prima di...

Ricerche in databaseRicerche in databasee allineamenti a coppiee allineamenti a coppie

1

“È un errore madornale elaborare teorie prima di avere i dati. Senza accorgersene uno incomincia a distorcere i fatti per adattarli alle teorie invece di far sì che le teorie spieghino i fatti.” (A. Conan Doyle, A scandal in Bohemia, Strand Magazine, July 1891)

SommarioSommario

Dot plotDot plot

Allineamenti sempliciAllineamenti semplici

GapGap

Matrici di punteggioMatrici di punteggio

Programmazione dinamica: l’algoritmo di Programmazione dinamica: l’algoritmo di Needleman e WunschNeedleman e Wunsch

Allineamenti globali e localiAllineamenti globali e locali

Ricerche in databaseRicerche in database

Allineamenti multipli di sequenzaAllineamenti multipli di sequenza2

Introduzione Introduzione 1 1

Ogni allineamento tra due o più sequenze di nucleotidi o aminoacidi rappresenta un’ipotesi esplicita riguardo alla storia evolutiva di quelle sequenze

Confronti tra sequenze correlate hanno favorito numerosi progressi nella comprensione del loro contenuto informativo e della loro funzioneLe tecniche di allineamento e confronto di sequenze e di ricerca di sequenze simili in database sono i pilastri della bioinformatica

3

Introduzione Introduzione 2 2

Sequenze strettamente correlate tra loro sono in genere facili da allineare e, viceversa, l’allinea-mento rappresenta un indicatore importante del loro livello di correlazioneGli allineamenti di sequenze servono per:

determinare la funzione di una sequenza genetica appena scoperta (confronto con sequenze simili)determinare la relazione evolutiva fra geni, protei-ne e intere speciepredire la struttura e la funzione di proteine nuove in base a proteine “simili” note

4

Dot plot Dot plot 1 1

Uno dei metodi più semplici per valutare la simi-larità fra due sequenze consiste nel visualizzare le regioni di similarità per mezzo di dot plotdot plot

Il dot plot è un metodo grafico di visualizzazione della similaritàMeno ovvio è il suo stretto rapporto con gli allineamenti

Il dot plot è una tabella o matrice o, in alternati-va, un piano cartesiano

Le righe (le ascisse) corrispondono ai residui di una sequenza e le colonne (le ordinate) ai residui della seconda sequenza

5


6

Dot plot: (a) rappresentazione matriciale e (b) rappresentazione grafica nel piano cartesianoDot plot: (a) rappresentazione matriciale e (b) rappresentazione grafica nel piano cartesiano

(a)(a) (b)(b)


Ciò indica che vi sono state inserzioni o delezioni nei segmenti tra le regio-ni di similarità

7

Le regioni di similarità saranno pertanto visualizzabili come linee diagonali che procedono nella direzione SudOvestNordEst; sequenze ripetute produrranno diagonali paralleleIl dot plot cattura dunque, in una singola immagine, non solo la similarità complessiva tra due sequenze, ma anche l’insieme completo e la relativa qualità dei diversi allineamenti possibiliSpesso alcune regioni di similarità possono risultare spostate, in modo da apparire su diagonali parallele, ma non collineari


Per ridurlo si può passare dal confronto dei singoli residui a quello di brevi sequenze (fine-stre scorrevoli) di più residuiIn tal caso, il dot è riportato solo quando in una finestra di w residui, s sono identici

8

Le identità casuali producono nelle matrici dot plot un rumore di fondo elevato (soprattutto per sequenze lunghe e simili)Inoltre, ciò accade quasi sempre negli allinea-menti tra acidi nucleici a causa dell’alfabeto di sole quattro lettere


A valori crescenti di s corrisponde una stringenza sempre maggiore (massima per s = w)

Ovviamente, la variazione di w e s ha influenza sul rumore di fondo

I valori di w e s più adatti al confronto di se-quenze nucleotidiche e proteiche sono determina-ti empiricamente con processi tipo trialanderror

9


Una matrice dot plot che consideri solo le identità non fornisce una reale indicazione dei rapporti di similarità per le proteine, ove la non identità tra aminoacidi può avere implicazioni biologiche pro-fondamente diverseInfatti:

in alcuni casi la sostituzione di un residuo con un altro non identico, ma con proprietà molto simili (ad es.: leucinaleucina ed isoleucinaisoleucina), può essere quasi irrilevantein altri casi, due residui non identici possono avere proprietà molto diverse

10

Allineamenti semplici Allineamenti semplici 1 1

Un allineamento semplice tra due sequenze è una corrispondenza a coppie tra i caratteri di ogni sequenzaL’allineamento di sequenze nucleotidiche o amino-acidiche riflette la relazione evolutiva fra due o più omologhiomologhi, cioè sequenze che hanno in comune uno stesso antenato

Non esistono gradi di omologia: ad ogni data po-sizione di un allineamento, le sequenze possiedono un antenato in comune o non lo possiedonoLa similarità complessiva si può invece quantificare per mezzo di un valore frazionario

11

Allineamenti semplici Allineamenti semplici 2 2In particolare, in ogni data posizione all’interno di una sequenza possono avvenire tre tipi di cambiamenti:

Una mutazionemutazione, che sostituisce un carattere con un altroUn’inserzioneinserzione, che aggiunge una o più posizioniUna delezionedelezione, che elimina una o più posizioni

In natura, inserzioni e delezioni sono significativamen-te meno frequenti delle mutazioniPoiché non esistono gli omologhi dei nucleotidi inseriti o cancellati, negli allineamenti sono comunemente ag-giunti dei gapgap che rispecchiano il verificarsi di questo tipo di cambiamenti

12

Allineamenti semplici Allineamenti semplici 3 3Nel caso più semplice, in cui non sono permessi gap, l’allineamento di due sequenze si riduce alla scelta del punto di partenza per la sequenza più corta

AATCTATA AATCTATA AATCTATA

AAGATA AAGATA AAGATA

Per determinare quale dei tre allineamenti sia quello “ottimale”, occorre stabilire un punteggio da valutare re-lativamente ad ogni allineamento

dove n è la lunghezza della sequenza più lunga

Per un punteggio di non/corrispondenza pari a 0/1, i tre allineamenti vengono valutati rispettivamente 4, 1 e 3

13

{n

i1 Punteggio di non corrispondenza se seq1iseq2i

Punteggio di corrispondenza se seq1iseq2i

Gap Gap

Considerare la possibilità di eventi di inserzione e delezione aumenta considerevolmente il numero di allineamenti possibili fra coppie di sequenzePer esempio, le due sequenze AATCTATA e AAGATA che possono essere allineate senza gap in soli tre modi, ammettono 28 allineamenti diversi, con l’inserimento di due gap all’interno della sequenza più corta

EsempioEsempioAATCTATA AATCTATA AATCTATA


14

Penalità semplici per utilizzo di gapPenalità semplici per utilizzo di gap

Introduzione nel punteggio di valutazione di alli-neamento di un termine di penalità per l’apertura di un gap (gap penaltygap penalty)

Assumendo un punteggio di non/corrispondenza pari a 0/1 ed una gap penalty uguale a 1, i punteggi per i tre allineamenti con gap risultereb-bero 1, 3, 3



15

{n

i1 Punteggio di non corrispondenza se seq1iseq2i

Punteggio di corrispondenza se seq1iseq2i

Punteggio per l’apertura di gap se seq1i“” o seq2i “”

Penalità per creazione e lunghezza dei gap Penalità per creazione e lunghezza dei gap 1 1

Usando gap penalty semplici, non è infrequente calco-lare più allineamenti “ottimali” (in base al criterio scelto)

Penalizzare diversamente i gap isolati e quelli che appa-iono in sequenza

Concretamente, ogni dato allineamento a coppie rap-presenta un’ipotesi sul percorso evolutivo che due sequenze hanno intrapreso dall’ultimo antenato in comuneQuando si considerano diverse ipotesi in competi-zione, quella che invoca il minor numero di eventi improbabili è, per definizione, quella più probabilmente corretta

16


Siano s1 ed s2 due sequenze nucleotidiche arbitrarie di lunghezza 12 e 9, rispettivamente

Ogni allineamento avrà necessariamente tre gap nella sequen-za più cortaAssumendo che le sequenze siano omologhe dall’inizio alla fine, la differenza di lunghezza può essere dovuta all’inserzione di nucleotidi nella sequenza più lunga o alla delezione di nucleotidi nella sequenza più corta, o a una combinazione delle duePoiché la sequenza del precursore è ignota, non esiste un metodo per determinare la causa di un gap, che si attribuisce genericamente ad un evento indel indel (inserzione/delezione)Dato che inserzioni/delezioni multiple di nucleotidi non sono infrequenti, è statisticamente più probabile che la differenza di lunghezza fra le due sequenze sia il risultato di un singolo indel da 3 nucleotidi, piuttosto che di più indel distinti 17


La funzione di punteggio deve premiare gli allinea-menti che sono più probabili dal punto di vista evolutivoAssegnando una penalità sulla lunghezza dei gap (che dipende dal numero di caratteri sequenziali mancanti) più bassa della penalità per la creazione di nuovi gap, la funzione di punteggio premia gli allineamenti che presentano gap sequenziali

EsempioEsempio: usando una penalità di creazione gap pari 2, una penalità per la lunghezza di 1 (per gap) e valori di non/corrispondenza uguali a 0/1, i punteggi per i tre allineamenti sono rispettivamente 3, 1, 1


AAGATA AAGATA AAGATA18

Matrici di punteggio Matrici di punteggio 1 1Esattamente come la gap penalty può essere suddivisa per premiare gli allineamenti evolutivamente più pro-babili, così anche la penalità per non corrispondenza può essere resa non uniforme, sulla base della sem-plice osservazione che alcune sostituzioni sono più comuni di altre

EsempioEsempio: si considerino due sequenze proteiche, una delle quali possiede un’alaninaalanina in una data posizione

Una sostituzione con un altro aminoacido piccolo e idrofobico, come la valinavalina, ha un minor impatto sulla proteina risultante, piuttosto che una sostituzione con un residuo grande e carico come, ad esempio, la lisinalisina

19

Matrici di punteggio Matrici di punteggio 2 2

20

LisinaLisina

AlaninaAlanina

ValinaValina


Si premiano moderatamente le corri-spondenze di nucleotidi, si dà una piccola penalità alle transizionitransizioni (sostituzione fra purine/pirimidine, A-G/C-T) e una penali-tà più severa per le transversionitransversioni, in cui una purina sostituisce una pirimidina o viceversa

21

A T C G

A 1 5 5 1

T 5 1 1 5

C 5 1 1 5

G 1 5 5 1

Intuitivamente, una sostituzione più conservativa, a diffe-renza di una più drastica, può avvenire più frequentemente, perché preserva la funzionalità originale della proteinaDato un punteggio di allineamento per ogni possibile coppia di nucleotidi o residui, la risultante matrice di punteggio è utilizzata per assegnare uno score ad ogni posizione non gap di un allineamento

EsempioEsempio


22

Si possono considerare diversi criteri nella creazione di una matrice di punteggio per gli allineamenti di se-quenze aminoacidiche

Similarità chimicofisicaFrequenze di sostituzione osservate

Nelle matrici basate sulla similarità, l’accoppiamento di due aminoacidi differenti, che però possiedono en-trambi gruppi funzionali aromatici (aminoacidi idrofobi-ci e caratterizzati da una catena laterale contenente un anello di benzene; sono fenilalaninafenilalanina, tirosinatirosina e tripto-fanotripto-fano) potrebbe ricevere un punteggio positivo, mentre l’accoppiamento di aminoacidi non polari con amino-acidi carichi potrebbe ricevere una penalità


23

Le matrici di punteggio possono essere ricavate in base all’idrofobicità, alla presenza di carica, all’elet-tronegatività e alla dimensione del residuoIn alternativa, si possono utilizzare criteri di similarità del genoma codificante: punteggio assegnato in base al numero minimo di sostituzioni nucleotidiche neces-sarie per convertire un codone da un residuo all’altro

Difficoltà di combinare vari punteggi, chimici, fisici e genetici, in una singola matrice “significativa”


24

Il metodo più comune per derivare matrici di punteg-gio è osservare le frequenze effettive di sostituzione dei vari residui aminoacidici in naturaSe una sostituzione tra due particolari aminoacidi è osservata frequentemente, le posizioni che vedono i due residui allineati ottengono punteggio favorevoleViceversa, sono penalizzati gli allineamenti tra residui fra i quali, nell’evoluzione, non si osserva una sosti-tuzione frequente

Matrici PAM Matrici PAM 1 1Le matrici di tipo PAMPAM si basano sul concetto di Percent Percent Accepted MutationAccepted Mutation e furono proposte nel 1978 da M. Dayhoff et al., sulla base di uno studio di filogenesi mole-colare compiuto su 71 famiglie di proteine Furono sviluppate esaminando le mutazioni all’interno di superfamiglie di sequenze aminoacidiche strettamente cor-relate e rilevando come le sostituzioni che occorrevano non fossero casuali

Si concluse che alcune sostituzioni di aminoacidi avvengono più frequentemente di altre, probabilmente a causa del fatto che tali sostituzioni non alterano significativamente la struttura e la funzione di una proteinaProteine omologhe non devono necessariamente essere costi-tuite dagli stessi aminoacidi in ogni posizione

25

Matrici PAM Matrici PAM 2 2Due proteine distano 1 PAM se si differenziano per 1 Due proteine distano 1 PAM se si differenziano per 1 aminoacido su 100 e se la mutazione è aminoacido su 100 e se la mutazione è acceptedaccepted, cioè non , cioè non ha portato a perdita di funzionalitàha portato a perdita di funzionalità

In altre parole… due sequenze s1 ed s2 distano 1 unità PAM se s1

può essere trasformata in s2 con una media di una mutazione puntuale ogni 100 aminoacidiIn 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%

Esempi di questo tipo sono proteine ortologhe (che svolgono la stessa funzione in organismi diversi), ma non mutazioni patologiche che si associano invece a perdita di funzionalitàPer generare una matrice PAM 1PAM 1, si considerano una coppia (più sequenze rappresentative) di proteine molto simili (identità 85%), in cui l’allineamento può essere definito senza ambiguità 26

Matrici PAM Matrici PAM 3 3Più in dettaglio…

Viene costruito un allineamento fra sequenze con identità molto alta

Si calcola la mutabilità relativa mj per ogni aminoacido j (il numero di volte in cui un aminoacido è sostituito da un altro)

Per ogni coppia di aminoacidi i e j, si calcola Fij, che

rappresenta il numero di volte che l’aminoacido j è sostituito dall’aminoacido i

Si divide Fij per i valori di mutabilità relativa, normalizzati per la frequenza di ogni aminoacido

Si valuta il logaritmo, per ottenere ogni elemento Pij della matrice PAM 1, detta anche matrice di loglogoddsodds

27

Matrici PAM Matrici PAM 4 4

EsempioEsempio1) Si costruisce un allineamento multiplo di sequenze:

ACGCTAFKI GCGCTLFKIGCGCTAFKI ASGCTAFKLACGCTAFKL ACACTAFKLGCGCTGFKI

28


29

ACGCTAFKI

ACACTAFKL

GGAA

IILL

ACGCTAFKL

CCSS

ASGCTAFKLGCGCTLFKI

AALL

AAGG

GCGCTAFKI

AAGG

GCGCTGFKI

Esempio (continua)Esempio (continua)2) Dall’allineamento, viene creato un albero filogeneticoalbero filogenetico,

che indica l’ordine in cui potrebbero essere avvenute le varie sostituzioni mostrate dall’allineamento


30

Esempio (continua)Esempio (continua)3) Per ogni tipo di aminoacido, viene calcolata la

frequenza di sostituzione (con un qualsiasi altro aminoacido)

Si assume che le sostituzioni siano simmetriche, cioè che avvengano con la stessa probabilità relativamente ad una data coppia di aminoacidi

Per esempio, per determinare la frequenza FG,AFA,G, delle sostituzioni fra A e G, si contano tutti i rami AG e GA


31

Esempio (continua)Esempio (continua)4) Si calcola la mutabilità relativa mj di ogni aminoacido

La mutabilità relativa è il numero di volte in cui un ami-noacido viene sostituito da un qualsiasi altro nell’albero filogeneticoTale numero viene poi normalizzato con il numero totale delle mutazioni che potrebbero avere effetto sul residuo…ovvero, il denominatore della frazione è dato dal numero totale delle sostituzioni nell’albero, moltiplicato per due, moltiplicato per la frequenza del particolare aminoacido, moltiplicato per un fattore di scala pari a 100Il valore 100 è usato perché la matrice PAM 1 rappresenti la probabilità di sostituzione per 100 residui


32

Esempio (continua)Esempio (continua)Consideriamo l’aminoacido A (alanina): vi sono 4 muta-zioni che lo coinvolgono all’interno dell’albero filogeneticoDividiamo questo valore per il doppio del numero totale di mutazioni (6212), moltiplicato per la frequenza relativa del residuo fA (10630.159), moltiplicato per 100

nA4(120.159100)0.0209


33

Esempio (continua)Esempio (continua)5) Si calcola la probabilità di mutazione Mij, per ogni

coppia di aminoacidi

MijnjFij/jFij

…e quindiMG,A(0.02093)40.0156

dove il denominatore jFij rappresenta il numero totale delle sostituzioni che coinvolgono l’aminoacido A nell’albero filogenetico


34

Esempio (continua)Esempio (continua)6) Infine, ogni Mij viene diviso per la frequenza di occor-

renza del residuo i ed il logaritmo del valore risultante costituisce il relativo elemento Pij della matrice PAM

Per G, la frequenza di occorrenza fG è pari a 0.159

Il valore PG,Alog(0.01560.159)1.01

7) Ripetendo il procedimento descritto per ogni coppia di aminoacidi si ottengono tutti i valori extradiagonali della matrice PAM; i valori diagonali Pii si calcolano invece

ponendo Mii 1ni ed eseguendo il calcolo effettuato al punto 6)

Matrici PAM Matrici PAM 11 11Le matrici PAM di ordine superiore vengono generate per successive moltiplicazioni della matrice PAM 1, perché la probabilità di due eventi indipendenti è pari al prodotto delle probabilità di ciascun evento singoloMentre per la matrice PAM 1 è vero che un evento mutazionale corrisponde ad una differenza 1%, que-sto non è vero per le matrici di ordine superioreInfatti, le successive mutazioni hanno una probabilità via via crescente di avvenire in corrispondenza di aminoacidi già mutatiIl grado di differenza aumenta con l’aumentare del nu-mero di mutazioni, ma mentre quest’ultimo può au-mentare all’infinito, la differenza tende asintoticamen-te al 100%

35


La scelta della matrice PAM più indicata, per un particolare allineamento di sequenze, dipende dalla loro lunghezza e dal loro grado di correlazionePAM 2 è calcolata da PAM 1 ipotizzando un altro passo evolutivo

PAM n è ottenuta da PAM n1PAM 100, quindi, rappresenta 100 passi evolutivi, in cia-scuno dei quali si è avuto un 1% di sostituzioni rispetto al passo precedente

36

PAM 1PAM 1 PAM 100PAM 100 PAM 250PAM 250

sequenze vicinesequenze vicinefilogeneticamentefilogeneticamente

sequenze lontanesequenze lontanefilogeneticamentefilogeneticamente


37

Matrice PAM 250Matrice PAM 250


38

NotaNotaOgni elemento Pij della matrice PAM misura quanto

la sostituzione dell’aminoacido Ai con l’aminoacido

Aj è più (o meno) probabile del “caso”

Pertanto:

Pij 0 più frequente di quanto atteso “per caso”

Pij 0 come “il caso”

Pij 0 meno frequente di quanto atteso “per caso”

Matrici BLOSUM Matrici BLOSUM 1 1Le matrici BLOSUMBLOSUM (BLOcks amino acid SUBstitution BLOcks amino acid SUBstitution MatricesMatrices) furono introdotte nel 1992 da S. Henikoff e J. G. Henikoff per attribuire un punteggio alle sostitu-zioni tra sequenze aminoacidicheIl loro scopo era quello di sostituirsi alle matrici PAM, facendo uso della maggiore quantità di dati che si era resa disponibile successivamente al lavoro della DayhoffLe matrici BLOSUM sono basate sulla banca dati BLOCKSBLOCKS, che contiene una collezione di allineamenti multipli di segmenti proteici senza gapPer ottenere la matrice BLOSUM, vengono raggruppati allineamenti senza gap di proteine correlate, utilizzan-do tecniche statistiche di raggruppamento (clusteringclustering)

39

Matrici BLOSUM Matrici BLOSUM 2 2L’approccio via clustering aiuta ad eliminare i problemi statistici che possono verificarsi quando si osserva una frequenza di sostituzione molto bassa per una parti-colare coppia di aminoacidiOgni blocco di allineamenti contiene sequenze con un numero di aminoacidi identici superiore ad una certa percentuale NAd esempio, nella costruzione della matrice BLOSUM62 ogni cluster sarà costituito da sequenze che hanno identità superiore al 62%Da ogni blocco è possibile ricavare la frequenza relativa di sostituzione degli aminoacidi, che può essere utilizzata per calcolare una matrice di score

40

Matrici BLOSUM Matrici BLOSUM 3 3Gli elementi Bij della matrice vengono valutati in base alla formula

Bij = klog(M(Ai,Aj)/C(Ai,Aj)), k costante

– M(Ai,Aj) è la frequenza di sostituzione dell’aminoacido Ai

con l’aminoacido Aj, osservata nei blocchi di proteine omologhe considerate

– C(Ai,Aj) è la frequenza di sostituzione attesa, stimata

come prodotto delle frequenze degli aminoacidi Aj e Aj nella totalità dei blocchi di proteine omologhe considerate

• Anche in questo caso la entry (i,j) della matrice è proporzionale alla frequenza di sostituzione dell’ami-noacido Ai con l’aminoacido Aj

41BLOSUM35BLOSUM35 BLOSUM62BLOSUM62

sequenze vicinesequenze vicinefilogeneticamentefilogeneticamente

sequenze lontanesequenze lontanefilogeneticamentefilogeneticamente

Esempio: BLOSUM62Esempio: BLOSUM62

42

PAM o BLOSUM PAM o BLOSUM 1 1I due tipi di matrici partono da presupposti diversi

In PAM si assume un modello in cui le sostituzioni ami-noacidiche osservate a grandi distanze evolutive deriva-no esclusivamente dall’assommarsi di tante mutazioni indipendenti; i punteggi risultanti esprimono quanto sia più probabile che l’appaiamento di una coppia di aminoacidi sia dovuta ad omologia piuttosto che al casoLe matrici BLOSUM non sono invece basate esplicitamen-te su un modello evolutivo delle mutazioni; ciascun blocco è ottenuto dall’osservazione diretta di una famiglia di proteine correlate (quindi probabilmente legate evolu-tivamente), ma senza valutare esplicitamente la loro somiglianza

43

PAM o BLOSUM PAM o BLOSUM 2 2L’indice PAM crescente indica score per proteine più “distanti” tra loro, esprimendo una distanza evolutiva; l’indice BLOSUM crescente indica proteine più simili tra loro, esprimendo il valore minimo di conservazione del BLOCKLe PAM tendono a premiare sostituzioni aminoacidiche derivanti da mutazioni di singola base, penalizzando le sostituzioni che implicano cambi di codone più complessi, più che motivi strutturali degli aminoacidi, come fanno invece le BLOSUM

44

PAM o BLOSUM PAM o BLOSUM 3 3Il confronto fra PAM e BLOSUM, ad un livello di sostituzioni paragonabili, indica che i due tipi di matrice producono risultati similiIn genere, le matrici BLOSUM sono ritenute più adatte per effettuare ricerche di similarità di sequenzaBLOSUM62BLOSUM62 è la matrice impostata di default nei programmi di ricerca di similaritàÈ importante però sempre scegliere la matrice più adatta in base alla distanza filogenetica tra le sequen-ze da confrontarePer sequenze vicine (organismi vicini), PAM con indice basso o BLOSUM con indice altoPer sequenze distanti, PAM con indice alto e BLOSUM con indice basso

45

Programmazione dinamica:Programmazione dinamica:L’algoritmo di Needleman e Wunsch L’algoritmo di Needleman e Wunsch 1 1

Una volta selezionato un metodo per assegnare un punteggio ad un allineamento, è necessario definire un algoritmo per stabilire il(/i) miglior(/i) allineamento(/i) tra due sequenzeLa ricerca esaustiva fra tutti i possibili allineamenti è generalmente non praticabile

Per due sequenze, lunghe rispettivamente 100 e 95 nucleotidi, vi sono 55 milioni di allineamenti possibili, nel caso di cinque gap inseriti nella sequenza più breve

L’approccio tramite ricerca esaustiva diventa rapida-mente intrattabile

Uso della programmazione dinamicaprogrammazione dinamica: si suddivide il problema in più sottoproblemi di dimensione “ragionevole”, le cui soluzioni vanno ricombinate a costituire la soluzione del problema originale

46


S. B. Needleman e C. D. Wunsch, nel 1970, furono i primi a risolvere il problema con un algoritmo in grado di trovare similarità globalisimilarità globali in un tempo proporzionale al prodotto delle lunghezze delle due sequenzeLa chiave per comprenderne l’approccio consiste nel-l’osservare come il problema dell’allineamento possa essere suddiviso in sottoproblemi

47


EsempioEsempio: allineare CACGA e CGA, con l’ipotesi di pena-lizzare uniformemente gap e non corrispondenze

Possibili scelte da effettuare relativamente al primo carattere:

1) Posizionare un gap al primo posto nella prima sequenza (controintuitivo, dato che la prima sequenza è più lunga)

2) Posizionare un gap al primo posto nella seconda sequenza3) Allineare i primi due caratteri

Nei primi due casi, il punteggio di allineamento per la prima posizione sarà uguale alla gap penalty Nel terzo caso, il punteggio di allineamento per la prima posizione sarà uguale al punteggio di corrispondenzaIl resto del punteggio dipenderà, in entrambi i casi, da come verrà allineata la parte rimanente delle due sequenze

48


Esempio (continua)Esempio (continua)

Se conoscessimo il punteggio per il miglior allineamento ottenibile tra le parti di sequenza rimanenti, potremmo facilmente calcolare il miglior punteggio complessivo re-lativo ad ognuna delle tre scelte effettuate

49

Prima PosizionePrima Posizione PunteggioPunteggio Sequenze da allineareSequenze da allineare

C C

1 ACGA GA

C

1 CACGA GA

C

1 ACGA CGA


Esempio (continua)Esempio (continua)Supponendo di tentare l’allineamento a partire dal-l’ipotesi in cui si allineano i due caratteri iniziali (senza inserimento di gap), resta da calcolare il punteggio di allineamento delle sequenze ACGA e GA In questa operazione, più volte si presenterà la neces-sità di calcolare punteggi relativi a sottosequenze (es. ACGA e GA)La programmazione dinamica utilizza una tabella in cui si memorizzano i punteggi parziali di allineamento, per evitare di ricalcolarli ogni volta

50


EsempioEsempio: tabella per l’al-lineamento delle sequen-ze ACAGTAG e ACTCG, dove la gap penalty è 1 ed il punteggio di non/corri-spondenza è 0/1

51

A C T C G

0 1 2 3 4 5

A 1

C 2

A 3

G 4

T 5

A 6

G 7

L’algoritmo di programmazione dinamica calcola gli al-lineamenti ottimali fra sequenze riempiendo una tabel-la con i punteggi parziali

Gli assi orizzontale e verticale descrivono, rispettivamen-te, le due sequenze da allineare


52

L’allineamento delle due sequenze equivale a costruire un percorso che va dall’angolo in alto a sinistra all’angolo in basso a destra della tabella

Uno spostamento orizzontale rappresenta un gap nella sequenza verticale e viceversaUno spostamento lungo la diagonale rappresenta l’alli-neamento dei relativi nucleotidi nelle due sequenze

La prima riga e la prima colonna della tabella sono inizializzate con i multipli della gap penalty (dato che ogni gap aggiunge una penalità al punteggio totale di allinea-mento)


53

Come si calcolano gli altri elementi della tabella?L’elemento in posizione (2,2) si calcola sondando le seguenti tre possibilità:1) Sommando il valore della casella a sinistra, in posizione (2,1),

alla gap penalty, il che equivale a considerare un gap nella sequenza verticale

2) Sommando il valore della casella superiore, in posizione (1,2), alla gap penalty, il che equivale a considerare un gap nella sequenza orizzontale

3) Sommando il valore dell’elemento diagonale in posizione (1,1) al punteggio di corrispondenza o alla penalità di non corri-spondenza (corrispondenza, in questo caso) per i due nucleo-tidi in esame, il che rappresenta un allineamento

Si calcola infine il valore massimo fra quelli ottenuti per le tre opzioni (2,2,1) e lo si assegna all’elemento (2,2)


54

Si può quindi procedere al riempimento dell’intera seconda riga, per poi passare alla riga successiva, fino a completare la tabella

A C T C G

0 1 2 3 4 5

A 1 1 0 1 2 3

C 2 0 2 1 0 1

A 3 1 1 2 1 0

G 4 2 0 1 2 2

T 5 3 1 1 1 2

A 6 4 2 0 1 1

G 7 5 3 1 0 2

EsempioEsempioN(3,5) max{(11),(21),(11)} max{0,3,0)} 0


55

Completata la tabella, il valore contenuto nell’angolo in basso a destra rappresenta il punteggio per l’allinea-mento ottimo tra le due sequenze (2, nel caso del-l’esempio)NotaNota: Il punteggio è stato determinato senza dover assegnare un punteggio in modo esaustivo a tutti i possibili allineamenti tra le due sequenzeCon la tabella dei punteggi parziali è possibile rico-struire gli allineamenti ottimali (in generale più di uno) tra le due sequenze

Tracciare un percorso dalla posizione più in basso a Tracciare un percorso dalla posizione più in basso a destra a quella più in alto a sinistradestra a quella più in alto a sinistra


56

Per il valore N(7,5) esiste di nuovo una sola possibilità, che porta, per allineamento, all’elemento N(6,4)1 (con penalità di non corrispon-denza fra i due nucleotidi)Il procedimento deve essere reiterato finché tutti i possi-bili percorsi vengano comple-tati fino alla posizione (1,1)

A C T C G

0 1 2 3 4 5

A 1 1 0 1 2 3

C 2 0 2 1 0 1

A 3 1 1 2 1 0

G 4 2 0 1 2 2

T 5 3 1 1 1 2

A 6 4 2 0 1 1

G 7 5 3 1 0 2

EsempioEsempioIl valore N(8,6)2 potrebbe essere stato ottenuto seguendo tre diversi percorsi, ma l’unico che può produrre il valore 2 è quello che procede per allineamento provenendo da N(7,5)1


57

Per convertire un percorso in un allineamento occorre percorrere a ritroso ogni cammino da (n1,m1) a (1,1), se n ed m rappresentano le lunghezze delle due sequenze da allineare, ricordando che:

un movimento verticale rappresenta un gap nella sequenza lungo l’asse orizzontaleun movimento orizzontale rappresenta un gap nella sequenza lungo l’asse verticaleun movimento diagonale rappresenta un allineamento dei nucleotidi delle due sequenze nella posizione corrente

EsempioEsempioGGCGAGTCGTAG


58

A C T C G

0 1 2 3 4 5

A 1 1 0 1 2 3

C 2 0 2 1 0 1

A 3 1 1 2 1 0

G 4 2 0 1 2 2

T 5 3 1 1 1 2

A 6 4 2 0 1 1

G 7 5 3 1 0 2

TCGGTAGTCGAGTAGCTCGCAGTAGACACTCGTCGACAGTAGACAGTAG

NotaNota: Seguendo tutti i percorsi (n1,m1)(1,1) nella tabella dei punteggi parziali, si possono ricostruire tutti i possibili allineamenti ottimali fra le due sequenze

L’algoritmo di Needleman e WunschL’algoritmo di Needleman e WunschEsempio Esempio 1 1

59

C G A

0 1 2 3

C 1 1 0 1

A 2 0 1 1

C 3 1 0 1

G 4 2 0 0

A 5 3 1 1

Calcolare l’allineamento fra le sequenze Calcolare l’allineamento fra le sequenze CACGACACGA ee CGACGA

N(5,2) max{(41),(11),(30)} max{5,2,3)} 2N(5,3) max{(21),(01),(11)} max{3,1,0)} 0N(5,4) max{(01),(11),(00)} max{1,0,0)} 0N(6,2) max{(51),(21),(40)} max{6,3,4)} 3N(6,3) max{(31),(01),(20)} max{4,1,2)} 1N(6,4) max{(11),(01),(01)} max{2,1,1)} 1

N(2,2) max{(11),(11),(01)} max{2,2,1)} 1N(2,3) max{(11),(21),(10)} max{0,3,1)} 0N(2,4) max{(01),(31),(20)} max{1,4,2)} 1N(3,2) max{(21),(11),(10)} max{3,0,1)} 0N(3,3) max{(01),(01),(10)} max{1,1,1)} 1N(3,4) max{(11),(11),(01)} max{0,2,1)} 1N(4,2) max{(31),(01),(21)} max{4,1,1)} 1N(4,3) max{(11),(11),(00)} max{2,0,0)} 0N(4,4) max{(01),(11),(10)} max{1,0,1)} 1

L’algoritmo di Needleman e WunschL’algoritmo di Needleman e WunschEsempio Esempio 2 2

60

C G A

0 1 2 3

C 1 1 0 1

A 2 0 1 1

C 3 1 0 1

G 4 2 0 0

A 5 3 1 1

Calcolare l’allineamento fra le sequenze Calcolare l’allineamento fra le sequenze CACGA CACGA ee CGA CGA

Due allineamenti ottimi con score 1

CGACGACACGACACGA

CCGAGACACGACACGA

Due percorsi possibiliDue percorsi possibili

Allineamenti globali e locali Allineamenti globali e locali 1 1

61

Allineamento globaleAllineamento globale: si tenta di allineare il numero massi-mo di caratteri fra le due sequenze; candidate ideali sono le sequenze di lunghezza simileAllineamento localeAllineamento locale: si tenta di allineare “pezzi” di sequenze con alto grado di similitudine; l’allineamento termina quando termina “l’isola di accoppiamento”; candidate ideali sono sequenze con lunghezze significativamente diverse, che presentano regioni fortemente conservate


62

L’algoritmo di Needleman e Wunsch esegue l’allineamento allineamento globale globale fra sequenze, cioè le confronta nella loro interezza

La gap penalty è fissata, senza pesare la posizione dei gap (collocati all’interno o alle estremità delle sequenze)

Non sempre è il modo migliore per effettuare l’allineamentoEsempioEsempio: supponiamo di voler cercare un’occorrenza della sequenza breve ACGT all’interno della sequenza più lunga AAACACGTGTCT (operazione nota come pattern matchingpattern matching)

Dei diversi allineamenti possibili, l’allineamento di interesse è:AAACACGTGTCTACG T Quando si cerca il miglior allineamento tra una sequenza corta ed un intero genoma (per isolare un gene, ad esempio) occorre evitare di penalizzare i gap che appaiono in una o in entrambe le estremità di una sequenza


63

I gap terminali sono di solito il risultato di un’acquisizione di dati incompleta e non hanno significato biologico

è opportuno trattarli diversamente dai gap interniallineamento semiglobaleallineamento semiglobale

Come occorre modificare l’algoritmo di programmazione dinamica per cablare questo nuovo comportamento?Con l’algoritmo di Needleman e Wunsch, per le sequenze ACTCG e ACAGTAG, muovendosi prima verticalmente verso la riga inferiore della tabella e quindi orizzontalmente sull’ul-tima riga fino a raggiungerne l’ultimo elemento, si ottiene

ACTCGACTCGACAGTAGACAGTAG


64

Infatti, dall’angolo in alto a sinistra della tabella, ogni movimento verso il basso aggiunge un ulteriore gap nell’al-lineamento all’inizio della prima sequenza……e, poiché ogni gap aggiunge una gap penalty al punteggio totale di allineamento, la prima colonna è stata inizializzata con i multipli della gap penaltyViceversa, se si vuole consentire la presenza di gap iniziali nella prima sequenza senza assegnare penalità

Occorre inizializzare la prima colonna della tabella con tutti zero

Ugualmente, inizializzando la prima riga della tabella con tutti zero, si consentono gap iniziali nella seconda sequenza senza assegnare penalità


65

Per ammettere gap alla fine di una sequenza senza asse-gnare penalità serve interpretare diversamente il significato di alcuni spostamenti all’interno della tabellaEsempioEsempio: supponiamo di avere il seguente allineamento

ACACTGATCGACACTGATCGACACTGACACTG

Utilizzandolo per costruire un percorso nella tabella dei punteg-gi parziali, dopo aver allineato i primi sei nucleotidi, si sarebbe raggiunta la riga inferiorePer raggiungere l’angolo inferiore destro si dovrebbero esegui-re quattro spostamenti orizzontaliConsentire movimenti orizzontali nell’ultima riga della tabella senza assegnare gap penaltyUgualmente, movimenti verticali sull’ultima colonna non pena-lizzati


66

A C A C T G A T C G

0 0 0 0 0 0 0 0 0 0 0

A 0 1 0 1 0 0 0 1 0 0 0

C 0 0 2 1 2 1 0 0 1 1 0

A 0 1 1 3 2 2 1 1 0 1 1

C 0 0 2 2 4 3 2 1 1 1 1

T 0 0 1 2 3 5 4 3 2 1 1

G 0 0 0 1 2 3 6 6 6 6 6


67

Riassumendo:Inizializzando la prima riga e la prima colonna della tabella dei punteggi parziali con il valore zero……e permettendo movimenti non penalizzati orizzontali e verticali, rispettivamente, nell’ultima riga e nell’ultima colonna della tabellaSi esegue un allineamento semiglobaleSi esegue un allineamento semiglobale

Sfortunatamente, talvolta, nemmeno gli allineamenti semiglobali offrono la flessibilità necessaria per affrontare tutti i problemi connessi all’allineamento di sequenze

L’algoritmo di Smith e Waterman L’algoritmo di Smith e Waterman 1 1

68

Nel 1981, T. F. Smith e M. S. Waterman svilupparono un nuovo algoritmo in grado di individuare anche similarità localiEsempioEsempio: supponiamo di avere una lunga sequenza di DNA e di voler isolare ogni sottosequenza simile ad ogni parte del genoma del lievito

Un allineamento semiglobale non è sufficiente perché verrà comunque penalizzato in ogni posizione di non corrispondenzaAnche se esistesse una sottosequenza interessante, perché parzialmente coincidente con il genoma del lie-vito, tutti i nucleotidi non corrispondenti concorrereb-bero a generare un punteggio di allineamento insoddi-sfacenteAllineamento localeAllineamento locale


69

EsempioEsempio: Si considerino le due sequenze AACCTATAGCT e GCGATATA

Utilizzando l’algoritmo di allineamento semiglobale con gap penalty pari a 1 e punteggi di non/corrispondenza uguali a 1/1, si ottiene l’allineamento:

AACCTATAGCTGCAATATA

piuttosto scadente dato che quattro delle prime cinque posizioni sono non corrispondenze o gap, così come le ultime tre posizioni (2)Tuttavia, si rileva una regione di corrispondenza al centro delle due sequenze: la sottosequenza TATAModificare l’algoritmo per identificare corrispondenze fra sottosequenze, ignorando non corrispondenze e gap prima e dopo la regione di corrispondenza


70

Per l’allineamento locale: Inizializzare a zero prima riga e prima colonna (come nell’allineamento semiglobale)Considerare penalità per non corrispondenza pari a 1Inserire uno zero nella tabella laddove tutti gli altri metodi restituiscono un punteggio negativo

Dopo aver costruito la tabella:Trovare il punteggio parziale massimoProcedere all’indietro, per ricostruire l’allineamento, fino a quando non si raggiunge uno zeroL’allineamento locale risultante rappresenterà la migliore sottosequenza di corrispondenza tra le due sequenze date


71

A A C C T A T A G C T

0 0 0 0 0 0 0 0 0 0 0 0

G 0 0 0 0 0 0 0 0 0 1 0 0

C 0 0 0 1 1 0 0 0 0 0 2 1

G 0 0 0 0 0 0 0 0 0 1 1 1

A 0 1 1 0 0 0 1 0 1 0 0 0

T 0 0 0 0 0 1 0 2 1 0 0 1

A 0 1 1 0 0 0 2 1 3 2 1 0

T 0 0 0 0 0 1 1 3 2 2 1 2

A 0 1 1 0 0 0 2 2 4 3 2 1

Concludendo… quando si lavora con sequenze lunghe diver-quando si lavora con sequenze lunghe diver-se migliaia, o milioni, di nucleotidi, i metodi di allineamento se migliaia, o milioni, di nucleotidi, i metodi di allineamento locale possono identificare sottosequenze corrispondenti, locale possono identificare sottosequenze corrispondenti, impossibili da trovare per mezzo di allineamenti globali o impossibili da trovare per mezzo di allineamenti globali o semiglobali semiglobali

I dati biologici I dati biologici

72

1965: Margareth Dayhoff compila un atlante di proteine omologhe, studiando le relazioni tra le sequenze primarie; viene reso pubblico in versione elettronica nel 1970 nella banca dati NBRF (National Biomedical Research Foundation)Inizio anni 70: nasce la tecnologia del DNA ricombinante, che permette di manipolare le sequenze nucleotidiche e di com-prendere la struttura, la funzione e l’organizzazione del DNA Fine anni 70: pubblicazione dei primi dati genomici, con le prime sequenze nucleotidiche codificanti liberamente accessibili attra-verso la rete (ristretta a poche università) 1980 [Kurt Stueber]: nasce una banca dati nel Laboratorio Europeo di Biologia Molecolare (EMBL) ad Heidelberg1982 [Walter Goad]: nasce una banca dati simile negli USA, che darà vita alla GenBank1986: nel National Institute of Genetics a Mishima (Giappone) nasce un mirror della GeneBank, la DDBJ2001: Il Consorzio Pubblico Internazionale e la Celera Genomics forniscono i dati del genoma umano completo

I database biologici I database biologici 1 1

73

Lo sviluppo delle biotecnologie molecolari ha portato alla produzione di enormi quantità di dati biologiciI database sono progettati come contenitori, costruiti per immagazzinare dati in modo efficiente e razionale, per ren-derli facilmente accessibili agli utentiIl fine ultimo è quello di recuperare ed analizzare i dati mediante gli appositi strumenti di cui ciascun database disponeNumerose sono oggi le banche dati biologiche esistenti:

Banche dati primarie Banche dati primarie (sequenze nucleotidiche e aminoacidiche)Banche dati specializzate Banche dati specializzate (domini e motivi proteici, strutture proteiche, geni, trascrittoma, profili di espressione, pathway metaboliche, etc.)

Valued Acer Customer

Domini proteici: regioni compatte semi-indipendenti e con funzioni distintive, collegate al resto della proteina da una porzione di catena polipeptidica che serve da cernieraTrascrittoma: termine analogo a genoma, proteoma e metaboloma, è l'insieme di tutti i trascritti (RNA messaggeri o mRNA) di un dato organismo o tipo cellularePathway metabolico o più semplicemente pathway è l'insieme delle reazioni chimiche coinvolte in uno o più processi di anabolismo o catabolismo all'interno di una cellula


74

Le banche dati biologiche raccolgono informazioni e dati derivati da:

LetteraturaAnalisi di laboratorio (in vitroin vitro e in vivoin vivo)Analisi bioinformatiche (in silicoin silico)

Molte banche dati biologiche sono fruibili da parte della comunità scientifica in formato flatflatfilefile, cioè file se-quenziali nei quali ogni record di informazione è ripor-tato su una o più linee consecutive identificate da un particolare codiceTali file sono dunque semplici file di testo strutturati in modo tale da essere analizzabili mediante opportuni tool in grado di estrarre le informazioni di interesseAlternativa: dati in formato HTMLHTML o XMLXML, di facile consultazione via browser


75

Ogni banca dati è caratterizzata da un elemento bio-logico centrale che costituisce l’oggetto intorno al quale viene costruita la entryentry principale del databaseCiascuna entry raccoglie quindi le informazioni che caratterizzano l’elemento centrale (attributi)Una entry di una banca dati di sequenze nucleotidiche potrebbe contenere, oltre alla sequenza di una mole-cola di DNA,

il nome dell’organismo cui la sequenza appartienela lista degli articoli scientifici che riportano dati su quella sequenzale caratteristiche funzionali (cioè se si tratta di un gene o di una sequenza non codificante)altra informazione ritenuta di interesse


76

Le banche dati mettono a disposizione strumenti bioin-formatici per l’elaborazione dei dati in esse contenuti, tra i quali:

Sistemi di interrogazione (ENTREZENTREZ, associato a GenBank, SRSSRS, per EMBL, DBGETDBGET, per DDBJ)Tool per lo screening (BLASTBLAST, FASTAFASTA)Tool per l’allineamento multiplo di sequenze (ClustalWClustalW, AntiClustalAntiClustal, TTCoffeeCoffee, ProbConsProbCons)Tool per l’identificazione di esoni ed elementi regolatori che caratterizzano un gene (GenScanGenScan, PromoserPromoser)…

Banche dati primarie Banche dati primarie 1 1

77

Le banche dati primarieprimarie contengono sequenze nucleo-tidiche (DNA e RNA) o aminoacidiche (proteine)Le principali banche dati primarie sono:

GenBankGenBank (NCBI NCBI National Center for Biotechnology National Center for Biotechnology InformationInformation, fondato nel 1982 a Bethesda, USA, http://www.ncbi.nlm.nih.gov); il database standard contie-ne 150.141.354.858 basi in 162.886.727 sequenzeEMBL datalibrary EMBL datalibrary (costituita nel 1980 all’EMBL EMBL European Molecular Biology LaboratoryEuropean Molecular Biology Laboratory, di Heidelberg, Germania, http://www.embl.de)DDBJDDBJ (DNA DataBase of JapanDNA DataBase of Japan, nato nel 1986 dal National Institute of Genetics National Institute of Genetics a Mishima in Giappone, http://www.ddbj.nig.ac.jp/index-e.html)

http://www.ncbi.nlm.nih.gov/

http://www.ncbi.nlm.nih.gov/

http://www.embl.de/

http://www.ddbj.nig.ac.jp/index-e.html

Banche dati primarie Banche dati primarie 2 2

78

Fra le tre banche dati biologiche è stato stipulato un accordo internazionale affinché il contenuto dei dati di sequenza venga mantenuto consistente (gli aggiorna-menti quotidiani apportati in ciascuna banca vengono automaticamente trasmessi alle altre)I tre istituti cooperano, inoltre, al fine di condividere e rendere pubblicamente disponibili tutti i dati di cui dispongono e che differiscono tra loro solamente per il formato con cui vengono rilasciati

NCBI NCBI 1 1

79

NCBI NCBI 2 2

80

È un database di sequenze genetiche di proprietà del National Institute of Healt National Institute of Healt statunitense, una collezione annotata di tutte le sequenze di DNA disponibili pub-blicamenteAccesso ai dati attraverso ENTREZENTREZ, sistema di inter-rogazione delle diverse basi dati gestite dall’NCBI, che costituisce quindi un hub completo per la ricerca di informazioni

Disponibile via web per la ricerca e l’estrazione dei dati da banche dati di sequenze nucleotidiche, proteiche, dalla banca dati bibliografica PubMedPubMed, dalla banca dati delle malattie mendeliane OMINOMIN, e da ogni banca dati sviluppata dall’NCBISistema chiuso: non è possibile ottenere il software che gestisce il sistema

NCBI NCBI 3 3

81

Principali database in NCBINCBI:GeneGene: contiene dati inerenti i geni di tutte le specie caratterizzate, quali la struttura genica ed il contesto genomico, le ontologie, le interazioni con altri geni ed i link alle sequenze ed alle relative pubblicazioni scien-tificheNucleotideNucleotide: contiene le sequenze nucleotidiche di tutte le specie caratterizzate, siano esse codificanti o menoProteinProtein: ha la stessa struttura di NucleotideNucleotide, ma è relativo alle sequenze aminoacidichePubMedPubMed: è il database delle pubblicazioni scientifiche di carattere biologico e biomedico; per ogni articolo è disponibile l’abstract; PubMed Central PubMed Central contiene articoli completi scaricabili gratuitamente

Valued Acer Customer

In informatica, il termine ontologia si riferisce specificamente ad un tentativo di formulare una concettualizzazione esaustiva e rigorosa nell'ambito di un dato dominio. Si tratta generalmente di una struttura dati gerarchica che contiene tutte le entità rilevanti, le relazioni esistenti fra di esse, le regole, gli assiomi ed i vincoli specifici del dominio.

NCBI NCBI 4 4

82

EntrezEntrez offre anche la possibilità di effettuare ricerche incrociate per stabilire un collegamento diretto tra i vari database di NCBI (sequenzastrutturamappa geneticaletteratura)

Banche dati proteiche Banche dati proteiche 1 1

83

Le banche di sequenze proteiche possono essere ottenute in seguito a:

Determinazione diretta della sequenza proteicaTraduzione di sequenze nucleotidiche per le quali sia stata individuata o predetta la funzione del gene codificante la proteinaStudi di espressione genicaCristallografia e determinazione delle strutture secondarie e terziarie

Banche dati proteiche Banche dati proteiche 2 2

84

SWISS-PROTSWISS-PROT (Protein knowledgebase, 1986): banca dati di riferimento sviluppata a Ginevra; contiene informazioni accuratamente annotate (spesso a mano)TrEMBLTrEMBL (Translated EMBL): risultato della traduzione automatica in aminoacidi di tutte le sequenze annotate nella banca dati EMBL come codificanti proteine; supplemento a SWISS-PROTPIRPIR (Protein Information Resource): soprattutto indi-rizzato a definire gli standard di annotazioneInsieme hanno formato il consorzio UNIPROTUNIPROT, repo-sitory centralizzato di tutte le sequenze proteiche

Banche dati specializzateBanche dati specializzate

85

Le banche dati specializzatespecializzate si sono sviluppate succes-sivamente Raccolgono insiemi di dati omogenei dal punto di vista tassonomico e/o funzionale, disponibili nelle banche dati primarie e/o in letteratura, o derivanti da approcci sperimentali, rivisti e annotati con informazioni di valore aggiuntoEsempiEsempi:

wwPDBwwPDB (world wide Protein Data Bank), banca dati di riferimento per i dati strutturali 3D di proteine, comprendente le coordinate atomiche determinate attraverso analisi cristal-lografiche ai raggi X, analisi NMR, etc.Database di sequenze genomiche: GDBGDB (uomo), MGI MGI (topo), SGDSGD (lievito)Database di geni e trascritti: UniGeneUniGene, LocusLinkLocusLink, dbESTdbEST, etc.

Ricerche in database Ricerche in database 1 1

86

Gli allineamenti di sequenze possono rappresentare un prezioso strumento per confrontare due sequenze noteUn uso molto più comune degli allineamenti, tuttavia, consiste nella ricerca all’interno di un database, contenente dati biologici, delle sequenze che sono simili ad una particolare sequenza di interesseI risultati della ricerca, che consistono in altre sequen-ze che si allineano bene con (e quindi sono simili a) la sequenza querysequenza query, possono infatti fornire:

un’indicazione sul ruolo funzionale della sequenza in esameindizi sulla sua regolazione ed espressione in relazione con sequenze simili in altre specie


87

EsempioEsempio: sequenziamento di una parte del genoma umano che potrebbe costituire un gene non precedentemente iden-tificatocomparazione del gene “putativo” con le milioni di sequenze depositate a GenBankGenBank presso l’NCBI

Nell’eseguire ricerche all’interno di un database biolo-gico, la dimensione stessa del database, e dei singoli dati in esso contenuti, spesso preclude l’approccio ovvio che consiste nell’allineare la sequenza query con tutte le altre sequenze, per ottenere i punteggi di allineamento più alti

Si utilizzano particolari tecniche di indicizzazione e ricerche guidate da euristiche


88

Molti degli algoritmi usati comunemente non garanti-scono il raggiungimento dell’ottimo, ma forniscono confidenza statistica sul reperimento della maggior parte delle sequenze che si allineano bene con la sequenza query

BLAST BLAST (Basic Local Alignment Search ToolBasic Local Alignment Search Tool)FASTA FASTA (per FastFastAllAll, un’estensione di FASTFASTNN e FASTFASTPP che erano dedicati, rispettivamente, alla ricerca di allineamenti in catene nucleotidiche e polipeptidiche)

L’efficienza è un prerequisito ed un connotato fondamentale per questi metodi, che sono divenuti un supporto impre-scindibile per la biologia molecolare

BLAST e variantiBLAST e varianti

89

Uno degli strumenti più conosciuti e più comunemente usati per la ricerca di sequenze in database biologici è BLASTBLAST, introdotto da S. Altschul et al. nel 1990BLASTBLAST esegue la ricerca degli allineamenti locali più lunghi, senza gap, ovvero rileva sottosequenze del database simili a sottosequenze della sequenza queryBLASTBLAST 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 essaNe esistono diverse varianti e versioni, per la ricerca di sequenze nucleotidiche e proteiche

BLASTP, BLASTNBLASTP, BLASTN, BLASTX, TBLASTN (, BLASTX, TBLASTN (Translated BLAST Translated BLAST NucleotideNucleotide), BLAST 2.0, PSI), BLAST 2.0, PSIBLASTBLAST

BLASTNBLASTN

90

Ricerca le corrispondenze di sequenze nucleotidiche, usando la semplice matrice di score

con penalità uniformi per transizioni e transversioni, per assegnare i punteggi agli allineamenti senza gap

A T C G

A 5 4 4 4

T 4 5 4 4

C 4 4 5 4

G 4 4 4 5

BLASTP BLASTP 1 1

91

Ricerca le corrispondenze di sequenze proteiche, usando le matrici PAM o BLOSUM per assegnare i pun-teggi agli allineamenti senza gap

Suddivide la sequenza query in paroleparole o sottosequenze di lunghezza prefissata (4, lunghezza di default)Utilizza una finestra scorrevole, di uguale dimensione della lunghezza della parola, lungo l’intera sequenza

EsempioEsempio: la query proteica AILVPTV produrrebbe quattro parole diverse AILV, ILVP, LVPT, VPTV

Le parole composte principalmente da aminoacidi comu-ni vengono eliminateLe parole rimaste vengono ricercate all’interno delle sequenze del database

BLASTP BLASTP 2 2

92

Quando si trova una corrispondenza, la corrispondenza viene estesa in entrambe le direzioni, finché il punteggio di allineamento non scende sotto una data soglia

L’estensione prevede l’aggiunta di nuovi residui alla regione di corrispondenza ed il ricalcolo del punteggio in accordo con la matrice di punteggio usataLa scelta del valore di soglia è un parametro importante perché determina la probabilità che le sequenze risultanti siano omologhi biologicamente rilevanti della sequenza queryEsempioEsempio: Ricerca di AILVPTV AILVMVQGWALYDFLKCRAILVGTVIAML…

AILVPTVMVQGWALYDFLKCRAILVGTVIAML…

BLAST e varianti (cont.)BLAST e varianti (cont.)

93

Numerosi algoritmi di allineamento di sequenza e di ricerca in database sono stati sviluppati per tipi specifici di dati

BLASTNBLASTN, , BLASTXBLASTX: : consentono rispettivamente la ricerca all’interno di database di sequenze di nucleotidi e la traduzione dalla sequenza nucleotidica in sequenza proteica prima della ricercaTBLASTNTBLASTN: : confronta la proteina query con il database di sequenze nucleotidiche; per effettuare questo tipo di confronto le sequenze nucleotidiche nel database vengono dinamica-mente tradotte in sequenze aminoacidiche e successivamente confrontate con la proteina queryBLAST 2.0BLAST 2.0: inserisce gap per ottimizzare l’allineamentoPSIPSIBLASTBLAST: riassume i risultati della ricerca di sequenze in matrici di punteggio matrici di punteggio dipendenti dalla posizione, utili per individuare omologhi remoti e per la modellizzazione e la predizione della struttura delle proteine

FASTA e varianti FASTA e varianti 1 1

94

Gli algoritmi FASTAFASTA costituiscono un’altra famiglia di strumenti di allineamento e di ricerca

Eseguono allineamenti locali con gap tra sequenze dello stesso tipoSono più sensibili degli algoritmi BLASTlike, special-mente per sequenze query ripetitiveSono computazionalmente più onerosi

Anche in questo caso la sequenza viene suddivisa in parole

di lunghezza 46 per le sequenze genomichedi lunghezza 12 per le sequenze polipeptidiche

Successivamente viene costruita una tabella per la sequenza query che mostra le posizioni di ogni parola all’interno della sequenza


95

EsempioEsempioSi consideri la sequenza aminoacidica

FAMLGFIKYLPGCM

che, per parole di lunghezza 1, produrrebbe la seguente tabella:

La colonna della fenilalaninafenilalanina (F) contiene i valori 1 e 6, che corrispondono alle posizioni di F nella sequenza query

A C D E F G H I K L M N P Q R S T V W Y2 13 1 5 7 8 4 3 11 9

6 12 10 14


96

Esempio (continua)Esempio (continua)Per confrontare la sequenza query con la sequenza bersaglio TGFIKYLPGACT, si costruisce, relativamente a quest’ultima, una seconda tabella che mette in relazione le posizioni rispettive degli aminoacidi

Si consideri la posizione 2, relativa al residuo di glicinaglicina (G)Nella sequenza query, la G è presente alle posizioni 5 e 12Le distanze tra 5 e 12 e la posizione della prima G nella sequenza bersaglio (2) producono i due valori 3 e 10Analogamente in corrispondenza della seconda G, in posi-zione 9, si ottengono i valori (59)4 e (129)3

1 2 3 4 5 6 7 8 9 10 11 12

T G F I K Y L P G A C T3 2 3 3 3 3 3 4 8 2

10 3 3 3


97

Esempio (continua)Esempio (continua)Agli aminoacidi che non si trovano nella sequenza query, come la treoninatreonina (T), non sono assegnati valori (le colonne relative nella tabella bersaglio possono essere eliminate)

L’elevato numero di elementi con distanza 3 suggerisce che spostando di tre posizioni verso sinistra la sequenza query (o di tre posizioni verso destra la sequenza bersaglio) si può ottenere un allineamento ragionevole

FAMLGFIKYLPGCM

TGFIKYLPGACT


98

Confrontando le tabelle compensate delle due sequen-ze, si possono trovare rapidamente le aree di identità Tali aree vengono quindi unite a formare sequenze più lunghe, che vengono allineate usando l’algoritmo di Smith e WatermanTuttavia, poiché l’allineamento è inizialmente vincolato ad una regione nota di due sequenze simili, FASTAFASTA è molto più veloce rispetto all’eseguire con la program-mazione dinamica un allineamento completo tra la sequenza query e tutti i possibili bersagli

Punteggi di allineamento Punteggi di allineamento 1 1

99

Anche se la ricerca in un database produrrà sempre un risultato, senza informazioni aggiuntive, le sequenze trovate non potranno essere sempre considerate cor-relate con la sequenza queryIl punteggio di allineamento è il principale indicatore di quanto i risultati della ricerca siano simili alla sequenza query

I punteggi di allineamento variano in base allo stru-mento di ricerca utilizzatoNon rappresentano, da soli, un indicatore sufficiente a garantire la correlazione fra sequenze


100

Se il risultato di una ricerca ha punteggio di allinea-mento S è lecito chiedersi:Dato un insieme di sequenze non correlate alla sequenza Dato un insieme di sequenze non correlate alla sequenza query, qual è la probabilità di trovare casualmente una query, qual è la probabilità di trovare casualmente una corrispondenza con punteggio di allineamento corrispondenza con punteggio di allineamento SS? ? Per affrontare il problema, i motori di ricerca in data-base biologici forniscono ulteriori punteggi, noti come E (o valoreE) o P, per ogni risultato

Sono diversi:E è proporzionale al numero atteso di sequenze casuali con punteggio SP è la probabilità che esistano una o più sequenze casuali con punteggio S

• Sono strettamente correlati e spesso hanno valori simili


101

Valori piccoli per E e P indicano come poco probabile che il risultato di una ricerca sia stato ottenuto casualmenteValori di E 103 sono considerati indicativi di risultati statisticamente significativiSpesso, gli algoritmi di allineamento forniscono risul-tati con E 1050

Forte probabilità di relazione evolutiva fra la sequenza query ed i risultati della ricerca

Allineamenti multipli Allineamenti multipli 1 1

102

Gli allineamenti multipli sono utili quando si osservano un certo numero di sequenze “simili”, per esempio per determinarne le frequenze di sostituzioneL’allineamento multiplo riassume la storia evolutiva di una famiglia di proteine

Quindi, si possono ricavare informazioni su:La conservazione dei residui dipendente dalla funzioneLa conservazione dei residui dipendente dalla struttura

Esempi di informazioni funzionali/strutturali che si ottengono da un allineamento multiplo:

Negli enzimi, le regioni maggiormente conservate corrispondono probabilmente al sito attivoUn pattern conservato di residui idrofobici alternati a residui idrofilici suggerisce un foglietto betaUn pattern conservato di residui idrofobici ogni 4 residui suggerisce l’esistenza di un alfa elica

Gli allineamenti multipli sono estremamente utili anche per la creazione delle matrici di punteggio, PAM e BLOSUM


103

Significato evolutivo dell’allineamento multiploSignificato evolutivo dell’allineamento multiplo

Esempio di allineamento multiplo di sequenzeEsempio di allineamento multiplo di sequenze


104

Le tecniche più semplici per eseguire allineamenti multipli sono estensioni logiche dei metodi di program-mazione dinamica (tipo Needleman e Wunsch)

Per allineare n sequenze occorre una griglia ndimen-sionaleLa complessità computazionale dei metodi di allinea-mento multiplo cresce rapidamente con il numero di sequenze da allineareAnche con notevole potenza di calcolo e parallelismo massiccio, gli allineamenti multipli rappresentano un problema intrattabile oltre le venti sequenze di media lunghezza e complessitàMetodi di allineamento guidati da euristiche

ClustalClustal


105

L’algoritmo ClustalClustal, proposto da Higgins e Sharp nel 1988, attua una tecnica di allineamento progressivoallineamento progressivo, allineando prima sequenze strettamente correlate, per poi aggiungere sequenze a divergenza crescente

Si costruisce un albero filogenetico per determinare il grado di similarità tra le sequenze da allineareUsando l’albero come guida, le sequenze strettamente correlate vengono allineate a coppie tramite program-mazione dinamica, fino a raggiungere l’allineamento multiplo completo


106

La selezione di un’opportuna matrice di punteggio è fondamentale nel caso di allineamenti multipli

L’utilizzo di una matrice di punteggio non appropriata genererà un allineamento scadenteUso di conoscenza a priori sul grado di similarità delle sequenze da allineare

In ClustalWClustalW, le sequenze sono pesate in base alla loro divergenza dalla coppia di sequenze più strettamente correlate e le gap penalty (per apertura ed estensione) e la scelta della matrice di punteggio si basano sul peso di ciascuna sequenzaAltra strategia per allineamenti multipli: non penaliz-zare gap allineati


107

Gli allineamenti multipli, così come quelli a coppie, sono basati esclusivamente sulla similarità nucleotidica o aminoacidica fra sequenzeLa similarità tra sequenze è un importante indicatore di analogie funzionali, ma spesso i biologi molecolari dispongono di ulteriori conoscenze sulla struttura o funzione di una particolare proteina o gene

Informazioni su struttura secondaria, presenza di regioni di loop superficiali, localizzazione di siti attivi, possono essere utilizzate per aggiustare “a mano” gli allineamenti multipli, allo scopo di produrre risultati biologicamente significativi

Concludendo… Concludendo… 1 1

108

Un allineamento fra due o più sequenze genetiche o polipeptidiche rappresenta un’ipotesi sul percorso at-traverso cui due sequenze omologhe si sono evolute divergendo dall’antenato comuneMentre il percorso evolutivo non può essere dedotto con certezza, gli algoritmi di allineamento possono essere usati per identificare “similarità” che hanno bassa probabilità di verificarsi per casoLa scelta della funzione di punteggio è cruciale per la qualità del risultato di allineamento

Uso di matrici di punteggio, quali PAM e BLOSUM

Concludendo… Concludendo… 2 2

109

L’algoritmo di programmazione dinamica di Needleman e Wunsch, per l’allineamento globale di sequenze, e la tecnica di Smith e Waterman, per l’allineamento locale, costituiscono le basi fondanti su cui sono stati costruiti numerosi algoritmi di ricerca in database

BLASTBLASTFASTAFASTAClustalClustal

Questi algoritmi usano tecniche di indicizzazione, euristiche e metodi di comparazione veloce per ottenere un confronto rapido fra una sequenza query ed un intero database di sequenze

Ricerche in database e allineamenti a coppie 1 È un errore madornale elaborare teorie prima di...

Documents

Transcript of Ricerche in database e allineamenti a coppie 1 È un errore madornale elaborare teorie prima di...