Bioinformatica
Allineamento di sequenze e ricerca di similarità
Dr. Giuseppe Pigola – [email protected]
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.
2
Bioinformatica
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
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK
||. | | | .|
.| || || | ||
TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
Locale
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK
||||||||.||||
TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
3
Bioinformatica
Allineamento Pairwise –
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.
4
Bioinformatica
Allineamento Pairwise –
Matrici Dot Plot
margaretqaklerdayhqff
m*
a *
*
*
*
r
Duplicazione
*
*
g
a * **
*
*
r
Inversione
*
*
e
*
*
t
*
d
*
a * *
*
y
**
h
Similarità
q
*
f
*
f
*
*
5
Bioinformatica
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 , ai 1 ,..., aw ) (b j , b j 1 ,..., bw )
risultino identiche per s residui su w.
6
Bioinformatica
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet
7

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
Bioinformatica
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 punteggio, mentre
una piccola 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 proporzionale al punteggio
che contengono.
Num di score con
quel punteggio
Punteggio ottenuto
8
Bioinformatica
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet
9

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;
Bioinformatica
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet

10
Spostando i cursori in modo da
posizionarci sulla piccola
distribuzione a destra a
punteggio elevato verranno
visualizzati solo i punteggi
elevati che ovviamente
corrispondono alla diagonale
principale;
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
CMDHFTHYSCDCQAGFHGTNCTDNIDDCQNHMCQNGGTCVDGINDYQCRCPDDYTGKYCEGHNMISMMYPQTSPCQNHE
C KHGVCFQPNAQGSDYLCRCHPGYTGKWCEYLTSISFVHNNSFVELEPLRTRPEANVTIVFSSAEQNGILMYDGQDAHLAV
ELFNGRIRVSYDVGNHPVSTMYSFEMVADGKYHAVELLAIKKNFTLRVDRGLARSIINEGSNDYLKLTTPMFLGGLPVDP
AQQAYKNWQIRNLTSFKGCMKEVWINHKLVDFGNAQRQQKITPGCALLEGEQQEEEDDEQDFMDETPHIKEEPVDPCLEN
KCRRGSRCVPNSNARDGYQCKCKHGQRGRYCDQGEGSTEPPTVTAASTCRKEQVREYYTENDCRSRQPLKYAKCVGGCG
N QCCAAKIVRRRKVRMVCSNNRKYIKNLDIVRKCGCTKKCY
11
Bioinformatica
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet
ESERCIZIO
Recuperare le sequenze proteiche in formato FASTA di:

subunità alfa 2 di Rattus norvegicus del recettore neuronale dell’acetilcolina
(Neuronal acetylcholine receptor protein, alpha-2 chain precursor P12389);

subunità alfa 4 di chicken del recettore neuronale dell’acetilcolina (Neuronal
acetylcholine receptor protein, alpha-4 chain precursor P09482);

Confrontare le due sequenze con DotLet per verificare la presenza di zone di somiglianza ed
eventuali dissimilarità nella diagonale principale(Far variare i parametri di input);
12
Bioinformatica
Allineamento Pairwise
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
 |S’|=|T’|
 Rimuovendo gli spazi da S’ e T’ otteniamo S e T.
Se l = |S’|=|T’|, lo score di un allineamento pairwise è definito da:
l
  S '[i], T '[i]
i 1
L’allineamento ottimale sarà quello che massimizza la similarità (lo score);
13
Bioinformatica
Allineamento Pairwise
ESEMPIO: NEEDLEMAN-WUNSCH
Lo score ottimale V(i,j) di due sequenze S1….i T1…j ha le seguenti proprietà:

i
V (i,0)    ( S k ,)
k 0
j
V (0, j )    (, Tk )
k 0
V (i  1, j  1)   ( Si , T j ) match/mismatch

V (i, j )  max  V (i  1, j )   ( Si ,) deletion
 V (i, j  1)   (, T )
insertion
j

Algoritmo di programmazione dinamica per calcolare l’allineamento
14
Bioinformatica
Allineamento Pairwise

ESEMPIO: NEEDLEMAN-WUNSCH
j -
i
-
1
2
3
4
5
C
A
D
B
D
S2
0
-1
-2
-3
-4
-5
1
A
-1
-1
1
0
-1
-2
2
C
-2
1
0
0
-1
-2
3
B
-3
0
0
-1
2
1
4
C
-4
-1
-1
-1
1
1
5
D
-5
-2
-2
1
0
3
6
B
-6
-3
-3
0
3
2
S1
Allineamento ottimale V(6,5) = 2
15
V (i  1, j  1)   ( Si , T j )

V (i, j )  max  V (i  1, j )   ( Si ,)
 V (i, j  1)   (, T )
j

S1 = ACBCDB
S2 = CADBD
ab
2
 ( a, b)  
 1 otherwise
Otteniamo tre allineamenti ottimali:
ACBCDB| ||
-C-ADBD
ACBCDB| ||
-CA-DBD
-ACBCDB
| | |
CADB-DBioinformatica
Allineamento Pairwise –
Matrici di Score

Un modo per definire la funzione σ è ad esempio quello di assegnare 1
in caso di caratteri uguali e 0 altrimenti.

Nel caso di Nucleotidi questa definizione può andare bene;

Nel caso di aminoacidi non è del tutto corretto assegnare ai
mismatch lo stesso peso;

Per questo motivo si introducono le matrici di score che assegnano
ad ogni coppia di amino acidi un punteggio:

Matrici PAM (Percent Accepted Mutations): si basano su calcoli statistici;

