Resumo Aula 1 - Reconstrução de Strings e Grafos

Resumo Aula 1 Reconstrução de strings parte 2 Genoma Path Grafo Sobrepostos Overlap graph Caminhos Hamiltonianos O problema da reconstrução de strings parte 2 Repetições no genoma tornam a sua remontagem mais complexa O problema de remontar exige que se veja à frente para que se consiga montar o genoma corretamente existem vários caminhos inviáveis que devem se previstos Genoma path 3mers da sequencia TAATGCCATGGGATGTT na ordem genômica O problema da reconstrução de strings parte 2 Reconstruir o genoma a partir do Genoma path é simples basta ler da esquerda para a direita Formalismo necessário Prefixo primeiros k1 nucleotídeos Exemplo PrefixoTAA TA Sufixo últimos k1 nucleotídeos Exemplo SufixoTAA AA Observe que no Genoma path que o sufixo do anterior prefixo do próximo Sendo assim podese afirmar que Regra 1 Sufixo Padrão Kmer1 Prefixo Padrão Kmer2 Pergunta É possível reconstruir o genoma conhecendose apenas a composição kmer e a Regra 1 O problema da reconstrução de strings parte 2 1 Se aplicarmos a regra 1 o grafo acima é criado 2 Muitos outros pares são conectados 3 Novas conexões ATG conectase a TGC TGG e TGT 4 O novo grafo tem 25 arestas e os 15 nós originais A figura acima representa um grafo ou rede de nós conectados por arestas arcos ou setas O problema da reconstrução de strings parte 2 O genoma original pode ainda ser reconstruído a partir do Genoma path Se construirmos o grafo a partir da CompositionTAATGCCATGGGATGTT O problema da reconstrução de strings parte 2 A figura acima mostra o caminho que se deve seguir para reconstruir o genoma original TAATGCCATGGGATGTT Pergunta Outros genomas podem ser reconstruídos a partir do grafo acima início Overlap Graph Problem Construct the overlap graph of a collection of kmers Input A collection Patterns of kmers Output The overlap graph OverlapPatterns O problema da reconstrução de strings parte 2 Overlap Graph Problem Construct the overlap graph of a collection of kmers Input A collection Patterns of kmers Output The overlap graph OverlapPatterns Exemplo Input A collection Patterns of kmers Output The overlap graph OverlapPatterns in the form of an adjacency list Exemplo de k5 Input AGGCA ATGCG CATGC GCATG GGCAT O problema da reconstrução de strings parte 2 Overlap Graph Problem Construct the overlap graph of a collection of kmers Input A collection Patterns of kmers Output The overlap graph OverlapPatterns Exemplo Input A collection Patterns of kmers Output The overlap graph OverlapPatterns in the form of an adjacency list Exemplo de k5 Input AGGCA ATGCG CATGC GCATG GGCAT Exemplo de k5 Output grafo representado por lista de adjacência AGGCA GGCAT CATGC ATGCG GCATG CATGC GGCAT GCATG O problema da reconstrução de strings Para resolver o problema da remontagem procuramos um caminho no grafo sobreposto overlap graph que visita cada nó exatamente uma vez caminho hamiltoniano Dois caminhos hamiltonianos encontrados TAATGCCATGGGATGTT TAATGGGATGCCATGTT O problema da reconstrução de strings parte 2 Hamiltonian Path Problem Construct a Hamiltonian path in a graph Input A directed graph Output A path visiting every node in the graph exactly once if such a path exists O problema com o algoritmo acima é que ele é NP Completo ou NPC Sendo assim não existe um algoritmo eficiente para resolvêlo Ao invés de procurar um caminho hamiltoniano em um grafo um novo grafo foi desenvolvido por De Bruijn Tal grafo pode representar melhor uma composição kmer