Tipi di allineamenti

La distanza di Levenshtein è definita tra stringhe che non hanno necessariamente la stessa lunghezza ed è il numero di “operazioni di edit” richieste per cambiare una stringa in un’altra.

Per operazioni di edit si intende una delezioni, un’inserzione o l’alterazione di un singolo carattere in entrambe le sequenze.

ag-tcc distanza di Levenshtein=3 cgctca

Misura delle similarità di sequenza:

La distanza di Hamming è definita tra due stringhe della stessa lunghezza ed è valutata calcolando il numero di posizioni con caratteri non corrispondenti

agtc distanza di Hamming=2

cgta

1° Esercizio:

Valutare la distanza di Hamming tra DECLENSION e RECREATION

SOLUZIONE:

DECLENSION

RECREATION

2° Esercizio:

Valutare la distanza di Levenshtein tra BIOINFORMATICS e CONFORMATION

SOLUZIONE:

BIOINFORMATICS

-CO-NFORMATION

Differenza tra i termini similarità ed omologia

Il termine omologia indica che due entità condividono una stessa origine filogenetica, da cui si sono evolute differenziandosi l’una dall’altra

Il termine similarità ha un significato più generale che indica una somiglianza prescindendo dalle ragioni che l’hanno determinata.

Questa similarità spesso è dovuta ad omologia ma può essere generata dal caso oppure da fenomeni di convergenza adattativa sia a livello morfologico sia a livello molecolare.

Ad esempio l’ala di un uccello e quella di un pipistrello si sono evolute indipendentemente l’una dall’altra e pertanto non sono omologhe.

Quindi l’omologia è una caratteristica qualitativa, che indica un’origine filogenetica comune.

La similarità è una caratteristica quantitativa che sulla base di qualche criterio comparativo indica un livello di somiglianza.

SIMILARITA’ DI SEQUENZE ED ALGORITMI DI ALLINEMANTO

L’allineamento dovrebbe portare all’appaiamento delle regioni simili condivise dalle due sequenze.

Vari sono i criteri che possono essere utilizzati per misurare la similarità tra due o più sequenze.

Il problema è che i concetti di similarità ed allineamento sono intimamente associati: infatti non si possono allineare sequenze senza definire dei criteri di similarità ed allo stesso tempo per valutare quanto due sequenze siano simili è necessario allinearle.

Comunque per allineare varie sequenze è necessario disporre anche di un metodo (che in informatica è definito algoritmo) che sulla base dei criteri di similarità sia in grado di produrre un allineamento.

Quindi

Per poter allineare delle sequenze abbiamo bisogno di due cose:

Definizione di criteri di similarità

Algoritmo

Se definissimo come criterio di similarità quello di valutare il numero di lettere che si appaiano esattamente, si potrebbe implementare un semplice algoritmo che faccia virtualmente scorrere una sequenza sull’altra e che valuti ad ogni spostamento tutte le lettere abbinate per stabilire il numero di appaiamenti esatti.

L’applicazione di questo algoritmo comporta che ad ogni avanzamento della sequenza si dovranno confrontare tutte le lettere appaiate tra le due sequenze.

In questo modo potremo facilmente dimostrare che alla fine si dovranno effettuare un numero di confronti pari al prodotto delle lunghezze delle due sequenze che si vogliono allineare. Infatti ogni lettera della prima sequenza dovrà essere confrontata con ogni lettera dell’altra.Nel nostro caso specifico ci sono complessivamente 30 coppie di lettere appaiate, un numero pari al prodotto delle lunghezze delle due sequenze (5 e 6 amminoacidi).

L’efficienza di un algoritmo dipenderà dal tempo impiegato per eseguire le varie operazioni. Questo tempo viene spesso indicato come proporzionale alla lunghezza O(nm) dove n e m sono le lunghezze delle due sequenze che stiamo andando a confrontare.

La necessità di effettuare ricerche di similarità in banche dati di sequenze ha determinato una crescente esigenza di disporre di rapidi algoritmi di allineamento.

Infatti le ricerche di similarità consistono nel ripetere automaticamente la procedura di allineamento di una data sequenza (definita query) con ognuna delle sequenze della banca dati.

In questo modo sarà possibile individuare la sequenza che ha il massimo punteggio di allineamento.

La crescita esponenziale delle banche dati ha portato allo sviluppo di programmi (FASTA e BLAST) che sono in grado di effettuare velocemente delle ricerche di similarità, grazie a soluzioni euristiche che sono basate su assunzioni non certe ma estremamente probabili.

Allineamenti di sequenze con gap

La complessità del problema di allineare sequenze di acidi nucleici e di proteine deriva dal fatto che deve essere considerata la possibilità che il migliore allineamento comporti l’inserimento di gap.

