Reconstrução de Genomas: Uma Abordagem em Bioinformática

Reconstrução de Genomas Prof Dr Luiz Cláudio Demes da Mata Sousa Tópicos em BioinformáticaBioinformática Última atualização em 20141 Introdução Explodindo jornais shotgun O problema da reconstrução de strings parte 1 so what did the June 27 2000 NY Times say Explodindo Jornais Shotgun O problema de remontar o jornal é um pouco mais difícil do que parece à primeira vista Existiam várias cópias do jornal e sendo assim não podemos remontálo da mesma forma que faríamos com um simples quebracabeça O que devemos fazer é tentar sobrepor fragmentos de diferentes cópias Explodindo Jornais shotgun A pergunta principal é o que remontar jornais tem a ver com Biologia Tecnologias de leitura de genoma são limitadas Em geral uma única leitura do inicio ao fim do genoma não é possível Sendo assim temos que realizar diversas cópias realizadas em fragmentos que precisam ser remontados assim como os jornais Uma única leitura de um pedaço de DNA com 500 nucleotídeos em 1988 custava mais de um dólar tornando o sequenciamento de mamíferos na casa dos bilhões de dólares Explodindo Jornais Shotgun Uma resposta a esse custo excessivo foi a criação do DNA Array Leituras do tamanho de 10 nucleotídeos Dessa forma geravam uma composição do genoma bem barata DNA Array Gerase todos o 4k possíveis DNA kmers e ligaos ao DNA Array DNA Array é uma matriz onde cada kmer é associado a uma única localização Todos os 64 possíveis 3mers Explodindo Jornais Sequenciamento Tradicional Devemos sobrepor as diversas leituras para remontar o genoma Mesma idéia aplicada ao tentar remontar os jornais O problema da reconstrução de strings Primeiro Considerando que as leituras em uma sequenciadora possuem basicamente o mesmo tamanho podese assumir que as leituras são kmers para algum valor de k Segundo Os algoritmos a serem estudados levarão em consideração um ambiente ideal e hipotético em que todo o gnoma é lido Terceiro Cada substring kmer é gerada a partir de uma única leitura Mundo kmer O problema da reconstrução de strings Problema computacional modelando uma montagem de genoma Dada um determinada string texto sua Composição kmer ou CompositionkTEXTO é a coleção de todas as substrings kmer de TEXTO Por exemplo Composition3TATGGGGTGC TAT ATG TGG GGG GGG GGT GTG TGC Os kmers devem ser listados na ordem lexicográfica dicionário aos invés da ordem em que aparecem na seqüência Sendo assim Composition3TATGGGGTGC ATG GGG GGG GGT GTG TATTGCTGG String Composition Problem Generate the kmer composition of a string Input An integer k and a string text Output CompositionkTEXT com kmers em ordem lexicográfica O problema da reconstrução de strings Para remontar um genoma precisase resolver o problema inverso String Reconstruction Problem Reconstruct a string from kmer composition Input An integer k and a collection Patterns of kmers Output A string TEXT with kmer composition equal to Patterns Antes de trabalhar o problema da reconstrução consideremos o exemplo a seguir AAT ATG GTT TAA TGT A maneira natural de resolver o problema da reconstrução é imitar a solução dada para remontar o jornal Conecte um par de kmer se eles se sobrescrevem em k1 símbolos letras Para o exemplo acima é fácil ver que devemos começar pelo kmer TAA O problema da reconstrução de strings AAT ATG GTT TAA TGT TAA AAT ATG TGT GTT TAATGTT SIMPLES Vamos com calma Exemplo 2 AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT TAA AAT ATG TGT GTT TAATGTT Problema Não há um kmer que inicie com as letras TT A dificuldade em montar essa seqüência reside no fato de haver três kmers ATG Dessa forma teremos três caminhos a seguir TGG TGC e TGT