Matrici BLOSUM: sono invece basate su una banca dati (BLOCKS) di
allineamenti multipli di segmenti proteici;
16
Bioinformatica
Allineamento Pairwise –
Matrici di Score
Score allineamento: 15
Seq1
Seq2
Score
V
V
4
D
E
2
S - C
S L C
4 -11 9
Y
Y
7
Penalità del gap.
blosum62
17
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/
18
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/
Utilizziamo EMBOSS per
allineare due sequenze
con gli algoritmi di
 Needleman-Wunsch
(globale);
 Smith-Waterman
(locale);
19
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/
Selezioniamo il tipo di
sequenza:
 Protein;
 DNA;
20
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/
Scelta della scoring matrix:


Protein:
 Blosum62;
 Blosum50;
 Blosum40;
DNA:
 DNAFull:
(Assegna
score diversi nel caso di
mismatch di caratteri
IUB-IUPAC);

21
DNAMat:
(usata da
BLAST assegna uno
score al match e un altro
al mismatch);
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/

GOP e GEP;
22
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/
Inserimento
delle
due
sequenza anche da file;
23
Bioinformatica
Allineamento Pairwise - EMBOSS
http://www.ebi.ac.uk/Tools/emboss/align/
Identity: percentuale di match identici;
Similarity: percentuale di match per cui la matrice di scoring ha un valore >=
0 (si tratta di aminoacidi diversi che hanno caratteristiche chimico-fisiche simili);
24
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
BLAST
Basic Local Alignment Search Tool
25
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
BLAST (Basic Local Alignment Search Tool)
Permette di ricercare regioni di
similarità locale tra una
sequenza data e una collezione
di sequenze in banca dati.
26
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
L’idea di base dell’algoritmo consiste nel procedere ad allineare passo
dopo passo piccole sequenze (WORD e KTUPLE) e tentando di
estendere poi l’allineamento.
27
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
BLAST NUCLEOTIDICO
MEGABLAST
E’ utilizzato per trovare efficientemente lunghi allineamenti tra sequenze
molto simili tra loro o per identificare una sequenza di input sconosciuta.
Discontiguous MEGABLAST
E’ utilizzato per trovare efficientemente lunghi allineamenti tra sequenze che
hanno alcune differenze tra loro.
BLASTN
Utilizzato in tutti gli altri casi.
28
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
BLAST PROTEICO
BLASTP
E’ utilizzato per identificare una sequenza proteica di input nel DB o per
ricercare sequenze proteiche simili;
PSI-BLAST
Position-Specific Iterata BLAST è il programma BLAST più sensibile, il che lo
rende molto utile per trovare proteine poco correlate (molto distanti).
PHI-BLAST
Pattern-Hit Initiated BLAST è progettato per la ricerca di proteine che
contengono un pattern specificato dall'utente e sono simili alla sequenza
query in prossimità del pattern.
29
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
BLASTX (Translated query vs protein database)
ALTRI TOOL
E’ utilizzato per trovare proteine simili a quelle codificate da
una query di nucleotidi;
TBLASTN (Protein query vs translated database)
E’ utilizzato per trovare proteine omologhe a quella data in
input. Le sequenze nucleotidiche del DB vengono tradotte in
sequenze aminoacidiche utilizzando tutti e sei i frame di
lettura e poi contfrontate con la query.
TBLASTX (Translated query vs translated
database)
Prende in input una sequenza nucleotidica, la traduce in tutti
e sei i frame di lettura e confronta queste sequenze tradotte
con il DB di nucleotidi a sua volta tradotto in Aminoacidi.
Utile per trovare nuovi geni.
BLAST2SEQ
Utilizza BLAST per allineare due o più sequenze.
30
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Scelta dei vari BLAST
Inserire la sequenza in
formato FASTA (anche da
file) oppure specificare
l’Accession Number o il
Gene ID.
Specificare eventualmente
l’intervallo di interesse.
31
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Scegliere un nome
descrittivo per la ricerca
che apparirà nei risultati.
Selezionare se si vuole
utilizzare BLAST per
allineare due o più
sequenze.
Campo di ricerca: DB,
Organismo.
E’ possibile usare la sintassi
di entrez per filtrare i DB
selezionati.
32
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Ottimizza la ricerca per:



33
Similarità;
Dissimilarità;
Ricerca generica;
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
E’ possibile cambiare la
soglia di significatività
statistica. Ogni match
trovato ha un valore di
significatività statistica, che
indica quanto è
statisticamente probabile
che quel match sia casuale.
Minore è il numero,
maggiore sarà il tempo di
esecuzione.L’accuratezza
però cresce.
Filtrare regioni il cui match
avrebbe scarso significato
biologico.
34
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Dimensione delle Word:
Maggiore è il numero, minore
sarà il numero di word
generate per cui minore sarà
il tempo di esecuzione.
L’accuratezza però decresce.
35
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Esempio ricerchiamo il gene DIABLO in Drosophila Melanogaster
La prima voce che troviamo è il gene cercato. Selezioniamo la sequenza
corrispondente di mRNA in formato FASTA e diamola in pasto a BLAST
scegliendo come DB nt e tool Megablast.
36
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Dati generali
Taxonomy
Report ci da
informazioni
sulle specie
coinvolte nei
risultati;
Può essere utile
per verificare la
presenza di
sequenze
ortologhi in altre
specie;
37
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Dati generali
Allineamento
grafico:
I colori indicano la
qualità
dell’allineamento.
Le prime due
sequenze sono
identiche.
38
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Le prime due sequenze sono identiche alla query (per questo motivo BLAST
può essere usato per ricercare sequenze sconosciute).
Le altre sono sequenze parziali.
39
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Scorrendo i risultati troviamo altre sequenze (anche parziali) in altri tipi di
Drosophile.
40
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Infine troviamo i dettagli dei vari allineamenti.
I trattini indicano un match, la loro assenza indica un mismatch.
41
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
MAX SCORE
Punteggio dell’allineamento locale più significativo.
(punteggio alto → elevata similarità);
TOTAL SCORE
La somma dei punteggi di tutti gli allineamenti locali
trovati tra la sequenza query e le sequenze del database.
QUERY COVERAGE
Percentuale della sequenza allineata
E-VALUE
Esprime la probabilità che l’allineamento trovato sia casuale. Più
basso è, maggiore è la probabilità che NON sia casuale.
(dipende, oltre che dalla similarità, anche dalla numerosità delle
sequenze in database e dalla lunghezza delle sequenze).
MAX INDENT
Percentuale di identità dell’allineamento locale più significativo.
42
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
VALIDAZIONE STATISTICA e BIT SCORE
La probabilità di trovare un allineamento con score maggiore o uguale di S segue la distribuzione
di Poisson
 S