Questa esigenza è necessaria dal momento che nel corso dell’evoluzione si possono avere processi di inserzione o delezione che comportano una diversa lunghezza di sequenze omologhe.

ATGGACCGGATGGATGATGGACCGTTAGGAT

ATGGACCGAATGGCTGACGGACCGTGAGGAT

ATGGAC.TGGCTGACGGACCGTGAGGAT -CGAA

Sostituzioni puntiformi

Delezioni

ATGGAC.TGGCTGACGGAACTCCGTGAGGAT

Inserzioni

AGTCCA.TGGCTGACGGAACTCCGTGAGGAT

Inversioni

Guardate questi due allineamenti:

Sono stati prodotti rispettivamente senza e con la possibilità di inserire gap.

E’ evidente come inserendo un gap in ciascuna delle due sequenze si passa da 10 a 25 appaiamenti esatti.

10

25

DOT MATRIX per individuare e localizzare similarità di sequenza anche in presenza di gap che graficamente appaiono come salti in diagonale

Sequenza 1

Sequenza 2

Quindi l’allineamento che ne viene fuori sarà:

RESPUBLICA

RE-PUBLIC-

Altro esempio:

LAMIAP---RIMASEQ-------CREATA

--MIA-ALTR--ASEQDAALLIN--EARE10 RESIDUI ALLINEATI

Matrici di sostituzione

PAM BLOSUM

Le Matrici di sostituzione sono usate quando è opportuno applicare dei criteri di dimilarità che non si limitano a verificare l’identità assoluta ma tengono conto del fatto che gli amminoacidi possano essere più o meno simili tra loro

MATRICI DI SOSTITUZIONE

Le Matrici di sostituzione sono usate quando è opportuno applicare dei criteri di Similarità che non si limitano a verificare l’identità assoluta ma tengono conto del fatto che gli amminoacidi possano essere più o meno simili tra loro.

Infatti

RICERCA DI SIMILARITA’ E ALLINEAMENTO DI SEQUENZE

BLAST e PSI-BLASThttp://blast.ncbi.nlm.nih.gov/Blast.cgi

FASTAhttp://fasta.bioch.virginia.edu/ oppure http://www.ebi.ac.uk/fasta33/

BCM Search Launcherhttp://searchlauncher.bcm.tmc.edu/multi-align/multi-align.html

Pole Bio-Informatique Lyonnais – NPS@http://npsa-pbil.ibcp.fr/cgi-bin/npsa_automat.pl?page=/NPSA/npsa_server.

Alcune caratteristiche dei tools più usati:

BLAST (Basic Local Alignment Search Tool), sviluppato dal National Center forBiotechnology Information, NCBI):

- allineamento locale- estremamente veloce- parte cercando brevi frammenti della sequenza, che poi prova ad estendere- usa una matrice di sostituzione in entrambe le fasi del processo di allineamento (scansione del database e estensione della subsequenza): più preciso ha quattro opzioni fondamentali:

BLASTP: confronta sequenze proteiche contro un database proteicoBLASTN: confronta sequenze nuclotidiche contro un database nucleotidicoTBLASTN: confronta una sequenza proteica contro un database nucleotidico, traducendo ciascuna sequenza del database nucleotidico nei suoi 6 frames di letturaBLASTX: confronta una sequenza nucleotidica contro un database proteico, dopo averla tradotta nei suoi 6 frames di lettura.

PSI-BLAST (Position Specific Interated BLAST): modificazione di BLAST che combina elementi sia del metodo di allineamento a coppie che multiplo: usa una ricerca iterativa per cui le sequenze trovate ad ogni ciclo sono usate in allineamento multiplo per costruire un modello di punteggio (profilo, vedi più avanti) per il ciclo successivo. Ad ogni ciclo il profilo viene modulato sempre più finemente.Vantaggi:aumentata sensibilitàtrova anche omologhi remoti

PHI-BLAST (Pattern Hit Initiated BLAST): combina PSI-BLAST conla capacità di identificare pattern regolari

I vantaggi di FASTA (FAST-All) (Lipman & Pearson, 1985):1. alta sensibilità per confronti veloci (prima identifica, poi ottimizza)2. allineamento locale3. la fase di estensione produce allineamenti “gapped”4. usa una matrice di sostituzione solo per la fase di estensione della subsequenza

BLAST

