Bioinformatica

ALLINEAMENTO CON ALBERO

Se si ha un insieme n di sequenze molto numeroso, con sequenze abbastanza lunghe, non è possibile

calcolare lo score dell’allineamento multiplo come somma di tutte le combinazioni che possono nascere tra

sequenze che considero. L’obiettivo è sempre quello di attribuire il massimo punteggio

tutte le n

all’allineamento multiplo, quindi massimizzare il punteggio derivante dall’allineamento a coppie.

Come si fa a selezionare le coppie di sequenze da allineare? Si deve realizzare un algoritmo di allineamento

multiplo tra gruppi di sequenze; fondamentalmente si deve stabilire quali sono le sequenze più simili, quindi

quelle che probabilmente avranno uno score di allineamento più alto e si limitano le tecniche di allineamento

solo a queste sequenze più simili.

NB: non vengono fatti tutti gli allineamenti fra le possibili coppie di sequenze perché richiederebbe

tantissimo tempo.

Se si assume di avere n sequenze di lunghezza l; se si mette tutto in tabella si formerà una matrice con l righe

(lunghezze sequenze) x n elementi (numero sequenze). 20

Per esempio, 10 sequenze di lunghezza 100 danno luogo ad una matrice di 10 elementi, che richiederebbero

richiederebbe 3 milioni di anni,

almeno 100 milioni di Terabytes di memoria e l’elaborazione supposto che 1

milione di elementi possano essere analizzati in un secondo.

Si può intuire che quindi occorre un metodo che permette di capire quali sequenze sono più simili e quindi

quali sequenze bisogna considerare per l’allineamento.

Viene utilizzata una rappresentazione ad albero: ha una struttura che parte da una radice, arriva ai rami e infine

termina con le foglie (sequenze).

Se fosse nota l’origine dei profili si potrebbe ricostruire una sequenza in un albero, perché possiedono un

antenato comune da cui discendono. Se le sequenze da allineare vengono rappresentate in questo modo, si può

utilizzare la rappresentazione ad albero per capire quali sono le coppie di sequenze più simili.

Per utilizzare questo metodo bisogna seguire un metodo, ripetuto n volte:

• Bisogna definire una distanza fra sequenze e bisogna ripetere i due passi seguenti fino ad ottenere un

unico cluster:

1. scegli le due sequenze con distanza minima (due sequenze più simili) e fondile in un unico

allineamento (cluster);

2. aggiorna le distanze calcolando la distanza tra il nuovo cluster e i rimanenti.

Inizialmente si crea una matrice di similarità in cui si riportano con dei numeri le differenze che esistono tra le

sequenze coinvolte nell’allineamento→ si scelgono le sequenze con distanza minima (cioè le sequenze più

→ da queste due sequenze se ne crea una sola→ si aggiorna la matrice di sostituzione, calcolando la

simili) che deriva dall’aggregazione. Questo procedimento è

distanza tra le sequenze rimanenti e la nuova sequenza

ripetuto n volte, e si ci ferma quando tutte le sequenze sono aggregate in unico cluster.

Questo procedimento riduce notevolmente il numero di confronti da eseguire poiché permette il confronto solo

tra le sequenze più simili; infatti, da un lato garantisce il raggiungimento di un punteggio di allineamento più

elevato e dall’altro riduce il numero di allineamenti da seguire.

Ad esempio si suppone di avere 4 sequenze con lunghezza molto

ridotta: una sequenza con 5 basi, due sequenze con 4 basi e una

sequenza con 3 basi.

Se non ci fosse l’allineamento con alberi, l’unico strumento a

sarebbe l’inserimento di gap nelle sequenze più

disposizione

corte, con lo scopo di massimizzare il numero di coincidenze,

evitando la formazione di colonne esclusivamente di gap.

Dopodiché si dovrebbe calcolare l’allineamento come somme di

coppie.

utilizzo l’allineamento con alberi, bisogna:

Se 1) costruire una matrice delle distanze tra le sequenze.

Si riportano le sequenze sulla riga e sulla colonna; la diagonale principale è tutta 0 perché rappresenta la

distanza tra le stesse sequenze. La distanza tra sequenze diverse si calcola con il numero di operazioni che

per farla diventare esattamente coincidente con l’altra.

bisogna compiere su una sequenza c’è una sostituzione L-F e l’inserimento

Ad esempio tra NYLS e NFS la distanza è 2 perché di un gap.

Una volta vista la distribuzione delle distanze, si devono scegliere le sequenze con distanza minima, quindi in

questo caso, si dovranno scegliere due sequenze con distanza 1 (perché è il valo re più piccolo, escluso lo 0).

si

Si può scegliere a caso fra le tre aggregazioni con distanza 1→ si sceglie di aggregare NYLS e NKYLS→

allineano inserendo il gap.

Si crea questo cluster costituito dalle due sequenze NYLS e NKYLS.

2) Si ricalcola le distanze tra le sequenze.

Questa volta la matrice è costituita da 3 sequenze, due sono rimaste uguali ma si deve aggiungere il cluster

formato precedentemente.

La diagonale principale è sempre 0.

La distanza fra il cluster (NYLS/NKYLS) e NFS è 2.5

perché nel caso del cluster bisogna fare la media delle

distanze dei singoli elementi contenuti nel cluster:

facendo riferimento alla tabella soprastante,

l’appaiamento NYLS/NFS=2, mentre NKYLS/NFS=3,