P  1 e
 Kmne
M,N: lunghezze delle due sequenze;
λ,K: parametri che dipendono tra le altre cose dalla banca dati, dalla sua dimensione etc.
Il numero atteso di sequenze che hanno per caso lo score S è
Kmne
 S
Il bit-score non è altro che lo score normalizzato in modo da poter confrontare bit-score di
banche dati diverse
S'
43
S  log( K )
ln 2
Bioinformatica
Allineamento Pairwise – BLAST2SEQ
http://www.ncbi.nlm.nih.gov/BLAST
E’ possibile usare BLAST per fare
un allineamento di due sequenze.
In questo caso verranno
evidenziate le similarità locali.
Si sceglie il programma adatto, si
inseriscono le sequenze e si
ottiene il risultato.
I parametri dell’interfaccia
cambiano leggermente quanto si
sceglie di allineare proteine
piuttosto che nucleotidi (ad
esempio le matrici di score).
44
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Ritorniamo alla pagina principale di BLAST
C’è una sezione dedicata
ai genomi completi
(o in fase di completamento);
In questo modo è possibile fare
un BLAST su sequenze di una
data specie;
45
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
Ritorniamo alla pagina principale di BLAST
C’è una sezione dedicata
ai genomi completi
(o in fase di completamento);
In questo modo è possibile fare
un BLAST su sequenze di una
data specie;
46
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
ESERCIZIO
Data la seguente sequenza sconosciuta.
Determinare l’identità più probabile.
>SCONOSCIUTA
ATCACTGTAGTAGTAGCTGGAAAGAGAAATCTGTGACTCCAATTAGCCAG
TTCCTGCAGACCTTGTGAGGACTAGAGGAAGAATGCTCCTGGCTGTTTTG
TACTGCCTGCTGTGGAGTTTCCAGACCTCCGCTGGCCATTTCCCTAGAGC
CTGTGTCTCCTCTAAGAACCTGATGGAGAAGGAATGCTGTCCACCGTGGA
GCGGGGACAGGAGTCCCTGTGGCCAGCTTTCAGGCAGAGGTTCCTGTCAG
AATATCCTTCTGTCCAATGCACCACTTGGGCCTCAATTTCCCTTCACAGG
GGTGGATGACCGGGAGTCGTGGCCTTCCGTCTTTTATAATAGGACCTGCC
AGTGCTCTGGCAACTTCATGGGATTCAACTGTGGAAACTGCAAGTTTGGC
TTTTGGGGACCAAACTGCACAGAGAGACGACTCTTGGTGAGAAGAAACAT
CTTCGATTTGAGTGCCCCAGAGAAGGACAAATTTTTTGCCTACCTCACTT
TAGCAAAGCATACCATCAGCTCAGACTATGTCATCCCCATAGGGACCATT
GGCCAAATGAAAAATGGATCAACACCCATGTTTAACGACATCAATATTTA
TGACCTCTTTGTCTGGATGCATTATTATGTGTCAATGGATGCACTGCTTG
GGGGATCTGAAATCTGGAGAGACATTGATTTTGCCCATGAAGCACCAGCT
TTTCTGCCTTGGCATAGACTCTTCTTGTTGCGGTGGGAACAAGAAATCCA
GAAGCTGACAGGAGATGAAAACTTCACTATTCCATATTGGGACTGGCGGG
ATGCAGAAAAGTGTGACATTTGCACAGATGAGTA
47
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
ESERCIZIO I
Ricercare le sequenze proteiche simili alla subunità IV della citocromo c ossidasi umana
(Accession Number: P13073).
Ci sono sequenze predette?
Ci sono sequenze appartenenti a organismi non facenti parte dei mammiferi?
48
Bioinformatica
Similarità nei DB - BLAST
http://www.ncbi.nlm.nih.gov/BLAST
ESERCIZIO II
Considerare la seguente sequenza proteica del lievito:
>gi|2498220|sp|Q06703.1|CDA2_YEAST Chitin deacetylase 2 precursor
MRIQLNTIDLQCIIALSCLGQFVHAEANREDLKQIDFQFPVLERAATKTPFPDW
LSAFTGLKEWPGLDPP YIPLDFIDFSQIPDYKEYDQNHCDSVPRDSCSFDCHH
CTEHDDVYTCSKLSQTFDDGPSASTTKLLDRLK HNSTFFNLGVNIVQHPDIYQ
RMQKEGHLIGSHTWSHVYLPNVSNEKIIAQIEWSIWAMNATGNHTPKWFRPPY
GGIDNRVRAITRQFGLQAVLWDHDTFDWSLLLNDSVITEQEILQNVINWNKSGT
GLILEHDSTEKTV DLAIKINKLIGDDQSTVSHCVGGIDYIKEFLS
Fare una ricerca di omologia nei soli funghi.
Riportare accession number e E-value della proteina più simile di Neuorspora Crassa.
Riportare accession number e E-value ddella proteina più simile di Aspergillus Nidulans.
49
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
FASTA
Sequence Similarity Search using the FASTA
50
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1- Scelta del DB
51
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1I - Inserimento della sequenza
52
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1II - Scelta del programma:
FASTA Simile a BLAST
SSEARCH (Smith-Waterman);
GGSEARCH (Needleman-Wunsch);
TFASTX, TFASTY Confronta una proteina con un
DB di DNA calcolando tutti i frame di lettura;
FASTX, FASTY Confronta una sequenza
nucleotidica con un DB di proteina traducendo la
sequenza di input;
53
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1V - Opzioni:
Match/mismatch scores;
GOP e GEP;
54
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1V - Opzioni:
KTUP: E’ alla base dell’algoritmo FASTA.
Più basso è il valore più accurata e la ricerca (ma
più lento sarà il programma); Esso rappresenta il
minimo numero di residui contigui identici
affinchè una coppia di sequenze sia considerata
simile (… e quindi presa in considerazione);
Expectation Upper value: Rappresenta il
numero MAX di volte che il match è atteso per
caso.
Expectation Lower Value: Rappresenta il
numero MIN di volte che il match è atteso per
caso.
55
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1V - Opzioni:
Strand: Per le sequenze
nucleotidiche specifica quale strand
usare per la ricerca (NONE,BOTH,
TOP,BOTTOM);
Histogram: Visualizza o meno
l’istogramma nei risultati.
L’istogramma da un vista qualitativa
dei risultati.
Filter: Filtrare regioni il cui match
avrebbe scarso significato biologico.
56
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
STEP 1V - Opzioni:
Opzioni di visualizzazione dei
risutati.
57
Bioinformatica
Similarità nei DB - FASTA
http://www.ebi.ac.uk/Tools/sss/fasta/
Eseguiamo FASTA sulla proteina DIABLO di Drosophila Melanogaster
58
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
CLUSTALW
Multiple sequence alignment program for DNA or proteins
59
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/

