Algoritmo BLAST

  • Published on
    10-Jul-2015

  • View
    342

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>Algoritmo BLAST</p><p>Aluno: Marllus de Melo Lustosa</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>Sumrio:</p><p>1. Alinhamento de sequncias 1.1. Alinhamento global 1.2. Alinha local 1.3. Global x Local 1.4. Alinhamento timo x heurstico 1.5. Ferramentas de alinhamento2. FASTA vs BLAST3. BLAST 3.1. Funcionamento do algoritmo 3.1.1. Semeadura</p><p>3.1.2. Extenso</p><p>3.1.3. Avaliao</p><p> 3.2. Famlia de programas BLAST-NCBI</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>1. Alinhamento de sequncias</p><p>- Encontrar um grau de similaridade entre sequncias de nucleotdeos ou protenas.- Definir sequncias homlogas;- Definir fragmentos similares entre sequncias;- Determinar caractersticas entre sequncias;</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>1.1. Alinhamento global- Sequncias so alinhadas de ponta a ponta;- Pode incluir grandes pedaos com baixa similaridade;- til para comparar sequncias cujas semelhanas sejam </p><p>esperadas em toda a sua extenso;</p><p>Fig1. Exemplo de alinhamento global entre duas sequncias. [1]</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>1.2. Alinhamento local- So alinhados um ou mais segmentos com alta </p><p>similaridade entre as sequncias;- til quando no se tem nenhum conhecimento sobre a </p><p>semelhana entre as sequncias a comparar;</p><p>Fig2. Exemplo de alinhamento local entre duas sequncias. [2]</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>1.3. Global x LocalGlobal: As sequncias so alinhadas de ponta a ponta;Local: Pedaos das sequncias que so comparados;</p><p>Fig3. Exemplo de alinhamento global e local entre duas sequncias. [3]</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>1.4. Alinhamento timo x heursticoheurstica -- do dicionrio HouaissAcepes substantivo feminino 1 arte de inventar, de fazer descobertas; cincia que tem por objeto a descoberta dos fatos 1.1 Rubrica: histria. ramo da Histria voltado pesquisa de fontes e documentos 1.2 Rubrica: informtica. mtodo de investigao baseado na aproximao progressiva de um dado problema 1.3 Rubrica: pedagogia. mtodo educacional que consiste em fazer descobrir pelo aluno o que se lhe quer ensinar </p><p>- Alinhamento timo: produz o melhor resultado computacionalmente possvel;</p><p>- Alinhamento heurstico: produz um resultado o mais prximo possvel do resultado timo, mas, principalmente, produz um resultado de maneira muito veloz;</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>1.5. Ferramentas de alinhamento</p><p>Tab1. Exemplo de alinhamento global e local entre duas sequncias. [3]</p><p>Programa</p><p>Tipo de Alinhamento</p><p>Preciso do Alinhamento</p><p>Nmero de seqncias a </p><p>serem alinhadas</p><p>BLAST2Sequences</p><p>Local</p><p>Heurstico</p><p>2</p><p>SWAT (Smith-Waterman)</p><p>Local</p><p>timo</p><p>2</p><p>ClustalW</p><p>Global</p><p>Heurstico</p><p>N</p><p>Multalin</p><p>Global</p><p>Heurstico</p><p>N</p><p>Needleman-Wunsch</p><p>Global</p><p>timo</p><p>2</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>2. FASTA vs BLAST</p><p>FASTP</p><p>1985</p><p>BLAST</p><p>1990</p><p>BLAST2</p><p>1997</p><p>- BLAST e FASTA so algoritmos de alinhamento local;- BLAST mais rpido que o FASTA;- BLAST mais preciso que o FASTA;- BLAST mais verstil e mais amplamente utilizado que o </p><p>o FASTA;- Partem da ideia bsica: Um bom alinhamento contm </p><p>subsequncias de identidade absoluta (pequenas palavras de similaridade exata) [5].</p><p>FASTA</p><p>1988</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3. BLAST- Basic Local Alignment Search Tool;- Ferramenta de alinhamento mais utilizada no mundo;- O artigo onde a ferramenta foi publicada o mais citado </p><p>da histria das cincias biolgicas;- um algoritmo de alinhamento simples, heurstico e </p><p>local;- Alinha um sequncia de entrada contra uma base de </p><p>dados desejada;</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3. BLAST</p><p>Tab2. Famlia de programas BLAST. [4 - Adaptada]</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1. Funcionamento do algoritmo- Consiste em 3 etapas heursticas:</p><p>- Semeadura;- Separa a sequncia de busca em palavras;- Identifica onde comea o alinhamento;</p><p>- Extenso;- Extende o alinhamento das sementes;</p><p>- Avaliao;- Determina quais alinhamentos so significantes;</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.1. Semeadura- Dada uma sequncia de entrada, identifique todas as </p><p>sequncias de um tamanho especfico (sementes).</p><p>RGDMCQLVEx:</p><p>RGDGDM</p><p>DMCMCQ</p><p>CQLQLV</p><p>Sequncia de busca</p><p>Sementes originais</p><p>GEM . . . . . .EDM</p><p>KGD . . . . . .TGD</p><p>RCQ . . . . . .ECQ</p><p>DME . . . . . .EMC</p><p>KLV . . . . . .QEV</p><p>CQE . . . . . .RGL</p><p>Sementes adicionais</p><p>No mximouma substituio</p><p>na palavra</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.1. Semeadura- Comparar as sementes adicionais com a semente original </p><p>correspondente, utilizando uma matriz de substituio (recomenda-se a matriz BLOSUM62 [6]).</p><p>KGDQGDRGEEGDHGDNGDRGNAGDMGDRADRSQRGSRNDRSDSGDTGD</p><p>RGD</p><p>================</p><p>14 = 2 + 6 + 6 = (R-K) + (G-G) + (D+D)131312121212121111111111111111</p><p>Valores de avaliao</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.1. Semeadura- Definir um valor mnimo de avaliao na seleo das sementes </p><p>adicionais;- Padro BLAST, em geral, utilizado o valor 12 para palavras de </p><p>tamanho 3;KGDQGDRGEEGDHGDNGDRGNAGDMGDRADRSQRGSRNDRSDSGDTGD</p><p>================</p><p>14131312121212121111111111111111</p><p>Palavras que sero excludas do conjunto das sementes </p><p>vlidas</p><p>Palavras vlidas</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.1. Semeadura- Conjunto de sementes vlidas para a busca no banco de dados:</p><p>KGDQGDRGEEGDHGDNGDRGNAGD</p><p>RGD</p><p>Sementes originais + sementes adicionais</p><p>Semente original </p><p>Sementes adicionais</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.1. Semeadura- Realizar a busca pelas sementes no banco de dados (prioridade </p><p>para sementes originais);</p><p> GDM CQLSementes de busca: Sequncia encontrada no BD: EGDMKCQLW</p><p>Ex:</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.2. Extenso- Extender o alinhamento das sementes;</p><p>RGDM-CQLVSementes de busca: Sequncia encontrada no BD:</p><p> EGDMKCQLW</p><p>Ex:</p><p>- Extende cada semente para a direita e para esquerda, considerando os seguintes critrios [7]:- A pontuao (score) da semente for maior que um valor T;- Possuir outra semente a uma certa distncia mxima entre elas;- O score da extenso com gaps tem pontuao normalizada de </p><p>pelo menos Sg bits;</p><p>- Muitas vezes necessrio adicionar gaps (buracos) para corrigir o alinhamento;- Gaps so vistos pelo BLAST como penalidades;- Quanto menos gaps, melhor o alinhamento;</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.2. Extenso- Extender o alinhamento das sementes;</p><p>RGDM-CQLVSementes de busca: Sequncia encontrada no BD:</p><p> EGDMKCQLW</p><p>Ex:</p><p>- HSPs (High-scoring Segment Pair): So alinhamentos locais que atingem os scores mais altos em uma busca;</p><p>- MSPs (Maximal-scoring Segment Pair): So os maiores HSPs encontrados na busca;</p><p>HSPs</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.3. Avaliao - Score bruto:</p><p>S = soma(matches) soma(mismatches) soma(penalidades de gap)</p><p> - Score normalizado (Bit score):</p><p>S = (S ln K) / ln 2</p><p> - E-value (probabilidade de alinha-</p><p>mentos terem ocorrido ao </p><p>acaso [2]):</p><p>E(S) = Kmne-S</p><p>ou</p><p>E(S) = mn2-S</p><p>m = Tamanho do banco de dadosn = Tamanho da sequncia de entrada = Escala da matriz de scoresK = Escala do tamanho do espao de busca</p><p>Penalidades de gap:</p><p>(gap open + gap extension) Gap open: definido um valorGap extension: definido um valor</p><p>legenda</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>3.1.3. Avaliao</p><p>Matches: 6*1 = 6Mismatches: 2*2 = 4Gap open: 1*5 = 5Gap extension: 1*2 = 2</p><p>RGDM-CQLV EGDMKCQLW</p><p>Sementes de busca: Sequncia encontrada no BD:</p><p>Definir Gap Costs:</p><p>Gap open: 5</p><p>Gap extension: 2</p><p>De acordo com [8], valores de:</p><p>Match/mismatches = 1/-3 =&gt; Sequncias 99% conservadas</p><p>Match/mismatches = 1/-2 =&gt; Sequncias 95% conservadas</p><p>Match/mismatches = 1/-1 =&gt; Sequncias 75% conservadas</p><p>Similaridade: 6/9 (67%) </p><p>S = 6 4 5 -2 = -5</p><p>Resultado parcial</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>- Outro exemplo, adaptado de [2]: Resultado do BLAST</p><p>Valores calculadosna mo</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>Referncias[ 1 ] h t t p : / / w w w . b d t d . u c b . b r / t e d e / t d e _ a r q u i v o s / 1 3 /TDE-2004-11-12T134348Z-143/Publico/Dissert_Felipe%20Liberman.pdf[2] http://minerva.ufpel.edu.br/~lmaia.faem/aula4.pdf[3] http://www.biotecnologia.com.br/revista/bio29/bioinf.pdf[ 4 ] h t t p : / / w w w . b d t d . u c b . b r / t e d e / t d e _ a r q u i v o s / 1 3 /TDE-2004-11-12T134348Z-143/Publico/Dissert_Felipe%20Liberman.pdf[5] http://csb.stanford.edu/class/public/readings/Bioinformatics_I_Lecture6/Altschul_JMB_90_BLAST_Sequence_alignment.pdf[6] Henikoff, S. &amp; Henikoff, J.G. (1992) "Amino acid substitution matrices from protein blocks." Proc. Natl. Acad. Sci. USA 89:10915-10919.[7] http://www.ncbi.nlm.nih.gov/pmc/articles/PMC146917/pdf/253389.pdf[8] http://www.ncbi.nlm.nih.gov/pmc/articles/PMC55814/</p></li><li><p>Marllus Lustosa</p><p>Universidade Federal do Piau UFPIBacharelado em Cincia da ComputaoTpicos em Bioinformtica</p><p>OBRIGADO</p><p>Contatoswww.marllus.com</p><p>marlluslustosa@gmail.com</p></li></ul>