quindi si fa la media→ 2+3=5 e 5/2=2.5

Si scelgono le sequenze con distanza minore, ad esempio NFS e NFLS, e si aggregano formando un nuovo

cluster. formazione dell’albero.

3) si mettono insieme le sequenze formando il cluster che porta alla

La strategia per l’allineamento multiplo ottimale (quello con score più alto) prevede di allineare inizialmente

le sequenze più simili, poi verranno allineate le sequenze più distanti, fino a che tutte le sequenze sono allineate.

Si utilizza l’albero con le sequenze per decidere l’ordine degli allineamenti.

Le prime due sequenze si allineano con

l’inserimento di un gap (NKYLS/N_YLS).

Le altre due sequenze vengono allineate con

l’inserimento di un gap (NF_S/NFLS).

Così si procede all’allineamento ottimale,

allineando solo le coppie di sequenze più simili.

Alla fine bisogna allineare l’intero cluster,

quindi se necessario bisogna inserire gap sia per

massimizzare lo score di allineamento sia per

permettere alle sequenze di avere tutte la stessa lunghezza.

Nel cluster finale non vengono riportate le 4 sequenze iniziali, ma vengono riportate le sequenze ottenute dopo

il primo allineamento.

L’obiettivo è quello di ridurre l’allineamento a coppie, limitandolo alle sequenze più simili perché quest’ultime

sono quelle che hanno un punteggio di allineamento maggiore.

In questo albero si procede dall’alto allineando le sequenze contenute nel livello più alto dell’albero, dopodiché

si scende di livello, a mano a mano che tutte le sequenze che fanno parte dello stesso livello sono allineate. In

questo caso si ha un albero a due livelli; prima si allineano le sequenze del primo livello (NYLS, NKYLS,

NFS, NFLS) e poi si allineano quelle del secondo livello (NKYLS, N_YLS, NF_S, NFLS).

CLUSTAL OMEGA

Omega è uno strumento che permette di effettuare l’allineamento tra sequenze.

Clustal

Come algoritmo, Clustal, confronta tutte le coppie di sequenze per ottenere la matrice di similarità; sulla base

costruisce l’albero guida e successivamente effettua l’allineamento progressivo con

della matrice, Clustal

l’ordine determinato dall’albero guida.

ESERCIZIO: ricerca di similarità con la proteina Grb2 e con il messaggero che la codifica in homo sapiens.

Ci sono due strategie: ricerca tramite advances search o ricerca tramite limits. (entrambi si trovano in NCBI)

Nei limits: bisogna selezionare il database Nucleotide e inserire nella barra di ricerca ("Homo

sapiens"[Organism]) AND grb2. Prima di effettuare la ricerca si devono inserire:

• Field: Gene Name

• Source database: RefSeq

• Gene Location: Genomic DNA/RNA

• Molecule: mRNA

• Exclude: STSs, working draft, TPA, patents.

I limits si trovano, una volta effettuata la ricerca, a destra e a sinistra della risposta.

Nell’andavances search:

• si seleziona Gene Name e si inserisce grb2 nella barra adiacente;

• Si selezione Organism e si inserisce homo sapiens nella barra adiacente.

Si può utilizzare l’una o l’altra strategia, l’importante è ottenere un risultato. Una volta effettuata la

ricerca su nucleotide, si

ottengono i risultati.

La ricerca ha

determinato due risultati

RefSeq.

Bisogna cliccare su Ref Seq transcripta e si ottiene la variante 1 e la variante 2. in un esercizio entrambe le

scelte risultano coincidenti,

entrambe infatti sono

sequenze RefSeq (non

prodotte da proiezioni); c’è

la variante 1 che risulta più

antica e la variante 2 più

recente. Viene scelta la

variante 2 perché è più

recente.

Se l’esercizio è generico, e non dà indicazioni su quale

NB: variante usare, si ha la possibilità di scegliere

una variante qualsiasi, MA si deve motivare la sempre la scelta.

Una volta scelta la variante si copia il formato FASTA e si incolla su BLASTn nella sezione evidenziata in

figura. BLAST cerca tra le sequenze

presenti nel database quella

più simile alla sequenza data.

La sequenza oltre ad essere

inserita su BLAST come

formato FASTA, può essere

salvata come file e caricata

su BLAST.

Come database seleziono

quello standard; mentre non

indico nulla in organism.

all’interno di un sottoinsieme

Si aggiunge qualcosa in organism quando si vuole forzare BLAST a cercare

dei database.

In Algorithm parameters è possibile visualizzare una serie di parametri di default:

-Max target sequences: si seleziona 100; questo valore rappresenta il numero massimo di sequenze simili che

verranno riportate nella risposta.

-Expect threshold: si seleziona 0.05; questo valore è inteso come la significatività statistica

-Word size: si seleziona 28; questo valore è stato calcolato in maniera euristica (per le proteine si

considerano 6 lettere)

è possibile inserire l’organism specifico (in questo caso Homo sapiens).

-Filter:

Dopo aver controllato tutti i parametri, si può premere BLAST e si aspetta la risposta.

La ricerca è articolata in diverse parti tra cui le informazioni sulla sequenza nucleotidica e il riassunto grafico

degli allineamenti.

Nella descriptions si trovano tutte le 100 sequenze ordinate e caratterizzate da:

• Max score e total score,

• expectation value (E value),

• query cover (%),

• identità (%),

• accession number (molto spesso di NCBI)