ALGORITMO PROGRESSIVO:

Si ottengono prima tutti i possibili allineamenti di coppia e si registra il punteggio di
ciascuno (Si mantiene una matrice di tutte le distanze);

Con questi punteggi si costruisce un albero filogenetico in modo da visualizzare le
relazioni evolutive (neighbour joining);

Ad ogni passo si allineerà la coppia (seq-seq o seq-profilo o profilo-profilo) con distanza
minima;

La radice dell’albero conterrà l’allineamento multiplo;
AGTTGG
ACTTGG
AGTTGG
ACTTGG
AG__GG
CCTTGG
AGTTGG
60
AG__GG
CCTTGG
AGTTGG
CCTTGG
AGTTGG
AGTTGG
ACTTGG
AGGG
CCTTGG
AGTTGC
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/

PROFILI:

Dato un allineamento multiplo M di N sequenze di lunghezza L , un profilo P è una
matrice | ∑{-}|  L le cui colonne denotano le freaquenze di ogni simbolo nella
corrispondente colonna dell’allineamento;
A-GTT—TA
AC-TTA-ACGTAAG-C-TA---
61
1
2
3
4
5
6
7
8
A
¾
0
0
0
½ ½
0
¼
T
0
0
0
1
½
0
¼
0
G
0
0
½
0
0
0
¼
0
C
0
¾
0
0
0
0
0
0
-
¼ ¼ ½
0
0
½ ½ ¾
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/

ALLINEARE UNA SEQUENZA CON UN PROFILO:

Sia P =(pij) per i=1… |∑|+1 e j=1… L un profilo, e sia S=s1…sn una sequenza.
Possiamo definire la seguente funzione di score:
σsp: (∑ {-}) {1,2,…,L}  R
 sp (b, i)   pai (a, b)
a
62
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/


ALLINEARE DUE PROFILI:
Siano P1 =(pij) e P2 =(pik) per i=1… |∑|+1, j=1… L’ k=1…L’’, due profili.
Possiamo definire la funzione di score:
σpp: {1,2,…,L’}{1,2,…,L’’}  R
 pp (i, j ) 

 p
a {} b {}
p  ( a, b)
ai bj
Rimpiazzando la funzione di score σ con σpp l’allineamento di due allineamenti
multipli si riduce al confronto di due profili;
63
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
ESEMPIO PRATICO:


Vogliamo allineare le sequenze aminoacidiche della proteina NAD6 dei metazoi ma non dei
mammiferi;

Utilizziamo SRS;

Selezioniamo
“Library Page”;

Scegliamo il DB
“Uniprotkb-SwissProt”;

