[en] A NOVEL APPROACH FOR DE BRUIJN GRAPH CONSTRUCTION IN DE NOVO GENOME FRAGMENT ASSEMBLY

[pt] UMA NOVA ABORDAGEM PARA A CONSTRUÇÃO DO GRAFO DE BRUIJN NA MONTAGEM DE NOVO DE FRAGMENTOS DE GENOMA

[pt] ELVISMARY MOLINA DE ARMAS

[pt] MONTAGEM DE GENOMAS

[pt] K MER

[pt] GRAFO DE BRUIJN

[en] GENOME ASSEMBLY

[en] K MER

[en] DE BRUIJN GRAPH

[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.

SERGIO LIFSCHITZ

MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO

SERGIO LIFSCHITZ

EDWARD HERMANN HAEUSLER

NALVO FRANCO DE ALMEIDA JUNIOR

DANIEL CARDOSO MORAES DE OLIVEIRA

2020-05-04

2019-09-23

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47791@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47791@2

https://doi.org/10.17771/PUCRio.acad.47791