[pt] A montagem de fragmentos de sequências biológicas é um problema fundamental na bioinformática. Na montagem de tipo De Novo, onde não existe um genoma de referência, é usada a estrutura de dados do grafo de Bruijn para auxiliar com o processamento computacional. Em particular, é necessário considerar um conjunto grande de k-mers, substrings das sequências biológicas. No entanto, a construção deste grafo tem grande custo computacional, especialmente muito consumo de memoria principal, tornando-se inviável no caso da montagem de grandes conjuntos de k-mers. Há soluções na literatura que utilizam o modelo de memória externa para conseguir executar o procedimento. Porém, todas envolvem alta redundância nos cálculos envolvendo os k-mers, aumentando consideravelmente o número de operações de E/S. Esta tese propõe uma nova abordagem para a construção do grafo de Bruijn que torna desnecessária a geração de todos os k-mer. A solução permite uma redução dos requisitos computacionais e a viabilidade da execução, o que é confirmado com os resultados experimentais. / [en] Fragment assembly is a current fundamental problem in bioinformatics. In the absence of a reference genome sequence that could guide the whole process, a de Bruijn Graph data structure has been considered to improve the computational processing. Notably, we need to count on a broad set of k-mers, biological sequences substrings. However, the construction of de Bruijn Graphs has a high computational cost, primarily due to main memory consumption. Some approaches use external memory processing to achieve feasibility. These solutions generate all k-mers with high redundancy, increasing the number of managed data and, consequently, the number of I/O operations. This thesis proposes a new approach for de Bruijn Graph construction that does not need to generate all k-mers. The solution enables to reduce computational requirements and execution feasibility, which is confirmed with the experimental results.

[pt] A área de pesquisa em Montagem de Genomas tem evoluído rapidamente, adaptando-se às novas tecnologias de sequenciamento e modernos ambientes computacionais. Existem diversos softwares montadores que usam múltiplas abordagens, porém persiste o questionamento sobre a qualidade da montagem ao final do processo. Assim que uma montagem é finalizada, muitas medidas de qualidade podem ser geradas, a fim de que a montagem seja qualificada. Todavia, essas medidas apenas fornecem aos biólogos valores quantitativos acerca da montagem. Nós propomos nesta pesquisa um framework de domínio para o processo de análise de medidas pós montagem de genomas. Nosso objetivo é de prover a interpretação dos dados e avaliação da qualidade das montagens a partir do Framework. O Genome Assembly Analysis Framework (GAAF) foi projetado para trabalhar com espécies, montadores e medidas distintas. Para validar nossa proposta, foram realizados testes com o GAAF que permitem entender como o mesmo pode ser utilizado e de que maneira ele pode ser instanciado e/ou estendido. / [en] The Genome Assembly research area has quickly evolved, adapting to new sequencing technologies and modern computational environments. There exist many assembler software that consider multiple approaches. However, at the end of the process, one can always question the quality of assemblies. When an assembly is accomplished, some quality features may be generated, in order to qualify it. Nonetheless, the features do not directly tell one about assembly quality, but only bring to the biologists quantitative assembly descriptions. We propose a Domain Framework for the feature analysis process post-genome Assembly. Our goal is to enable data interpretation and assembly quality evaluation. The Genome Assembly Analysis Framework (GAAF) was designed to work with distinct species, assemblers and features. In order to validate our proposal, we have run a few practical experiments with GAAF, which make us understand the way it can be used, instantiated and extended.