Clicchiamo su
“Standard Query Form”;
64
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
Impostiamo la Query
65
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
Salviamo i risultati in un
file di testo nel
formato “fasta2seqs”;
66
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
Sul sito di ClustalW
facciamo un upload delle
sequenze e lanciamo il tool
67
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
Risultato dell’allineamento: Formato testuale e colori.
68
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
Sommario:Tabella delle distanze
69
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
JALVIEW: Permette di visualizzare/editare l’allineamento (modificando /
cancellando / inserendo amino acidi)
Colori: Ad ogni aminoacido (o
simili) è assegnato un colore;
Conservation: misura il numero
di proprietà fisico-chimiche
conservate per ogni colonna
dell'allineamento.
Quality: Qualità dell’allineamento
in base alla matrice di score
utilizzata.
Consensus: Aminoacido più
conservato in ogni posizione
(compreso il simbolo di gap). Se ci
sono più consensi viene indicato il
simbolo +;
70
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
Albero filogenetico ricavato dall’allineamento progressivo (i rami hanno
lunghezza proporzionale alla distanza tra le sequenze) .
71
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
OPZIONI.
Si seleziona il tipo di sequenza;
Si incollano le sequenze o si fa
un upload di un file;
72
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
OPZIONI.
Pairwise Alignment Type:
Slow (lento ma accurato);
Fast (veloce ma approssimato);
73
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
OPZIONI.
SLOW OPTIONS
Matrici di score;
GOP;
GEP;
74
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
OPZIONI.
FAST OPTIONS
KTUP: Più basso è il valore più accurata e la ricerca (ma più lento sarà il programma); Esso
rappresenta il minimo numero di residui contigui identici affinchè una coppia di sequenze sia
considerata simile;
WINDOW LENGTH: Dimensione della finestra in cui vengono ricercati i residui contigui.
Decrementare per velocizzare la ricerca; Incrementare per aumentare l’accuratezza.
SCORE TYPE: Percentuale o valore assoluto;
TOPDIAG: Decrementare per velocizzare; Incrementare per aumentare l’accuratezza.
PAIRGAP: Gap penalty;
75
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/
OPZIONI.
Multiple Alignment Type:
Matrici di score;
GOP e GEP;
GAP Distances: Penalità assegnata a gap
troppo vicini;
NO ENDS GAPS: Riferito alla voce
precedente per i gap alla fine delle sequenze;
Iteration: Migliora la qualità dell’allineamento
(NO, Ad ogni step, solo all’ultimo
allineamento).
CLUSTERING: Tipo di clustering:
Neighbour Joining etc.;
Output Format;
76
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/

ESERCIZIO I:

Identificare le sequenze corrispondenti della proteina (avente 214aa) umana shp-2
in topo, ratto e drosophila con E-value migliore.

Costruirne l'allineamento multiplo;

Quale è la parte più conservata?

Visualizzare l’albero filogenetico e trarne le dovute considerazioni.
77
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/

ESERCIZIO II:

Utilizzando Entrez o SRS, estrai le sequenze in formato Fasta delle proteine aventi i
seguenti accession number: P96551, P47700, P48525, O33120 e O25360 e prendi
nota degli organismi a cui appartengono;

Conservare le sequenze fasta in un file;

Lanciare ClustalW;

A quale organismo appartiene la sequenza più lunga e di quanti aminoacidi è
composta?

Quali sono gli AC della coppia con score più alto?
78
Bioinformatica
Allineamento Multiplo - Clustalw
http://www.ebi.ac.uk/Tools/msa/clustalw2/

ESERCIZIO III:

Recuperare le sequenze proteiche in formato fasta YP_521353.1, YP_864391.1,
YP_286398.1, NP_249218.1, YP_316351.1, YP_284886.1, ZP_00942609.1

Lanciare ClustalW;

Visualizzare e commentare l’albero filogenetico.
79
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
80
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
T-Coffee (Tree-based Consistency Objective Function for alignment Evaluation)
Dato un insieme di sequenze un allineamento è ottimale se esso è il più possibile
consistente con tutti i possibili allineamenti pairwise ottimali;

STEP 1: Viene generata una “Primary Library” contenente un insieme di
allineamenti pair-wise tra tutte le sequenze di input.
 Allineamenti globali: tra tutte le coppie di sequenze (ClustalW);
 Allineamenti locali: I primi 10 migliori allineamenti locali per ogni coppia di
sequenze (lalign);
81

Ogni coppia di residui ha inizialmente un peso pari a quello dato dalla identità
percentuale;

Le due librerie vengono combinate in una sola con un semplice processo
additivo: se una coppia di residui è presente in entrambe, viene fusa in una sola
entry il cui peso è dato dalla somma dei pesi;
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
Libreria primaria di allineamenti pairwise globali

Tutte le coppie di sequenze in input vengono allineate mediante ClustalW.

Per ogni allineamento pairwise viene calcolata l’identità percentuale:
sim ( S1 , S 2 )  100
I % ( S1 , S 2 ) 
pos

Dove sim(S1,S2) è il numero dei match nell’allineamento e pos il numero delle
coppie allineate di residui escluse quelle in cui compare un gap.
S1) A C A - G – T C A
S2) A G - T G C T – T
3  100
I % ( S1 , S 2 ) 
 60
5
82
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/

Nella libreria ogni allineamento pairwise è rappresentato come una lista di coppie
di residui pesati (constraint list);

Inizialmente ogni coppia di residui riceve un peso equivalente alla sequence
identity dell’allineamento da cui proviene:
S1) A C A - G – T C A
S2) A G - T G C T – T
Seq1
S1
S1
S1
S1
S1
83
Seq2
S2
S2
S2
S2
S2
Res1
1
2
4
5
7
Res2
1
2
4
6
7
Weight
60
60
60
60
60
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
•
Viene creata una seconda libreria a partire dagli allineamenti locali creati con LAlign, un tool
del pacchetto FASTA;
•
L’allineamento locale di una coppia di sequenze S1, S2 consiste nell’allineamento di
sottosequenze di S1 ed S2, al fine di mettere in evidenza eventuali regioni ad alta similarità:
S1
S2
•
LAlign restituisce i 10 migliori allineamenti locali (in termini di similarità) della coppia di
sequenze in input;
•
Una volta individuato l’allineamento locale con il massimo score, LAlign cerca il successivo
escludendo dalla ricerca le due regioni appena trovate: in questo modo gli allineamenti
prodotti non si intersecheranno.
84
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/

A partire dalle due librerie globale e locale viene creata un’unica libreria primaria mediante una semplice
operazione di addizione;

