Bioinformatica Allineamento di sequenze e ricerca di similarità Dr. Giuseppe Pigola –...
-
Upload
vittoria-valentino -
Category
Documents
-
view
224 -
download
0
Transcript of Bioinformatica Allineamento di sequenze e ricerca di similarità Dr. Giuseppe Pigola –...
BioinformaticaAllineamento 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.
Bioinformatica2
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à.
Bioinformatica3
Globale
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||. | | | .| .| || || | || TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
Locale
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||||||||.|||| TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
Globale
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||. | | | .| .| || || | || TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
Locale
LTGARDWEDIPLWTDWDIEQESDFKTRAFGTANCHK ||||||||.|||| TGIPLWTDWDLEQESDNSCNTDHYTREWGTMNAHKAG
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.
Bioinformatica4
Allineamento Pairwise – Matrici Dot Plot
Bioinformatica5
margaretd
yhqff
a
m a r g a r e t d a y h q f fq elk ra** * ** **
*
* * * *
* * *
* ** ** *
*****
*
Duplicazione
Inversione
Similarità
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
risultino identiche per s residui su w.
Bioinformatica6
),...,,( ),...,,( 11 wjjwii bbbaaa
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet
Preleviamo la sequenza proteica della calmodulina umana con accession Number CAA36839;
Confrontate la sequenza con se stessa per mezzo di DotLet;
Lasciare come parametri iniziali la matrice Blosum62 ed una finestra di 15 residui per il confronto
Bioinformatica7
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.Bioinformatica8
Num di score conquel punteggio
Punteggio ottenuto
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet
Cliccando sulla matrice si attiva un reticolo che può essere spostato sulla superficie della matrice stessa con il puntatore del mouse;
In basso viene riportato l’allineamento tra i due segmenti della proteina corrispondenti alla posizione del centro del reticolo sulla matrice;
Bioinformatica9
DotLet - http://myhits.isb-sib.ch/cgi-bin/dotlet
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;
Bioinformatica10
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%
Bioinformatica11
SLIT_DROME (P24014):MAAPSRTTLMPPPFRLQLRLLILPILLLLRHDAVHAEPYSGGFGSSAVSSGGLGSVGIHIPGGGVGVITEARCPRVCSCT GLNVDCSHRGLTSVPRKISADVERLELQGNNLTVIYETDFQRLTKLRMLQLTDNQIHTIERNSFQDLVSLERLDISNNVI TTVGRRVFKGAQSLRSLQLDNNQITCLDEHAFKGLVELEILTLNNNNLTSLPHNIFGGLGRLRALRLSDNPFACDCHLSW LSRFLRSATRLAPYTRCQSPSQLKGQNVADLHDQEFKCSGLTEHAPMECGAENSCPHPCRCADGIVDCREKSLTSVPVTL PDDTTDVRLEQNFITELPPKSFSSFRRLRRIDLSNNNISRIAHDALSGLKQLTTLVLYGNKIKDLPSGVFKGLGSLRLLL LNANEISCIRKDAFRDLHSLSLLSLYDNNIQSLANGTFDAMKSMKTVHLAKNPFICDCNLRWLADYLHKNPIETSGARCE SPKRMHRRRIESLREEKFKCSWGELRMKLSGECRMDSDCPAMCHCEGTTVDCTGRRLKEIPRDIPLHTTELLLNDNELGR ISSDGLFGRLPHLVKLELKRNQLTGIEPNAFEGASHIQELQLGENKIKEISNKMFLGLHQLKTLNLYDNQISCVMPGSFE HLNSLTSLNLASNPFNCNCHLAWFAECVRKKSLNGGAARCGAPSKVRDVQIKDLPHSEFKCSSENSEGCLGDGYCPPSCT CTGTVVACSRNQLKEIPRGIPAETSELYLESNEIEQIHYERIRHLRSLTRLDLSNNQITILSNYTFANLTKLSTLIISYN KLQCLQRHALSGLNNLRVVSLHGNRISMLPEGSFEDLKSLTHIALGSNPLYCDCGLKWFSDWIKLDYVEPGIARCAEPEQ MKDKLILSTPSSSFVCRGRVRNDILAKCNACFEQPCQNQAQCVALPQREYQCLCQPGYHGKHCEFMIDACYGNPCRNNAT CTVLEEGRFSCQCAPGYTGARCETNIDDCLGEIKCQNNATCIDGVESYKCECQPGFSGEFCDTKIQFCSPEFNPCANGAK CMDHFTHYSCDCQAGFHGTNCTDNIDDCQNHMCQNGGTCVDGINDYQCRCPDDYTGKYCEGHNMISMMYPQTSPCQNHEC KHGVCFQPNAQGSDYLCRCHPGYTGKWCEYLTSISFVHNNSFVELEPLRTRPEANVTIVFSSAEQNGILMYDGQDAHLAV ELFNGRIRVSYDVGNHPVSTMYSFEMVADGKYHAVELLAIKKNFTLRVDRGLARSIINEGSNDYLKLTTPMFLGGLPVDP AQQAYKNWQIRNLTSFKGCMKEVWINHKLVDFGNAQRQQKITPGCALLEGEQQEEEDDEQDFMDETPHIKEEPVDPCLEN KCRRGSRCVPNSNARDGYQCKCKHGQRGRYCDQGEGSTEPPTVTAASTCRKEQVREYYTENDCRSRQPLKYAKCVGGCGN QCCAAKIVRRRKVRMVCSNNRKYIKNLDIVRKCGCTKKCY
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);
Bioinformatica12
Allineamento PairwiseSiano 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’allineamento ottimale sarà quello che massimizza la similarità (lo score);
Bioinformatica13
l
i
iTiS1
]['],['
Allineamento Pairwise ESEMPIO: NEEDLEMAN-WUNSCH
Lo score ottimale V(i,j) di due sequenze S1….i T1…j ha le seguenti proprietà:
Algoritmo di programmazione dinamica per calcolare l’allineamento
Bioinformatica14
),()1,(
),(),1(
),()1,1(
max),(
),(),0(
),()0,(
0
0
j
i
ji
j
kk
i
kk
TjiV
SjiV
TSjiV
jiV
TjV
SiV
match/mismatchdeletion
insertion
Allineamento Pairwise ESEMPIO: NEEDLEMAN-WUNSCH
Bioinformatica15
j
230-3-3-6B6
301-2-2-5D5
11-1-1-1-4C4
12-100-3B3
-2-1001-2C2
-2-101-1-1A1
-5-4-3-2-10-
DBDACi
54321-
S1 = ACBCDBS2 = CADBD
Allineamento ottimale V(6,5) = 2
Otteniamo tre allineamenti ottimali:
ACBCDB- ACBCDB- -ACBCDB | || | || | | | -C-ADBD -CA-DBD CADB-D-
S2
S1
),()1,(
),(),1(
),()1,1(
max),(
j
i
ji
TjiV
SjiV
TSjiV
jiV
otherwise
baba
1
2),(
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;
Bioinformatica16
Allineamento Pairwise – Matrici di Score
Bioinformatica17
Seq1 V D S - C YSeq2 V E S L C YScore 4 2 4 -11 9 7
Score allineamento: 15
blosum62
Penalità del gap.
Allineamento Pairwise - EMBOSShttp://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica18
Allineamento Pairwise - EMBOSShttp://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica19
Utilizziamo EMBOSS per allineare due sequenze con gli algoritmi di
Needleman-Wunsch (globale);
Smith-Waterman (locale);
Allineamento Pairwise - EMBOSS http://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica20
Selezioniamo il tipo di sequenza:
Protein; DNA;
Allineamento Pairwise - EMBOSS http://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica21
Scelta della scoring matrix:
Protein: Blosum62; Blosum50; Blosum40;
DNA: DNAFull: (Assegna
score diversi nel caso di mismatch di caratteri IUB-IUPAC);
DNAMat: (usata da BLAST assegna uno score al match e un altro al mismatch);
Allineamento Pairwise - EMBOSS http://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica22
GOP e GEP;
Allineamento Pairwise - EMBOSS http://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica23
Inserimento delle due sequenza anche da file;
Allineamento Pairwise - EMBOSS http://www.ebi.ac.uk/Tools/emboss/align/
Bioinformatica24
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);
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica25
BLASTBasic Local Alignment Search Tool
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica26
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica27
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica28
MEGABLASTE’ utilizzato per trovare efficientemente lunghi allineamenti tra sequenze molto simili tra loro o per identificare una sequenza di input sconosciuta.
BLAST NUCLEOTIDICO
Discontiguous MEGABLASTE’ utilizzato per trovare efficientemente lunghi allineamenti tra sequenze che hanno alcune differenze tra loro.
BLASTNUtilizzato in tutti gli altri casi.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica29
BLASTPE’ utilizzato per identificare una sequenza proteica di input nel DB o per ricercare sequenze proteiche simili;
BLAST PROTEICO
PSI-BLASTPosition-Specific Iterata BLAST è il programma BLAST più sensibile, il che lo rende molto utile per trovare proteine poco correlate (molto distanti).PHI-BLASTPattern-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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica30
BLASTX (Translated query vs protein database)E’ utilizzato per trovare proteine simili a quelle codificate da una query di nucleotidi;
ALTRI TOOL
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.BLAST2SEQUtilizza BLAST per allineare due o più sequenze.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica31
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica32
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica33
Ottimizza la ricerca per:
Similarità; Dissimilarità; Ricerca
generica;
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica34
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica35
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica36
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.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica37
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;
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica38
Dati generali
Allineamento grafico: I colori indicano la qualità dell’allineamento.
Le prime due sequenze sono identiche.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica39
Le prime due sequenze sono identiche alla query (per questo motivo BLAST può essere usato per ricercare sequenze sconosciute).
Le altre sono sequenze parziali.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica40
Scorrendo i risultati troviamo altre sequenze (anche parziali) in altri tipi di Drosophile.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica41
Infine troviamo i dettagli dei vari allineamenti.I trattini indicano un match, la loro assenza indica un mismatch.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica42
MAX SCOREPunteggio dell’allineamento locale più significativo. (punteggio alto → elevata similarità);
TOTAL SCORELa somma dei punteggi di tutti gli allineamenti locali trovati tra la sequenza query e le sequenze del database.QUERY COVERAGEPercentuale della sequenza allineata
E-VALUEEsprime 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 INDENTPercentuale di identità dell’allineamento locale più significativo.
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica43
VALIDAZIONE STATISTICA e BIT SCORE
La probabilità di trovare un allineamento con score maggiore o uguale di S segue la distribuzione di Poisson
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 è
Il bit-score non è altro che lo score normalizzato in modo da poter confrontare bit-score di banche dati diverse
SKmneeP1
SKmne
2ln
)log('
KSS
Allineamento Pairwise – BLAST2SEQhttp://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica44
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).
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica45
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;
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica46
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;
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica47
ESERCIZIOData la seguente sequenza sconosciuta. Determinare l’identità più probabile.
>SCONOSCIUTAATCACTGTAGTAGTAGCTGGAAAGAGAAATCTGTGACTCCAATTAGCCAGTTCCTGCAGACCTTGTGAGGACTAGAGGAAGAATGCTCCTGGCTGTTTTGTACTGCCTGCTGTGGAGTTTCCAGACCTCCGCTGGCCATTTCCCTAGAGCCTGTGTCTCCTCTAAGAACCTGATGGAGAAGGAATGCTGTCCACCGTGGAGCGGGGACAGGAGTCCCTGTGGCCAGCTTTCAGGCAGAGGTTCCTGTCAGAATATCCTTCTGTCCAATGCACCACTTGGGCCTCAATTTCCCTTCACAGGGGTGGATGACCGGGAGTCGTGGCCTTCCGTCTTTTATAATAGGACCTGCCAGTGCTCTGGCAACTTCATGGGATTCAACTGTGGAAACTGCAAGTTTGGCTTTTGGGGACCAAACTGCACAGAGAGACGACTCTTGGTGAGAAGAAACATCTTCGATTTGAGTGCCCCAGAGAAGGACAAATTTTTTGCCTACCTCACTTTAGCAAAGCATACCATCAGCTCAGACTATGTCATCCCCATAGGGACCATTGGCCAAATGAAAAATGGATCAACACCCATGTTTAACGACATCAATATTTATGACCTCTTTGTCTGGATGCATTATTATGTGTCAATGGATGCACTGCTTGGGGGATCTGAAATCTGGAGAGACATTGATTTTGCCCATGAAGCACCAGCTTTTCTGCCTTGGCATAGACTCTTCTTGTTGCGGTGGGAACAAGAAATCCAGAAGCTGACAGGAGATGAAAACTTCACTATTCCATATTGGGACTGGCGGGATGCAGAAAAGTGTGACATTTGCACAGATGAGTA
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica48
ESERCIZIO IRicercare 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?
Similarità nei DB - BLAST http://www.ncbi.nlm.nih.gov/BLAST
Bioinformatica49
ESERCIZIO IIConsiderare la seguente sequenza proteica del lievito:
>gi|2498220|sp|Q06703.1|CDA2_YEAST Chitin deacetylase 2 precursor MRIQLNTIDLQCIIALSCLGQFVHAEANREDLKQIDFQFPVLERAATKTPFPDWLSAFTGLKEWPGLDPP YIPLDFIDFSQIPDYKEYDQNHCDSVPRDSCSFDCHHCTEHDDVYTCSKLSQTFDDGPSASTTKLLDRLK HNSTFFNLGVNIVQHPDIYQRMQKEGHLIGSHTWSHVYLPNVSNEKIIAQIEWSIWAMNATGNHTPKWFRPPYGGIDNRVRAITRQFGLQAVLWDHDTFDWSLLLNDSVITEQEILQNVINWNKSGTGLILEHDSTEKTV 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.
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica50
FASTASequence Similarity Search using the FASTA
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica51
STEP 1- Scelta del DB
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica52
STEP 1I - Inserimento della sequenza
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica53
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;
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica54
STEP 1V - Opzioni:
Match/mismatch scores;
GOP e GEP;
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica55
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.
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica56
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.
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica57
STEP 1V - Opzioni:
Opzioni di visualizzazione dei risutati.
Similarità nei DB - FASTA http://www.ebi.ac.uk/Tools/sss/fasta/
Bioinformatica58
Eseguiamo FASTA sulla proteina DIABLO di Drosophila Melanogaster
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica59
CLUSTALWMultiple sequence alignment program for DNA or proteins
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica60
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;
AGTTGGACTTGG
CCTTGGAGTTGG
AG__GGCCTTGGAGTTGG
AGTTGGACTTGGAG__GGCCTTGGAGTTGG
AGTTGG
AGGGCCTTGGAGTTGC
ACTTGG
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica61
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;
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 ½ ½ ¾
A-GTT—TAAC-TTA--ACGTAAG--C-TA---
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica62
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
),(),( bapiba
aisp
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica63
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
Rimpiazzando la funzione di score σ con σpp l’allineamento di due allineamenti multipli si riduce al confronto di due profili;
}{ }{
),(),(a b
bjaipp bappji
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica64
Utilizziamo SRS;
Selezioniamo “Library Page”;
Scegliamo il DB “Uniprotkb-SwissProt”;
Clicchiamo su “Standard Query
Form”;
ESEMPIO PRATICO: Vogliamo allineare le sequenze aminoacidiche della proteina NAD6 dei
metazoi ma non dei mammiferi;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica65
Impostiamo la Query
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica66
Salviamo i risultati in un file di testo nel formato “fasta2seqs”;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica67
Sul sito di ClustalW facciamo un upload delle sequenze e lanciamo il tool
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica68
Risultato dell’allineamento: Formato testuale e colori.
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica69
Sommario: Tabella delle distanze
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica70
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 +;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica71
Albero filogenetico ricavato dall’allineamento progressivo (i rami hanno lunghezza proporzionale alla distanza tra le sequenze) .
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica72
OPZIONI.
Si seleziona il tipo di sequenza;
Si incollano le sequenze o si fa un upload di un file;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica73
OPZIONI.
Pairwise Alignment Type:
Slow (lento ma accurato);
Fast (veloce ma approssimato);
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica74
OPZIONI.
SLOW OPTIONS
Matrici di score;
GOP;
GEP;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica75
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;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica76
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;
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica77
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.
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica78
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?
Allineamento Multiplo - Clustalw http://www.ebi.ac.uk/Tools/msa/clustalw2/
Bioinformatica79
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.
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica80
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica81
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);
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;
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica82
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:
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.
pos
SSsimSSI
100),(),( 21
21%
S1) A C A - G – T C AS2) A G - T G C T – T
605
1003),( 21%
SSI
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica83
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:
Seq1 Seq2 Res1 Res2 WeightS1 S2 1 1 60S1 S2 2 2 60S1 S2 4 4 60S1 S2 5 6 60S1 S2 7 7 60
S1) A C A - G – T C AS2) A G - T G C T – T
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica84
• 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à:
• 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.
S1
S2
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica85
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 ClustalWSeq1 Seq2 Res1 Res2 Weight
S1 S2 1 1 60S1 S2 2 2 60S1 S2 3 3 60S1 S2 5 6 60S1 S2 7 7 60
Local Alignments by LAlignSeq1 Seq2 Res1 Res2 Weight
S1 S2 1 1 30S1 S2 2 2 30S1 S2 3 3 30S1 S2 15 22 10S1 S2 16 23 10
Primary LibrarySeq1 Seq2 Res1 Res2 Weight
S1 S2 1 1 90S1 S2 2 2 90S1 S2 3 3 90S1 S2 5 6 60S1 S2 7 7 60S1 S2 15 22 10S1 S2 16 23 10
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica86
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;
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica87
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 CATSeqB GARFIELD THE FAST CA-T ---SeqC GARFIELD THE VERY FAST CATSeqD THE FA-T CAT
SeqA GARFIELD THE LAST FA-T CATSeqB GARFIELD THE ---- FAST CATSeqC GARFIELD THE VERY FAST CATSeqD THE FA-T CATfrom Notredam et al. 2000
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica88
SeqA GARFIELD THE LAST FAT CAT SeqB GARFIELD THE FAST CAT ---
SeqA GARFIELD THE LAST FA-T CATSeqC GARFIELD THE VERY FAST CAT
SeqA GARFIELD THE LAST FAT CATSeqD -------- THE ---- FAT CAT
SeqB GARFIELD THE ---- FAST CATSeqC GARFIELD THE VERY FAST CAT
SeqB GARFIELD THE FAST CATSeqD -------- THE FA-T CAT
SeqC GARFIELD THE VERY FAST CATSeqD -------- THE ---- FA-T CAT
Consistency
SeqA GARFIELD THE LAST FAT CAT |||||||| ||| |||| |||SeqB GARFIELD THE FAST CAT ---
SeqA GARFIELD THE LAST FAT CAT |||||||| ||| |||| || \ \\\SeqC GARFIELD THE VERY FAST CAT |||||||| ||| |||| |||| |||SeqB GARFIELD THE FAST CAT
SeqA GARFIELD THE LAST FAT CAT ||| ||| |||SeqD THE FAT CAT ||| ||\ \\\ SeqB GARFIELD THE FAST CAT
STEP II: Per ogni coppia di sequenze controlla l’allineamento di ogni coppia di residui usando gli altri allineamenti;
Extended library
SeqA GARFIELD THE LAST FAT CAT
SeqB GARFIELD THE FAST CAT
Programmazione dinamica
SeqA GARFIELD THE LAST FA-T CAT
SeqB GARFIELD THE ---- FAST CAT
w(A(G),B(G)) + min(w(A(G),C(G)) w(C(G),B(G)))
I pesi sono utilizzati nell’allineamento finale progressivo al posto delle matrici di score
Per esempio la coppia A(G),B(G) avrà un peso dato da:
STEP I: Library of pairwise alignments
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica89
L’algoritmo:(1) Calcolo degli allineamenti pairwise
con ClustalW;
(2) Calcolo degli allineamenti locali con LAlign (10 migliori allineamenti per ogni coppia di sequenza)
(3) Calcolo della primary library con i relativi pesi;
(4) Estensione della libreria con il calcolo dei pesi in base a tutti gli allineamenti pariwise;
(5) Allineamento progressivo usando i pesi per ogni coppia di residui al posto delle matrici di score;
Weighting
Primary library
Extension
Extended library
Progressive alignment
ClustalW globalPairwise alignments
LAlign local pairwise alignments
ABC
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica90
Tool Online sul sito di EMBL
Allineamento Multiplo – TCoffee http://www.ebi.ac.uk/Tools/msa/tcoffee/
Bioinformatica91
Esempio di Output del tutto simile a quello di ClustalW;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica92
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica93
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: Costruire l’albero di clustering (rappresenta l’albero filogenetico); Allinea progressivamente le sequenze partendo dalle foglie fino alla radice
che conterrà l’allineamento finale;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica94
CLUSTERING: Presupposto: Sequenze lontane saranno sicuramente in cluster
diversi.
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 σ;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica95
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:
Per k = 1 il problema è chiamato 1-mediana e consiste nel ricercare un elemento tale che la seguente funzione è minimizzata:
Ssi
kik csdcccw ),(min),...,,(
,...,121
Ss
csdcw ),()(
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica96
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica97
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica98
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica99
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica100
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica101
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica102
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica103
1-Mediana approssimata
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica104
1-Mediana approssimata
The final winner
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica105
Pseudo Diametro: 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);
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica106
Costruzione dell’Antipole Tree
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica107
Costruzione dell’Antipole Tree
AB>
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica108
Costruzione dell’Antipole Tree
AB>
SASB
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica109
Costruzione dell’Antipole Tree
>
SASB
A1
A2
BA
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica110
Costruzione dell’Antipole Tree
>
SASB
A1
A2
BA
SA1
SA2
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica111
Costruzione dell’Antipole Tree
SASB
A1
A2
B
CA1
CA2
A
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica112
Costruzione dell’Antipole Tree
B>
SASB
A1
A2
B2
B1
CA1
CA2
A
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica113
Costruzione dell’Antipole Tree
B
SASB
A1
A2
B2
B1
CA1
CA2
A
SB1
SB2
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica114
Costruzione dell’Antipole Tree
B
SASB
A1
A2
B2
B1
CA1
CA2
A
CB1
CB2
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica115
Costruzione dell’Antipole Tree
A1
A2
B2
B1
CA1
CA2
CB1
CB2
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica116
How to align two clusters
How to align the sequences in a cluster
Multiple sequence alignment via the Antipole tree
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica117
ANTICLUSTAL++ Costruisce una libreria di pesi per ogni coppia di residui allo stesso
modo di T-Coffee;
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;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica118
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;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica119
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;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica120
ESEMPIO: Risultati di un allineamento con tutti gli elementi scaricabili;
Allineamento Multiplo – Anticlustal http://alfredo.dmi.unict.it/ac2/
Bioinformatica121
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?
Allineamento Multiplo – MUSCLE http://www.ebi.ac.uk/Tools/msa/muscle/
Bioinformatica122
MUSCLE: MUltiple Sequence Comparison by Log- Expectation
Allineamento Multiplo – MUSCLE http://www.ebi.ac.uk/Tools/msa/muscle/
Bioinformatica123
Stage 1
Stage 2
Stage 3
Allineamento Multiplo – MUSCLE http://www.ebi.ac.uk/Tools/msa/muscle/
Bioinformatica124
Stage 1
Stage 2
Stage 3
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;
Bioinformatica125
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;
Bioinformatica127
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;
Bioinformatica129
Allineamento Multiplo – MUSCLE http://www.ebi.ac.uk/Tools/msa/muscle/
Bioinformatica130
Allineamento Multiplo – MUSCLE http://www.ebi.ac.uk/Tools/msa/muscle/
Bioinformatica131
Allineamento Multiplo – PROBCONS http://probcons.stanford.edu/
Bioinformatica132
Allineamento Multiplo – PROBCONS http://probcons.stanford.edu/
Bioinformatica133
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;
First order Hidden Markov Model (HMM)
X1X2 XL-1 XLXi
Hidden states
Observed symbols
H1 H2 HL-1 HLHi
Markov Property: The state of the system at time i+1 depends only on the state of the system at time i
)|Pr( 1 bXaX ii
transition probabilities (between hidden states)
emission probabilities (probability that a given observation symbol was generated by a hidden state)
Three problems
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 sequencewhich maximizes Pr[ x, | M ]
Likelihood of evidenceGiven a model M with unspecified transition emission probabilities and an observation xPr[x| M] Durbin et al. (1998)
Bioinformatica134
Pair HMMs
START
MPs[i]t[j]
IS
qs[i]
IT
qt[j]
21
1
1
END
21
start M IS IT end
start -- 1-2δ-τ δ δ τ
M -- 1-2δ-τ δ δ τ
IS -- 1-ε-τ ε -- τ
IT -- 1-ε-τ -- ε τ
end -- -- -- -- 1
Emission probabilities:
M Pr[(a,b) | M] = pab
IS Pr[(a,-) | IS] = qa
IT Pr[(-,a) | IT] = qaBLOSUM estimation
Transition probabilities:
With pair HMMs
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;
computing the expected accuracy of a given alignment.
Durbin et al. (1998)Bioinformatica135
PHMM posterior probabilities for each pair of sequences. Reliability measure for each part of an alignment
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)
MPs[i]t[j
]
IS
qs[i]
IT
qt[j]
21
1
),Pr(
),(),(}~1{),|Pr(),|~Pr(
TS
jibjifatsTSaTSts MM
Aajiji
1
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. It can be useful to be able to give a reliability measure for each part of an alignment. Bioinformatica136
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.
ats
jia
ji
TStsmn
TSaaaccuracyE~
* ),|~Pr(},min{
1),|*),((
Bioinformatica137
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
Sz z
jkki
k
yztzzxzsS
),|~Pr(),|~Pr(1
Bioinformatica138
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
Bioinformatica139
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
Bioinformatica140
ProbCons is a PHMM model-based progressive alignment which
uses Maximum Expected Accuracy and integrates probabilistic consistency transformation.
Bioinformatica141
Allineamento Multiplo – PROBCONS http://probcons.stanford.edu/
Bioinformatica142