Resumo da Aula sobre Grafos de De Bruijn e Teorema de Euler

Resumo Aula 2 Grafos de De Bruijn Teorema de Euler Do Teorema de Euler para um Algoritmo Grafos de De Bruijn Seja a representação do genoma TAATGCCATGGGATGTT como uma seqüência de suas 3mers TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT Ao invés de colocar os 3mers nos nós coloquemos nas arestas Acrescentemos os prefixos e sufixos nos vértices ie 16 nós como 2mers O novo grafo gerado pela função PathGraphkTAATGCCATGGGATGTT Grafos de De Bruijn Aparentemente nada de novo Agora juntemos os nós idênticos AT Agora juntemos os nós idênticos TG Temos um grafo com 12 nós Grafos de De Bruijn De Bruijn Graph from a String Problem Construct the de Bruijn graph of a string Input PathGraphkText Where k is an integer and Text is a string Output DeBruijnkPathGraphkText O DeBruijnkText é o PathGraphkText onde os nós idênticos são colados ou juntados Pergunta Se tivermos o grafo DeBruijnkText sem fornecer o Text seria possível reconstruir Text Grafos de De Bruijn representação como matriz de adjacência Figura 1 DeBruijn3TAATGCCATGGGATGTT Grafos de De Bruijn Caminhada Resolver o problema de reconstruir a string utilizando um Grafo de DeBruijn consiste em caminhar o grafo de forma a visitar cada aresta ou arco apenas uma vez Caminho Euleriano TAATGCCATGGGATGTT Figura 2 DeBruijn3TAATGCCATGGGATGTT Grafos de De Bruijn Eulerian Path Problem Construct an Eulerian path in graph Input A directed graph Output A path visiting every edge in the graph exactly once if it exists Pergunta Podese construir o grafo DeBruijnkText sem saber qual Texto que o gerou mas sabendose a composição kmer A Figura 3 abaixo representa o grafo da composição 3mer da string TAATGCCATGGGATGTT Figura 3 Resultado de CompositionGraph3TAATGCCATGGGATGTT Grafos de De Bruijn Cole os vértices idênticos de CompositionGraph3TAATGCCATGGGATGTT Como o grafo resultante pode ser comparado ao grafo DeBruijn3TAATGCCATGGGATGTT Grafos de De Bruijn Grafos de De Bruijn DeBRUIJNPatterns represent every kmer in Patterns as an isolated edge between its prefix and suffix glue all nodes with identical labels yielding the graph DeBruijnPatterns return DeBruijnPatterns Formalmente Para uma string Text qualquer CompositionGraphkText é o grafo que consiste de Text k 1 arcos isolados Cada arco é nomeado por um kmer de Text Cada arco nomeado por um kmer conecta dois nós O primeiro nó é nomeado pelo prefixo e o segundo nó pelo sufixo do kmer CompositionGraph3TAATGCCATGGGATGTT 17 3 1 15 arcos isolados Teorema de Euler A Figura 4 abaixo apresenta dois grados um desbalanceado a direita e um balanceado a esquerda Um grafo é balanceado quando todos os vértices possuem grau de entrada igual ao grau de saída Figura 4 Grafo balanceado a esquerda e desbalanceado a direita O Teorema de Euler estabelece que um grafo é euleriano se é balanceado ou se o vértice de partida tem grau de saída impar e o vértice de chegada tem grau de entrada ímpar Teorema de Euler A Figura 5 abaixo mostra que um grafo desbalanceado e desconexo não atende ao Teorema de Euler Sendo assim nem todo grafo balanceado é também Euleriano Figura 5 Grafo balanceado e desconexo Teorema de Euler Um grafo G conexo possui caminho euleriano se e somente se ele é balanceado ou tem exatamente dois vértices de grau ímpar Encontrando um Caminho Euleriano A Saga de Léo a formiga andarilha A formiga Léo começa sua caminhada no vértice verde Se Léo fosse um gênio ou extremamente sortudo ele atravessaria cada arco ou aresta apenas uma vez No entanto experiências com formiga tem mostrado que geralmente elas ficam presas antes de encontrarem o caminho euleriano Pergunta Em que nós Léo poderia ficar preso Isto é não teria uma aresta que não tenha andado para poder sair Encontrando um Caminho Euleriano A Saga de Léo a formiga andarilha Tentativa 1 Tentativa 2 Tentativa 3 Do Teorema para um Algoritmo Tentativa 3 EulerianCycleGrafo gere um caminho Ciclo visitando arestas randomicamente no Grafo Enquanto existir arestas não visitadas no Grafo faça 1 selecione um novo nó inicial em Ciclo que ainda tenha arestas não visitadas 2 gere um novo caminho Ciclo1 atravessando Ciclo iniciando em novo nó inicial e então gere randomicamente uma nova travessia Ciclo Ciclo1 retorne Ciclo Figura 5 Transformando um Caminho Euleriano em um Ciclo Euleriano Basta adicionar uma aresta entre o último nós e o primeiro Ciclo Euleriano a partir de um Caminho Euleriano