Le coppie di residui comuni vengono sostituite da un’unica entry il cui peso è la somma dei due pesi,
mentre tutte le altre coppie vengono trascritte così come sono:
Global Alignments by ClustalW
Seq2
Res1
Res2
S2
1
1
S2
2
2
S2
3
3
S2
5
6
S2
7
7
Seq1
S1
S1
S1
S1
S1
Seq1
S1
S1
S1
S1
S1
S1
S1
85
Seq2
S2
S2
S2
S2
S2
S2
S2
Weight
60
60
60
60
60
Seq1
S1
S1
S1
S1
S1
Primary Library
Res1
Res2
1
1
2
2
3
3
5
6
7
7
15
22
16
23
Local Alignments by LAlign
Seq2
Res1
Res2
S2
1
1
S2
2
2
S2
3
3
S2
15
22
S2
16
23
Weight
30
30
30
10
10
Weight
90
90
90
60
60
10
10
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/

STEP II: Calcolo dei pesi nella “Extended Library”. Ad ogni coppia di residui
allineati nella libreria viene assegnato un peso in base agli altri allineamenti
pairwise;


Date due sequenze S1 e S2. Allineamo prima S1 e poi S2 con le rimanenti;
Fatto l’allineamento tra S1 e Zi e S2 e Zi:

se i residui x di S1 e y di S2 sono allineati con lo stesso residuo z di Zi allora il peso della coppia di
residui w(x,y) viene incrementato ponendolo uguale a:
w(x,y) + min(w(x,z),w(z,y))


Altrimenti nella libreria vengono inserite altre due coppie (x,z) e (z,y) con i relativi pesi;
STEP III: Esegue l’allineamento progressivo utilizzando la libreria al posto
delle matrici di score;
86
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
Quattro sequenze e il relativo allineamento progressivo con ClustalW
SeqA GARFIELD THE LAST FAT CAT
SeqB GARFIELD THE FAST CAT
SeqC GARFIELD THE VERY FAST CAT
SeqD THE FAT CAT
SeqA GARFIELD THE LAST FA-T
SeqB GARFIELD THE FAST CA-T
SeqC GARFIELD THE VERY FAST
SeqD
THE
FA-T
from Notredam et al. 2000
87
CAT
--CAT
CAT
SeqA GARFIELD THE LAST FA-T
SeqB GARFIELD THE ---- FAST
SeqC GARFIELD THE VERY FAST
SeqD
THE
FA-T
CAT
CAT
CAT
CAT
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
SeqA GARFIELD THE LAST FAT CAT
SeqB GARFIELD THE FAST CAT ---
SeqB GARFIELD THE ---- FAST CAT
SeqC GARFIELD THE VERY FAST CAT
SeqA GARFIELD THE LAST FA-T CAT
SeqC GARFIELD THE VERY FAST CAT
SeqB GARFIELD THE FAST CAT
SeqD -------- THE FA-T CAT
SeqA GARFIELD THE LAST FAT CAT
SeqD -------- THE ---- FAT CAT
SeqC GARFIELD THE VERY FAST CAT
SeqD -------- THE ---- FA-T CAT
STEP I: Library of
pairwise
alignments
STEP II: Per ogni coppia di sequenze controlla l’allineamento di ogni coppia di residui
usando gli altri allineamenti;
Consistency
Extended library
SeqA GARFIELD THE LAST FAT CAT
|||||||| ||| |||| |||
SeqB GARFIELD THE FAST CAT ---
SeqA GARFIELD THE LAST FAT
SeqA GARFIELD
||||||||
SeqC GARFIELD
||||||||
SeqB GARFIELD
SeqB GARFIELD THE
THE
|||
THE
|||
THE
LAST
||||
VERY
||||
FAT CAT
|| \ \\\
FAST CAT
|||| |||
FAST CAT
SeqA GARFIELD THE LAST FAT CAT
|||
||| |||
SeqD
THE
FAT CAT
|||
||\ \\\
SeqB GARFIELD THE
FAST CAT
88
CAT
I pesi sono utilizzati
nell’allineamento finale
progressivo al posto delle
matrici di score
FAST CAT
Per esempio la coppia A(G),B(G) avrà un peso dato da:
w(A(G),B(G)) + min(w(A(G),C(G)) w(C(G),B(G)))
Programmazione dinamica
SeqA GARFIELD THE LAST FA-T CAT
SeqB GARFIELD THE ---- FAST CAT
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/
L’algoritmo:
(1) Calcolo degli allineamenti pairwise con
ClustalW;
ClustalW global
Pairwise alignments
LAlign local pairwise
alignments
Weighting
(2)
(3)
Calcolo degli allineamenti locali con LAlign (10
migliori allineamenti per ogni coppia di
sequenza)
Calcolo della primary library con i relativi
pesi;
Primary library
Extension
Extended library
(4)
Estensione della libreria con il calcolo dei pesi
in base a tutti gli allineamenti pariwise;
Progressive alignment
(5)
89
Allineamento progressivo usando i pesi per
ogni coppia di residui al posto delle matrici di
score;
A
B
C
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/

90
Tool Online sul sito di
EMBL
Bioinformatica
Allineamento Multiplo – TCoffee
http://www.ebi.ac.uk/Tools/msa/tcoffee/

91
Esempio di Output del tutto
simile a quello di ClustalW;
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/
92
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Antipole Clustering Algorithm sostituisce l’albero guida di ClustalW per la
costruzione dell’allineamento multiplo;

Permette di velocizzare il processo di allineamento con risultati paragonabili o
migliori a quelli ottenuti con ClustalW;

Il metodo di allineamento può essere riassunto in:
93

Costruire l’albero di clustering (rappresenta l’albero filogenetico);

