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

• Ano de defesa: 2020
• Autor(a) principal: ELVISMARY MOLINA DE ARMAS
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] MONTAGEM DE GENOMAS; [pt] K MER; [pt] GRAFO DE BRUIJN; [en] GENOME ASSEMBLY; [en] K MER; [en] DE BRUIJN GRAPH
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47791&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47791&idi=2; http://doi.org/10.17771/PUCRio.acad.47791

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