Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorítimos de alinhamento, Correspondência aproximada, Preprocessamento,…

- - - - Porém, caso seja detectado que algum caractere do padrão seja diferente do texto, o loop para e pula para o próximo alinhamento
      - Caso todos os caracteres sejam iguais, o alinhamento em que isso ocorreu é registrado na variável ocorrências.
- - - - Se, durante a comparação de caractere, houver uma não-correspondência entre P e T. Pula alinhamentos até:
        
        1) A não-corresponência do texto se tornar uma correspondência com o padrão
        
        2) O padrão P passar completamente pelo caractere não correspondente do texto
        
        Quando o P é deslocado em x posições, o número de alinhamentos pulados é x-1. p.ex se P for descolado em 3 posições, o algorítimo pulou 2 alinhamentos
    - - 1) Caso haja uma substring do texto correspondente ao padrão
        2) Caso haja uma não correspondência à esquerda da substring
        
        Pular alinhamentos até:
        
        1) Que um segmento do padrão seja totalmente correspondente a substring, sem formar novos mismatches
        
        O deslocamento que permite o maior número de correspondências entre a substring do texto e o padrão é o que tem prioridade
        
        2) P passar pela substring
- - - - Se P ocorre no texto com até k edições, se P for dividido em P/k + 1, ao menos uma partição não terá edições e haverá correspondência com o texto.
      - Assim, qualquer algorítimo de correspondência exata pode ser adaptado para detectar uma correspondência no texto
        
        O padrão é divido em padrão, alinhado com o genoma de referência com algorítimo de correspondencia exata, onde houver uma ocorrência faz uma verificação para saber se as outras partições também terão corresponências, respeitado o número máximo de edições.
- - - - O resultado será o menor valor encontrado na ultima linha
- - - - Buscador da web p.ex.
      - Alinhamento de DNA pois os padrões mudam a cada sequenciamento, porém, as referências são estáveis, e podem ser preprocessadas para maior rapidez de busca
  - - - Por exemplo, o NEM e o Boyer-Moore.
  - - - Uma das formas de fazer isso é por meio de um índice
        
        Lista de itens e sua localização
        
        Para o genoma podemos dividí-lo em substrings de um determinado comprimento e listar as substrings, associando a posição onde ocorre no genoma
        
        A mesma substring pode ocorrer em mais de um local
        
        k-mer é uma substring do genoma de tamanho k
        
        5-mer (substring de tamanho 5)
        3-mer (substring de tamanho 3)
        
        índice k-mer : Indice composto por vários k-mer e suas posições de ocorrências
        
        USO: Supondo um padrão de tamanho 6 e um índice 5-mer.
        O primeiro 5-mer do padrão é comparado com os 5-mer do texto e uma posição pode ser encontrada.
        O trabalho adicional é saber se o sexto elemento do padrão também corresponde a base que vem depois do 5-mer no genoma, isso é chamado de "verificação"
        
        Acerto de índice Posições em que o k-mer de P corresponde exatamente ao k-mer de T. Necessário investigar se resultará em match (verificação).
        
        É um multimapa (possui chaves [os k-mer] e valores [posições onde o k-mer ocorre no genoma, pode ser mais de 1]
        
        2 more items...
        
        navegação por busca binária: O k-mer de P é comparado ao k-mer do índice que está no meio da lista. Se a ordem alfabética do k-mer de P for posterior a do meio do k-mer do índice, a primeira metade de k-mer é ignorada e apenas a segunda é considerada..
        
        2 more items...
        
        Implementação do k-mer (preprocessamento de T
        
        4 more items...
        
        Há variações de índices k-mer
        
        2 more items...
- - - - Requisitos
        
        Precisa levar em consideração uma distância de hamming = 2.
        
        Ou seja,a comparação de caractere deve persistir até que um limite de mismatch seja alcançado, quando isso ocorrer, pula para o próximo alinhamento
- - - - Algorítimo de índice é um deles
        
        Encontra correspondências de substrings entre P e T
        
        Busca binária pode ser usada para detectar onde o k-mer do padrão é igual ao k-mer do texto (bissectseft)
        
        Verifica caracteres adjacentes a substring são corespondentes (verificação)