Allinea progressivamente le sequenze partendo dalle foglie fino alla radice che conterrà
l’allineamento finale;
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

CLUSTERING:
 Presupposto: Sequenze lontane saranno sicuramente in cluster diversi.



94
1-Mediana approssimata per il calcolo del diametro;
Splittare il dataset in due cluster;
Applicare ricorsivamente il metodo fin quando la dimensione dei cluster supera
un certo parametro σ;
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

1-Mediana
 Sia S un database di oggetti in uno spazio metrico, dato il numero intero k, il
problema della k-mediana per S consiste nel trovare k oggetti c1, c2, …, ck in S
che minimizzano:
w ( c1 , c 2 ,..., c k )   min d ( s , c i )
s S

i 1,..., k
Per k = 1 il problema è chiamato 1-mediana e consiste nel ricercare un
elemento tale che la seguente funzione è minimizzata:
w (c )   d ( s, c )
s S
95
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

96
1-Mediana approssimata
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

97
1-Mediana approssimata
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

98
1-Mediana approssimata
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

99
1-Mediana approssimata
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

1-Mediana approssimata
100
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

1-Mediana approssimata
101
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

1-Mediana approssimata
102
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

1-Mediana approssimata
103
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

1-Mediana approssimata
The final winner
104
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Pseudo Diametro:

105
Se ad ogni step eliminiamo l’elemento centrale e manteniamo gli altri due elementi,
applicando lo stesso algoritmo possiamo calcolare un diametro approssimato (cioè la
coppia di elementi più distanti);
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
106
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
A
107
>
B
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
SB
SA
A
108
>
B
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
SB
SA
A1
B
A
>
A2
109
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
SA
SB
SA1
A1
B
A
>
SA2
A2
110
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
SA
SB
CA1
A1
B
A
CA2
A2
111
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
B1
SA
CA1
SB
A1
B
>
A
B2
CA2
A2
112
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
SB1
B1
SA
CA1
SB
A1
B
A
B2
CA2
A2
113
SB2
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
CB1
B1
SA
CA1
SB
A1
B
A
B2
CA2
A2
114
CB2
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

Costruzione dell’Antipole Tree
CB1
B1
CA1
A1
B2
CA2
A2
115
CB2
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/
How to align two clusters
How to align the sequences in a cluster
Multiple sequence alignment via the Antipole tree
116
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/
ANTICLUSTAL++

Costruisce una libreria di pesi per ogni coppia di residui allo stesso modo di TCoffee;

Le sequenze sono clusterizzate con l’algoritmo Antipole;

L’albero antipole è visitato in modo bottom-up producendo una “Level Matrix”: Ad
ogni step se due sequenze si trovano assieme nello stesso cluster, la
corrispondente entry nella matrice viene incrementato;

Alla fine la “Level Matrix” darà un indice di similarità tra le sequenze; Tale matrice
verrà usata per raffinare la libreria che alla fine verrà usata per l’allineamento vero
e proprio allo stesso modo di T-Coffee;
117
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/
Formato di Output:
FASTA, GCG, etc;
Metodi per calcolare la
libreria: ClustalW,
FASTA etc.
Programmazione
dinamica: Myers and
Miller, FASTA, etc.
Usare un albero
filogenetico
precalcolato;
118
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/
Metric: CRISP o PAM;
Diameter: Distanza per cui due sequenze sono considerate diverse;
GOP e GEP;
Metodo di vista dell’albero antipole: Right Left o Left Right;
Web Logo: E’ una rappresentazione grafica dell’allineamento; Si possono fornire i
residui di Start e End per la rappresentazione grafica;
119
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/
ESEMPIO: Risultati di un allineamento con tutti gli elementi scaricabili;
120
Bioinformatica
Allineamento Multiplo – Anticlustal
http://alfredo.dmi.unict.it/ac2/

ESERCIZIO:

Utilizzando Entrez o SRS, estrai le sequenze in formato Fasta delle proteine aventi i
seguenti accession number: P96551, P47700, P48525, O33120 e O25360 e prendi
nota degli organismi a cui appartengono;

Conservare le sequenze fasta in un file;

Confrontare l’albero filogenetico costruito con ClustalW e quello ottenuto
dall’algoritmo antipole. Ci sono differenze?
121
Bioinformatica
Allineamento Multiplo – MUSCLE
http://www.ebi.ac.uk/Tools/msa/muscle/

