ࡱ> (   H(http://fasta.bioch.virginia.edu/fasta_www/cgi/search_frm.cgi?pgm=fahttp://fasta.bioch.virginia.edu/fasta_www/cgi/search_frm.cgi?pgm=fa?<http://www.ncbi.nih.gov/BLAST/<http://www.ncbi.nih.gov/BLAST/B:http://www.ebi.ac.uk/fasta33/:http://www.ebi.ac.uk/fasta33/DDhttp://www.ncbi.nlm.nih.gov/BLAST/Dhttp://www.ncbi.nlm.nih.gov/BLAST// 00DTimes New Romanll+b0DCourier Newmanll+b071 DWingdingswmanll+b070DSymbolgswmanll+b07@(.2 @n?" dd@  @@``  XU4 # N     +,-./012345678 +  +F 0e0e     A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||S"@auʚ;~:ʚ;g4CdCd7 b0ppp@ <4!d!d8i0l*<4dddd8i0l* <4BdBd8g0l0___PPT10 pp___PPT9?BD? %*&+',(-).*/+0,1-2.3/40516283t  0` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>>  6(    60 "P  m9Fare clic per modificare lo stile del titolo dello schema: :G  0X "  uFare clic per modificare gli stili del testo dello schema Secondo livello Terzo livello Quarto livello Quinto livello: v  0| "``  X*  0 "`   Z*  0Ȭ "`   Z*B  s *޽h ? ̙33 *Struttura predefinital0 #(    0hp W#Algoritmi EURISTICI di allineamento$ 2$5  0 0 Sono nati insieme alle banche dati, con lo scopo di permettere una ricerca per similarit rapida anche se meno accurata contro le migliaia di sequenze depositate. (2  0P` \,Attualmente i programmi pi utilizzati sono:- 2-+  0P0 P  5FASTA: Lipman & Pearson (1985) BLAST: Altshul (1990)46 2  >  H  0޽h ? ̙33y___PPT10Y+D=' += @B +K0 r j  (    0$Ց0  9FASTA 2(  0? L algoritmo implementato in FASTA si basa su una strategia di INDICIZZAZIONE delle parole: la proteina QUERY viene spezzettata in parole di lunghezza ktup (k-tuples) e la query viene cos indicizzata (cio si memorizzano solo gli indici, non la coppia).& 2>P A  0J0@P HTFDERILGVQQTFWECIKGD 2  B@ P@ 61.TF  BlR`   65.RI  BLV  62.FD  B,Z `   66.IL  B^   67.LG  Ba@  64.ER  BLf o  A 20.GD  B,j@p`  63.DE  Bn 0 V 0  8......p  0q Pp Maggiore il valore ktup pi rapida e meno accurata sar la ricerca. Per una proteina a ktup = 2 potr avere al massimo 202 = 400 combinazioni, sempre.((2{,$[  <x ?"}  Nktup = 2 2   H  0޽h ? ̙33y___PPT10Y+D=' += @B +>0 >>P=(    0  > 2   0  Ogni SUBJECT della banca dati viene consultata allo stesso modo, ma anzich indicizzarla, viene consultato l indice della query per vedere se e dove si posiziona il match, e viene memorizzata la diagonale corrispondente (indice della query  indice della subject). $ -1PC.j6x  #   #"*L #  ڸ HD?q#  $-----SUBJECT-----2    @` ظ B?q X   @`*  Bԡ?q  L------------- QUERY ----------------2'%    @` Y B? ; #  X   @` Z B? ; #  X   @` [ B? ; #  X   @` \ B?; #  X   @` ] B?'; #  X   @` ^ B?5; '#  X   @` _ Bp?D; 5#  X   @` ` BT?S; D#  X   @` a B8?b; S#  X   @` b B?q; b#  L-4  @` c Bt ? R ;  X   @` d B? R ;  X   @` e B? R ;  X   @` f B(?R ;  X   @` g B2?'R ;  X   @` h BT;?5R ';  X   @` i BTD?DR 5;  X   @` j BL?SR D;  X   @` k BU?bR S;  X   @` l B^?qR b;  L-3  @` m Bg? i R  X   @` n BY? i R  X   @` o By? i R  X   @` p BЂ?i R  X   @` q B@?'iR  X   @` r B?5i'R  X   @` s B4?Di5R  X   @` t B?SiDR  X   @` u B?biSR  X   @` v Bܷ?qibR  L-2  @` w B?  i X   @` x B?  i X   @` y B?  i X   @` z B? i X   @` { Bh?'i X   @` | B(?5'i X   @` } B\?D5i X   @` ~ BD?SDi X   @`  B?bSi X   @`  B ?qbi L-1  @`  B$?   K9  @`  B,$?   K8  @`  B4-?   K7  @`  B<6?  K6  @`  BD??' K5  @`  BLH?5' K4  @`  BTQ?D5 K3  @`  B\Z?SD K2  @`  Bdc?bS K1  @`  Bll?qb K0  @`fB  6o ?qfB  6o ?# # fB  6o ?fB  6o ?  # ZB  s *1 ? `B θ 01 ?bb# `B ϸ 01 ?SS# `B и 01 ?DD# `B Ѹ 01 ?55# `B Ҹ 01 ?''# `B Ӹ 01 ?# `B Ը 01 ?  # `B ո 01 ?  # `B ָ 01 ?  # ZB ٸ s *1 ?qq# `B  01 ?q `B  01 ?qi i`B  01 ?qR R `B  01 ?q; ; fB  6o ?q fB  6o ?# 8  0s@   Se alla riga successiva della matrice, cio alla parola successiva della subject, c corrispondenza sulla stessa diagonale, la parola viene memorizzata e quindi man mano si allunga la diagonale. 2HtM  0|  Considerando una matrice di sostituzione, vengono riconosciute le migliori diagonali come i segmenti pi lunghi e che totalizzano quindi lo score maggiore. 2 H  0޽h ? ̙33y___PPT10Y+D=' += @B + 0 B(     0ܫ 0 HIl programma ripete queste operazioni per ogni subject della banca dati, identificando le Best Initial Regions i cui punteggi sono chiamati Init1. Con questi fa una graduatoria per decidere su quante e quali sequenze procedere. La scelta delle subject pi adatte stata fatta. Da ora procede con un numero molto minore di proteine subject. Ora il programma cerca di congiungere ogni best initial region della subject confermata utilizzando i parametri di penalty per i gaps. Le regioni vengono allungate e avranno un nuovo score, detto InitN. Alla fine tutta la regione della subject riconosciuta come simile viene allineata mediante l algoritmo di Smith e Waterman, tenendo una finestra di analisi intorno alla diagonale principale abbastanza stretta (< 20 residui). Lo score definitivo definito Opt.^%(2Z.(P14>"A H  0޽h ? ̙33y___PPT10Y+D=' += @B +R,0 y+q+j +(  X  0  0p0 7Query 2  6Z  KSubject 2 RB  s *Do RB  s *Do RB  s *Dop`RB  s *DopRB  s *Do `RB  s *DoRB  s *DoppRB  s *Do`RB  s *Do RB  s *Do0`RB " s *DoPPRB $ s *Do00RB & s *DoRB ' s *Dop`RB ) s *Do@0RB + s *DoP@RB , s *Do@pRB . s *Do0`RB / s *Do0@p`RB 0 s *Do0PRB 1 s *DoRB 2 s *Do0`RB 3 s *DoRB 4 s *DopRB 5 s *Do RB 6 s *Do0`0RB 7 s *Do@RB 8 s *Do@X 9 0  : 00 7Query 2 ; 6ZH  KSubject 2 RB < s *Do RB = s *Do RB > s *Dop`RB ? s *DopRB @ s *Do `RB A s *DoRB B s *Do@RB C s *DoppRB D s *Do`RB E s *Do RB F s *Do0`RB G s *DoPPRB H s *Do00RB I s *DoPRB J s *DoRB K s *Dop`RB L s *Do@0RB M s *DoP@RB N s *Do@pRB O s *Do0`RB P s *Do0@p`RB Q s *Do0PRB R s *DoRB S s *Do0`RB T s *DoRB U s *DopRB V s *Do RB W s *Do0`0RB X s *Do@RB Y s *Do@X Z 0 [ 00 7Query 2 \ 6Z   KSubject 2 RB ] s *Do  RB b s *Do  RB f s *Do0  RB m s *Do RB r s *Do@  LB { c $D  LB | c $D @ LB } c $D 0 LB ~ c $D  X  0`   0``  7Query 2  6Z  KSubject 2 RB  s *Do @0 RB  s *Do  RB  s *Do @0 RB  s *Do RB  s *Do @ LB  c $D 0 LB  c $D  LB  c $D @@ LB  c $D 0 Rb  s *  Xb  0` pRB  s *Do`pRB  s *Do`px2  BL/ ?"f/x2  BL/ ?"PPx2  BL/ ?"@x2  BL/ ?"Px2  BL/ ?"PRB  s *Dox2  BL/ ?"P0RB  s *DoPx2  BL/ ?" p  <@ ?"@ ]Fase 1 : Indicizzazione(2   <T ?"  GFase 3 :Definizione delle sequenze da approfondire, calcolo degli InitNH(2H H  < ?" ` z4Fase 2 : Calcolo degli Init1, generazione delle bits5(25 5  <P ?"P  cFase 4 : Smith-Waterman (Opt)(2 H  0޽h ? ̙33y___PPT10Y+D=' += @B +. 0 U M  (  R  s * p   0D)0  9BLAST 2(  0) XE basato anch esso sull indicizzazione delle parole, ma l utilizzo degli indici poi molto diverso. L algoritmo diviso in tre parti:(2 @`  0) P @  9TFDER 2  B) @  7LSH 2  B) @ @  ? GVQQTFWECIKGD  6,) 0  <VSH = 16 2   B)   <ISH = 14 2   BH)  <LAH = 13 2   6#)  <LTH = 13 2   6')p <LSH = 13 2   <<,)P uV  "w = 3 t = 13  6/)  X1- Creazione di un elenco di parole di lunghezza W dalla query e creazione di w-mers, cio parole di lunghezza W che diano, secondo una matrice di sostituzione uno score > T se allineati sulla query stessa.((2">8l !  07) 0  oPer ogni parola vengono generati anche tutti i possibili w-mers, quindi ci sono molte pi parole che in FASTA. p 2p;1H  0޽h ? ̙33y___PPT10Y+D=' += @B +g 0    (    0A)   NF2 - Ricerca di hits in banca dati per ogni w-mer, segnando ogni volta che un match stato trovato e che la corrispondenza alla parola, non al suo w-mer. Ottengo cos una lista di proteine in cui stata trovata una corrispondenza con i frammenti della query. 3 - Estensione di ogni hit verso entrambe le direzioni senza inserimento di gap, finch il loro score non scende sotto S. Si ottengono regioni dette HSP (High-scoring Segment Pair). In realt anche se lo score scende sotto S, ma solo per alcuni residui, e poi risale, l HSP pu ancora allungarsi. Il parametro X dice la quantit di perdita di score massima tollerabile se si prosegue con l allungamento dell HSP.^(2F32kMH[  <TT) ?" : Query:83 LMVAISNVGTDTLSHLEAQNKIKSASHNLSLTLQKSK +++AIS GT+++SH +AQ++IK+AS+ L L + ++ Subject:48 VILAISGFGTESMSHADAQDRIKAASYQLCLKIDRAE  2 r2  < ?"P pp  N`Z) ?"` I GHSP 2 xB @ BD?"H  0޽h ? ̙33y___PPT10Y+D=' += @B +00 WO (    04b) [)BLAST ha dunque 4 parametri fondamentali:* 2*  0Hg) `/  W: word size, maggiore il numero, minore il numero di parole generate, minore il tempo di esecuzione. Ma la sensibilit decresce sensibilmente. T: threshold, minore il numero, maggiore il numero di w-mers inclusi nella lista, maggiore il tempo di esecuzione. Si ha per un incremento di sensibilit. S: score, minore il numero, maggiore sar la lunghezza degli HSP X: maggiore il numero, pi estesamente sar osservato l intorno di una HSP, aumentando il tempo di esecuzione.T 2Bp> 0H  0޽h ? ̙33y___PPT10Y+D=' += @B +0 0O(    0y) DBLAST stato recentemente implementato con un two-hit method, che prevede che l estensione delle HSP possa avvenire solo se due hits indipendenti si verifichino entro un numero di residui A, senza gaps in mezzo.((2/P.C@ k  0)*, _La potenza di BLAST sta nella sua base statistica che permette di dire quanto accurati sono i suoi risultati: dato un S in fatti possibile prevedere quanti HSP si verificheranno in una banca dati della stessa grandezza di quella vera ma composta da proteine casuali. Questo numero definito E (expected) => molto pi semplice pensare in termini di E che non in termini di S, quindi in realt non si imposta S ma E, ed S viene calcolato automaticamente, rispattando una complessa relazione statistica tra i due valori. Tenendo E molto basso, si quasi certi di avere solo allineamenti significativi. J`G >* H  0޽h ? ̙33y___PPT10Y+D=' += @B +0 @(    0T)  IVarie versioni di BLAST 2  0)` Asblastp: cerca similarit in banche dati proteiche a partire da un a query di amino acidi. blastn: cerca similarit in banche dati di nucleotidi a partire da una query di nucleotidi. blastx: cerca similarit in banche dati proteiche a partire da una query di nucleotidi che viene tradotta in tutti i frame. tblastn: cerca similarit in banche dati di nucleotidi a partire da una query di amino acidi, traducendo in amino acidi tutti i subject della banca dati, in tutti frame. tblastx: cerca similarit in banche dati di nucleotidi a partire da una query di nucleotidi, traducendo in amino acidi tutti i subject della banca datift 2TVvD=$  < %$ 2"$  #H  0޽h ? ̙33y___PPT10Y+D=' += @B +0 PB(     0)NP  ~gapped-blast: porta avanti la fase di estensione delle HSP considerando la possibilit di inserzione dei gap. PSI-BLAST: effettua una ricerca iterativa utilizzando le HSP per generare dei profili caratteristicio della query. PHI-BLAST: estensione di PSI-BLAST per la ricerca in banca dati di pattern proteici pi che di query esatte. BL2SEQ: adattamento di blast per l allineamento a coppie MegaBLAST: pu concatenare molte queries tra loro per minimizzare il tempo di esecuzione dovuto a sequenze query troppo lunghe ( adatto a sequenze nucleotidiche molto simili tra loro)f@ 2 b j d3 ` BIH  0޽h ? ̙33y___PPT10Y+D=' += @B +0 `(    0@)  HMeglio FASTA o BLAST ? 2  0P) c]Gli algoritmi di Blast e Fasta sono simili come strategia, ma molto diversi nei contenuti. Il fatto che Fasta indicizzi le query in modo esatto lo porta a ridurre di molto il numero di subject su cui lavorer in seguito, e questo una tappa limitante che Blast non ha grazie ai w-mers. Per Blast crea i w-mers basati su una matrice quindi pu accadere che match esatti diano meno score S di match non esatti: es. secondo la Blosum62 - il match perfetto AIS-AIS d score 12 - lo score inesatto LSH-MSH d score 14 => il secondo premiato pi del primo^ 2^d8? e%&.%H  0޽h ? ̙33y___PPT10Y+D=' += @B +?0 f^p(    00) p  HPer ricerche in banche dati nucleotidiche, l indicizzazione in w-mers ha poca rilevanza. Inoltre il valore w di default di Blast per i nucleotidi 11, il che lo porta a non riconoscere sequenze che condividano in modo esatto meno di 11 basi, questo un limite grosso. Fasta molto pi tollerante per sequenze che presentano gaps, visto che gi nelle prime fasi prevede il loro inserimento, mentre Blast li inserisce solo in fase di allungamento.  2A  D.  0)   R FASTA pi adatto a ricerche in banche dati nucleotidiche BLAST pi adatto a ricerche in banche dati proteiche Anche se questa regola un po troppo arbitraria...@t 2 25(2H  0޽h ? ̙33y___PPT10Y+D=' += @B +P0 wo(    0,g' 0 7FASTA 2x  6:  ?0 7BLAST 2x  N ?" B0 chttp://www.ebi.ac.uk/fasta33/ 2   N ?" gX  D0 h"http://www.ncbi.nlm.nih.gov/BLAST/# 2## H  0޽h ? ̙33y___PPT10Y+D=' += @B +rL *-,ku١~V18&_R1Oh+'0 `h  Presentazione di PowerPointMatrammrama25Microsoft PowerPoint@eÌ@go@ @'G g  f  y--$xx--'@Times New Roman-. <2 (#Algoritmi EURISTICI di allineamento."SystemX9-@Times New Roman-. f2 ?Sono nati insieme alle banche dati, con lo scopo di permettere .-@Times New Roman-. -2 " una ricerca per similariti.-@Times New Roman-.  2 ">.-@Times New Roman-. ?2 "A%rapida anche se meno accurata contro .-@Times New Roman-. =2 (+$le migliaia di sequenze depositate. .-@Times New Roman-. .2 8 Attualmente i programmi pi.-@Times New Roman-.  2 8F.-@Times New Roman-. 2 8Jutilizzati sono:.-@Times New Roman-. 2 I FASTA.-@Times New Roman-.  2 I":.-@Times New Roman-. 2 I$Lipman.-@Times New Roman-.  2 I6&.-@Times New Roman-. 2 I; Pearson (.-@Times New Roman-. 2 IP1985).-@Times New Roman-. 2 _ BLAST.-@Times New Roman-.  2 _#:.-@Times New Roman-. 2 _%Altshul.-@Times New Roman-. 2 _5(1990).-՜.+,D՜.+,8    Presentazione su schermo Casa Mial Times New Roman Courier New WingdingsSymbolStruttura predefinitaDiapositiva 1Diapositiva 2Diapositiva 3Diapositiva 4Diapositiva 5Diapositiva 6Diapositiva 7Diapositiva 8Diapositiva 9Diapositiva 10Diapositiva 11Diapositiva 12Diapositiva 13Diapositiva 14 Caratteri utilizzatiModello strutturaTitoli diapositiveh 8@ _PID_HLINKSA Dhttp://fasta.bioch.virginia.edu/fasta_www/cgi/search_frm.cgi?pgm=fahttp://www.ncbi.nih.gov/BLAST/http://www.ebi.ac.uk/fasta33/#http://www.ncbi.nlm.nih.gov/BLAST/_mramamrama  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuwxyz{|}Root EntrydO)Current UserSummaryInformation(vPowerPoint Document(DocumentSummaryInformation8~