Estruturas de dados para grafos de De Bruijn

Felipe Lambach Cardoso; André Yoshiaki Kashiwabara

doi:10.20906/CPS/SICITE2015-0188

Resumo

Este trabalho tem como objetivo central estudar estruturas de dados que são utilizados para a montagem do genoma de modo eficiente, utilizando a teoria de Grafos de De Bruijn. Neste trabalho, foram comparadas estruturas de dados existentes que utilizam grafos de de Bruijn e verificou-se vantagens, desvantagens, considerando também a dificuldade de implementação de cada estrutura proposta. Durante o trabalho foram estudadas estruturas de dados eficientes, entre elas está a Succicint de De Bruijin proposta pelo pesquisador Alex Bowe. Segundo a teoria de Bowe, é possível representar a montagem do genoma humano utilizando apenas 2,5 Gb de memória. Esta estrutura armazena três vetores que são construídos em cima da ordenação dos k-mer. Também existem alguns métodos que possuem alto grau de complexidade que auxiliam na busca de informações da estrutura. Entre estes métodos os mais importantes são o Rank e Select, que auxiliam na construção dos outros métodos existentes. Analisando o código fornecido pelo autor ficou constatado na prática que esta representação não consegue executar a construção de grandes sequências por conta da implementação dos métodos, que não foram implementados de maneira eficiente. Ainda não existe um algoritmo que consiga realizar a construção da estrutura da teoria proposta por Alex Bowe. Por fim os algoritmos indicados para representar a montagem de genomas utilizando a teoria de Grafos de De Bruijn são o Minia (Bloom Filter) que utiliza cerca de 5,8 Gb para representar o genoma humano, descrito pelos autores Rayan Chikhi e Gulliaume Rizk, e a estrutura do Kfm-Index, retratado por Einar Andreas Rødland.

Palavras-chave: NGS; Grafos de De Bruijn; Sequenciamento; Genoma