MUSCLE: MUltiple Sequence Comparison by Log- Expectation
122
Bioinformatica
Allineamento Multiplo – MUSCLE
http://www.ebi.ac.uk/Tools/msa/muscle/
Stage 1
Stage 2
Stage 3
123
Bioinformatica
Allineamento Multiplo – MUSCLE
http://www.ebi.ac.uk/Tools/msa/muscle/
Stage 1
Stage 2
Stage 3
124
Bioinformatica
MUSCLE - Stage 1
1.
Calcola la kmer distance tra tutte le coppie di sequenze;
2.
Similmente al neighbor- joining, con tali distanze viene
calcolato il guide tree basato su UPGMA (Unweighted Pair
Group Method with Arithmetic mean);
3.
Calcola l’allineamento progressivo;
125
Bioinformatica
MUSCLE - Stage 2: Improved progressive
1.
Utilizzando l’allineamento del primo step, vengono estratti tutti gli
allineamenti pairwise che ne derivano;
2.
Viene calcolata la Kimura distance tra tutte le coppie di sequenze;
3.
Viene calcolato un nuovo albero usando queste distanze;
4.
Viene calcolato un nuovo allineamento multiplo con l’allineamento
progressivo;
127
Bioinformatica
MUSCLE - Stage 3:Refinement
1.
Sceglie un arco random nell’albero;
2.
Divide le sequenze in due set;
3.
Estrae i due allineamenti multipli (profile) corrispondenti;
4.
Rellainea i due profili;
5.
Accetta il nuovo allineamento se gli score (Sum of Pair) sono migliori;
6.
Itera;
129
Bioinformatica
Allineamento Multiplo – MUSCLE
http://www.ebi.ac.uk/Tools/msa/muscle/
130
Bioinformatica
Allineamento Multiplo – MUSCLE
http://www.ebi.ac.uk/Tools/msa/muscle/
131
Bioinformatica
Allineamento Multiplo – PROBCONS
http://probcons.stanford.edu/
132
Bioinformatica
Allineamento Multiplo – PROBCONS
http://probcons.stanford.edu/
L’algoritmo:
(1) Calcola le Pair HMM posterior probabilities per ogni coppia
di sequenze;
(2) Calcola la maximum expected accuracy tra tutte le coppie di
sequenze;
(3) Applica la probabilistic consistency transformation alle
posterior probabilities;
(4)Calcola il guide tree dai valori maximum expected accuracy;
(5)Allinea le sequenze progressivamente usando il guide tree;
(6)Raffina iterativamente l’allineamento multiplo;
133
Bioinformatica
First order Hidden Markov Model
(HMM)
Hidden
states
H1
H2
Hi
HL-1
HL
X1
X2
Xi
XL-1
XL
Observed
symbols
transition probabilities (between hidden states)
emission probabilities (probability that a given
observation symbol was generated by a hidden
state)
Three problems
Markov Property:
The state of the system at time i+1 depends
only on the state of the system at time i
Pr( X i 1  a | X i  b)
Evaluation
(Computed with forward and backward probabilities)
Given a model M and an observation x,
Compute Pr[ x | M ]
Decoding (Viterbi Algorithm or Posterior Decoding)
Given a model M and an observation x,
Identify a hidden state  sequence
which maximizes Pr[ x,  | M ]
134
Likelihood of evidence
Given a model M with unspecified transition emission
probabilities and an observation x
Bioinformatica
Pr[x| M]
Durbin et al. (1998)
Pair HMMs
d
e
With pair HMMs
IS
qs[i]
d
1  e 

1  2d 

M
Ps[i]t[j]
START
1  2d 
END

d

IT
qt[j]
1  e 
d
Viterbi algorithm can be used to compute the
optimal pairwise alignment of two sequences;
computing if two sequences are related to the
pair HMM using the forward algorithm;
finding the posterior probabilities of an
alignment, an aligned pair of symbols;
e
computing the expected accuracy of a given
alignment.
Transition probabilities:
start
M
IS
I
end
T
Emission probabilities:
M  Pr[(a,b) | M] = pab
start
--
1-2δ-τ
δ
δ
τ
M
--
1-2δ-τ
δ
δ
τ
IS  Pr[(a,-) | IS] = qa
IS
--
1-ε-τ
ε
--
τ
--
1-ε-τ
--
ε
τ
IT  Pr[(-,a) | IT] = qa
--
--
-- --
1
IT
135
end
BLOSUM estimation
Bioinformatica
Durbin et al. (1998)
PHMM posterior probabilities for each pair of sequences.
Reliability measure for each part of an alignment
e


Given two residues si, tj from
sequence S and T of length n and m
Uses forward and backward
algorithms for Pair HMM to compute
posterior probabilities that si and tj are
matched in the alignment (the true
biological one)
IS
qs[i]
d
1 2d
1 e
M
Ps[i]t[
j]
1 e
f (i, j )bM (i, j )
Pr( si ~ t j | S , T )   Pr( a | S , T ) 1{si ~ t j  a}  M
Pr( S , T )
aA
d
IT
qt[j]
e
Will be equal to 1 when si and tj are aligned in a, 0 otherwise
The probability of any single complete path being entirely correct is small.
To analyze the local accuracy of an alignment could result very useful. Often part of an alignment is fairly
clear and other regions are less certain.
136be useful to be able to give a reliability measure for each part of an alignment.
Bioinformatica
It can
Compute the maximum expected
accuracy

Compute an alignment a by align sequences with simple
Needleman-Wunsch algorithm



Using the posterior probabilities as the match and mismatch scores
Set Gap penalties to 0
The goal is to find an alignment a which maximizes the
expected accuracy (try to identify a* -- the best alignment -for all sequence pairs). This can be expressed in function of
posterior match probabilities.
Ea* (accuracy (a, a*) | S , T ) 
137
1
Pr( si ~ t j | S , T )

min{ n, m} si ~t j a
Bioinformatica
Probabilistic consistency

Apply probabilistic consistency approximating it using
matrix multiplication.

The probability of residues si and tj being aligned given the
set of all sequences
1
S
138
 Pr(s
zS z k
i
~ zk | x, z ) Pr( zk ~ t j | z, y)
Bioinformatica
Guide tree computation
and progressive alignment

Use UPGMA as guide tree built using maximum expected
accuracy distances

Perform profile alignment with sum-of-pairs with maximal
expected accuracy scoring

No gap penalties
139
Bioinformatica
Iterative refinement

Randomly partition sequences into two sets

Extract multiple alignments for both sets from
current multiple alignment

Re-align two multiple alignments

No gap penalty, sum-of-pairs scoring guaranteed to
increase or stay the same
140
Bioinformatica

ProbCons is a PHMM model-based progressive alignment
which
uses Maximum Expected Accuracy and integrates probabilistic
consistency transformation.
141
Bioinformatica
Allineamento Multiplo – PROBCONS
http://probcons.stanford.edu/
142
Bioinformatica