Resumo da Aula 3: Grafos de De Bruijn e Composição kdmer

Resumo Aula 3 Grafos de De Bruijn pareado Quanto maior o k menos emaranhado DeBruijn4TAATGCCATGGGATGTT K 4 DeBruijn5TAATGCCATGGGATGTT k 5 Quanto maior o K tamanho da leitura menos repetição Maior leitura precisa com tecnologia atual 300 nucleotídeos k300 é insuficiente para evitar repetição no menor genoma existente Criar uma leitura kmer d kmer onde temse um kmer uma região desconhecida de tamanho d e outro kmer O primeiro kmer é conhecido a região d é desconhecida e o segundo kmer é conhecido Aumentase virtualmente o tamanho da leitura diminuindo a probabilidade de repetições Diminuindo a probabilidade do grafo de De Bruijn gerar emaranhados Solução Virtual dos Biólogos Dada uma cadeia de caractere Text um k dmer é um par de kmers no Text separados pela distância d A notação Padrão1 Padrão2 representa um kdmer Por exemplo ATGGGG é um 34mer pareado de TAATGCCATGGGATGTT A composição kdmer de Text é denotada por ComposicaoPareadakdText Tal composição é a coleção de todos os kd mers de Text incluindo oskdmers repetidos Exemplo ComposicaoPareada31TAATGCCATGGGATGTT TAA GCC AAT CCA ATG CAT TGC ATG GCC TGG CCA GGG CAT GGA ATG GAT TGG ATG GGG TGT GGA GTT Na ordem do dicionário AATCCA ATGCAT ATGGAT CATGGACCAGGG GCCTGG GGAGTT GGGTGT TAAGCC TGCATG TGGATG Solução Virtual Exercício Gere a composição 31mer de TAATGCCATGGGATGTT na ordem do dicionário Include repetições e retorne a composição como uma linha Observe que a composicao31 de TAATGCCATGGGATGTT é diferente da ComposicaoPareada31 TAATGCCATGGGATGTT Embora TAATGCCATGGGATGTT e TAATGGGATGCCATGTT tenham a mesma Composicao 3mer Eles tem diferentes composicoes 31mer Assim podemos diferenciar ambas cadeias resolvendo o problema do múltiplo caminho Euleriano gerado pelo grafo de De Bruijn Podese reconstruir uma cadeia a partir da Composicao kdmer Podese adaptar o grafo de De Bruijn para esse propósito String Reconstruction from ReadPairs Problem Reconstruct a string from its kdmer composition Input A collection of paired kmers PairedReads and an integer d Output A string Text with kdmer composition equal to PairedReads if such a string exists Solução Virtual Dado um kdmer a1 ak b1 bk definimos seus prefixo como k 1 dmer a1 ak 1 b1 bk 1 e o sufixo como k 1dmer a2 ak b2 bk Exemplo PrefixoGAC TCA GA TC and SufixoGAC TCA AC CA Para kdmers consecutivos o sufixo do primeiro é igual ao prefixo do segundo Exemplo Para os k dmers consecutivos TAA GCC e AAT CCA do texto TAATGCCATGGGATGTT SufixoTAA GCC PrefixoAAT CCAAA CC Para kdmers consecutivos o sufixo do primeiro é igual ao prefixo do segundo Exemplo Dado uma cadeia Text constróise o grafo PathGraphkdText que representa um caminho formado por Text k d k 1 arestas correspondentes a todos os k dmers no Text As arestas são nomeadas pelos k dmers e os nós iniciais e finais da aresta pelos prefixo e sufixo respectivamente A Figura 1 mostra o PathGraph31TAATGCCATGGGATGTT Prefixo Sufixo e PathGraph do kdmer Grafo de De Bruijn a partir do PathGraph PathGraph31TAATGCCATGGGATGTT tem 11 arestas e 12 nós Apenas dois nós são iguais TGAT Pergunta Podese construir o grafo de De Bruijn a partir da ComposicaoPareda de um texto Isto é da mesma forma que se pode construir a partir do PathGraph Composição kdmer e Grafo De Bruijn CODE CHALLENGE Solve the String Reconstruction from ReadPairs Problem Input An integer d followed by a collection of paired kmers PairedReads Output A string Text with k dmer composition equal to PairedReads Input ComposicaoPareada42Text Output Text 2 GAGATTGA TCGTGATG CGTGATGT TGGTTGAG GTGATGTT GTGGGTGA TGAGGTTG GGTCGAGA GTCGAGAT GTGGTCGTGAGATGTTGA GTG GTG TGG TGA GTGG GTGA TGG TGA GGT GAG TGGT TGAG GGT GAG GTC AGA GGTC GAGA GTC AGA TCG GAT GTCG AGAT TCG GAT CGT ATG TCGT GATG CGT ATG GTG TGT CGTG ATGT GTG TGT TGA GTT GTGA TGTT TGA GTT GAG TTG TGAG GTTG GAG TTG AGA TGA GAGA TTGA G T G G G T G A T G G T T G A G G G T C G A G A G T C G A G A T T C G T G A T G C G T G A T G T G T G A T G T T T G A G G T T G G A G A T T G A