Please enable JavaScript.

Coggle requires JavaScript to display documents.

Montagem do genoma - Coggle Diagram

- - - - Um gráfico de sobreposiçao pode ser usado para representar as sobreposiçoes: sufixo 'a' --> prefixo 'b' + n, sendo n o número de caracteres que se sobrepoem
      - Um numero mínimo de caracteres que se sobrepoem pode ser definido para minimizar que segmentos aleatorios sejam considerados como sobreposiçoes
- - - - Porém demora muito quando aumenta o tamanho do imput (NP-complete
        
        As listas geradas são do tamanho n!. Crescem muito rápido com grandes quantidades de reads
      - Algorítimo SCS
        
        Regras
        
        Pega todos os reads e cria listas com todas as ordens possíveis de reads(permutação)
        
        Para cada read adjacente, compara-se 'a' com 'b' e busca-se a maior sequência de sobreposição (overlap)
        
        Detectado o overlap, caso não esteja presente no final da lista, adiciona-o a lista + a sequência 'b' após o overlap
        
        Ao final gera-se uma superstring canditada.
        
        repete o mesmo processo para diferentes ordens. ao final, uma a menor superstring comum será gerada
  - - - é um multigráfico, mais de uma borda pode conectar um nó ao outro (p.ex duas conexões de 'a' para 'b'
      - Precisa considerar que cada read é uma substring do genoma (k-mer) e só ocorre uma vez
        
        Cada k-mer (read) é dividido em k-1mer:
        
        parte esquerda (tamanho do k-mer -1) e parte direita
        
        Cada divisão vira um nó distinto caso os k-1 mer sejam diferentes.
        
        As setas apontam a direçaõ do k-1mer da direta para o k-1 da esquerda.
        
        o k-mer original será formado pela concatenação do nó da direita + nó da esquerda (pós overlap)
        
        Cada nó permite reconstituir 1 k-mer
        
        1 nó a cada k-1mer (parte esquerda -1, parte direita -1 do k-mer)
        
        Assim cada seta (borda) permite reconstituir 1-kmer, e ao passar 1 vez por cada borda, reconstitui-se o genoma/string original (porém os k-mers gerados nao podem ter a mesma sequencia).
        
        Gráfico que permite construir o genoma passando por uma borda (seta) uma unica vez, permite construir o genoma (Eulerian walks). Nem todos o gráficos são eulerian pois podem ter reads (-kmer) identicos originando de diferentes regioes do genoma.
        
        PERMITE RECONSTITUIR UM GENOMA