Resumo: As melhorias contínuas em tecnologias de sequenciamento de DNA aumentaram a disponibilidade de genomas sequenciados. No entanto, devido às dificuldades para montar completamente um genoma, obtendo uma única cadeia para cada cromossomo, muitos genomas têm montagens incompletas (draft), em que cada cromossomo é representado por um conjunto de cadeias com informação parcial sobre a ordem relativa entre elas. Abordagens livres de alinhamento foram propostas recentemente para construir filogenias a partir da comparação de montagens draft de genomas, extraindo caminhos em grafos de de Bruijn. Neste trabalho investigamos métodos eficientes para comparar genomas incompletos por meio da comparação direta de grafos de de Bruijn coloridos representados de maneira sucinta usando a representação BOSS utilizando medidas baseadas na distribuição de similaridade de Burrows-Wheeler (BWSD). Nós propomos o algoritmo gcBB, este recebe um conjunto de genomas (em que cada genoma é representado por um conjunto de fragmentos) e sua saída são duas matrizes de distância derivadas da BWSD. Nós realizamos experimentos com conjuntos de genomas de Drosophilas e Vibrios, comparando as filogenias obtidas pelo gcBB com filogenias de referência Ver menos

Abstract: The continuous improvements in DNA sequencing technologies have increased the volume of available genomic data. Nevertheless, due to the difficulties in assembling a complete genome, obtaining a single sequence for each chromosome, many genomes are still incomplete (draft), in which each chromosome is represented as a set of sequences with partial information on their relative order. Recent alignment-free approaches have been proposed to construct phylogenies from the comparison between draft genomes, extracting paths from a de Bruijn graph. In this work we investigated efficient methods for directly comparing the succinct BOSS representation of colored de Bruijn graphs through measures based on the Burrows-Wheeler similarity distribution (BWSD). We propose the gcBB algorithm that takes a set of genomes (where each genome is a set of reads) and outputs matrices of distances derived from the BWSD. We performed experiments with sets of Drosophila and Vibrio genomes, comparing phylogenies obtained with gcBB to reference phylogenies Ver menos