1. Suddivide la sequenza in “parole” (3 per le proteine e 11 per gli acidi nucleici

2. Confronta ogni parola con regioni di uguali dimensioni delle sequenze contenute nei database e calcola un valore si score

3. Se lo score è > di un valore soglia T al sotto del quale la similarità è considerata troppo bassa, il programma estende la regione allineata cercando regioni di alta similarità. In questo modo si ottiene un segmento di allineamento locale non ulteriormente estendibile, definito HSP (High-scoring Segment Pair). Il parametro S definisce una soglia di score al di sopra della quale un HSP viene ritenuto degno di attenzione.

I valori di default usati da BLAST sono W=3, T=13, Matrice=BLOSUM 62

FASTA

1. Suddivide le sequenze in parole (2 per proteine, 6 per acidi nucleici)

2. Trova le parole nelle sequenze del database e calcola un indice in base alla posizione in cui ciascuna parola è trovata all’interno della sequenza query.

3. Calcola la similarità delle dieci regioni con maggiori parole identiche per ciascuna sequenza del database (init1)

4. Calcola la similarità delle dieci regioni con maggiori parole identiche includendo le penalizzazione per inserzioni o delezioni (initN)

5. Allinea le N sequenze con il migliore punteggio initN

FASTA: http://www.ebi.ac.uk/fasta33/

Vari database

Sequenza in formato FASTA

Ktup: lunghezza delle parole

Align: numero di allineamenti finali

Open e residue: Penalità per i gap

Differenze tra BLAST e FASTA:

1. Lunghezze delle “parole usate”

2. FASTA si limita ad un’indicizzazione diretta della parola invece BLAST seleziona da ogni parola diverse parole simili (indicate come W-mers).

3. BLAST utilizza una matrice di sostituzione sin dalle prime fasi dell’analisi

4. BLAST è ottimizzato per trovare segmenti di similarità locale privi di gap

FASTA: http://fasta.bioch.virginia.edu/fasta_www2/fasta_www.cgi?rm=select&pgm=fap

Cliccando su Protein-Protein FASTA

In Program ci sono tutte le possibili opzioni

SSEARCH

Esempio pratico

1. Ricercare la sequenza di myoblobin bovine usando SRS

2. Ricercare in BLAST tutte le sequenze simili alla mioglobina bovina

3. Ricercare in BLAST tutte le strutture PDB simili alla mioglobina bovina

Quante sequenze troviamo? Quante strutture PDB?

4. Ripetere la stessa ricerca con FASTA

5. Provare a modificare le matrici di sostituzioni e valutare le differenze.

Allineamento di due sequenze:

BLAST: bl2seq

LALIGN: http://www.ch.embnet.org/software/LALIGN_form.html

EMBOSS: http://www.ebi.ac.uk/emboss/align/

LALIGN:

Dal sito Exspasy:

ALLINEAMENTO MULTIPLO DI SEQUENZE

Informazione biologica maggiore rispetto a quella riportata l’allineamento di due sole sequenze: i residui più importanti dal punto di vista strutturale o funzionale saranno estremamente conservati tra tutte le sequenze dell’allineamento.

“Una sequenza amminoacidica fa la timida; un paio di sequenze omologhe sussurrano; molte sequenze allineate gridano”.

Per essere informativo un allineamento multiplo dovrebbe contenere unadistribuzione di sequenze sia strettamente sia lontanamente correlate:Svantaggi:•tutte strettamente correlate => ridondanza•tutte lontanamente correlate => allineamento inaccurato => inutilità

ALLINEAMENTO MULTIPLO DI SEQUENZE

Parametri importanti per la ricerca di omologhi di proteine note:Sensibilità = riconoscere tutte le correlazioni anche molto lontaneSelettività = minimizzare il numero di sequenze trovate che non siano dei veri omologhi

Da un allineamento riusciamo a dedurre informazioni sui profili:

Un profilo esprime tutta l’informazione contenuta in un multiallineamento: in generale, osservando gli amminoacidi rappresentati, si attribuisce un punteggio a ciascun amminoacido perogni colonna dell’allineamento (con le matrici di sostituzione) osservandone la conservazione. Analogamente, osservando la frequenze dei gap, si attribuisce una penalità per il loro inserimento.

CLUSTAL W: -il tool più comune utilizzato per l’allineamento multiplo di sequenza:- potenziato per allineamenti di sequenze proteiche divergenti favorisce l’apertura di gaps in regioni in cui è potenzialmente presente un loop piuttosto che una struttura secondaria ordinata (in base a una penalità residuo-specifica e a una penalità ridotta in regioni idrofiliche) favorisce l’apertura di gaps nelle stesse posizioni.

HMMer: crea profili utilizzando gli HMM e li usa per la ricerca controuna banca dati proteica

ALLINEAMENTO MULTIPLO DI SEQUENZE

1. http://www.ebi.ac.uk/clustalw/

2. http://hmmer.wustl.edu/