Representações cache eficientes para montagem de fragmentos baseada em grafos de de Bruijn de sequências biológicas

• Ano de defesa: 2017
• Autor(a) principal: LIMA, Jamerson Felipe Pereira
• Orientador(a): FONSECA, Paulo Gustavo Soares da
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Pernambuco
• Programa de Pós-Graduação: Programa de Pos Graduacao em Ciencia da Computacao
• País: Brasil
• Palavras-chave em Português: Ciência da computação; Biologia computacional
• Link de acesso: https://repositorio.ufpe.br/handle/123456789/25352

O estudo dos genomas dos seres vivos têm sido impulsionado pelos avanços na biotecnologia ocorridos desde a segunda metade do Séc. XX. Particularmente, o desenvolvimento de novas plataformas de sequenciamento de alto desempenho ocasionou a proliferação de dados brutos de fragmentos de sequências nucleicas. Todavia, a montagem dos fragmentos de DNA continua a ser uma das etapas computacionais mais desafiadoras, visto que a abordagem tradicional desse problema envolve a solução de problemas intratáveis sobre grafos obtidos a partir dos fragmentos, como, por exemplo, a determinação de caminhos hamiltonianos. Mais recentemente, soluções baseadas nos grafos de de Bruijn (gdB), também obtidos a partir dos fragmentos sequenciados, têm sido adotadas. Nesse caso, o problema da montagem relaciona-se com o de encontrar caminhos eulerianos, o qual possui soluções polinomiais conhecidas. Embora apresentem custo computacional teórico mais baixo, ainda demandam, na prática, grande poder computacional, face ao volume de dados envolvido. Por exemplo, a representação empregada por algumas ferramentas para o gdB do genoma humano pode alcançar centenas de gigabytes. Faz-se necessário, portanto, o emprego de técnicas algorítmicas para manipulação eficiente de dados em memória interna e externa. Nas arquiteturas computacionais modernas, a memória é organizada de forma hierárquica em camadas: cache, memória RAM, disco, rede, etc. À medida que o nível aumenta, cresce a capacidade de armazenagem, porém também o tempo de acesso. O ideal, portanto, seria manter a informação limitada o mais possível aos níveis inferiores, diminuindo a troca de dados entre níveis adjacentes. Para tal, uma das abordagens são os chamados algoritmos cache-oblivious, que têm por objetivo reduzir o número de trocas de dados entre a memória cache e a memória principal sem que seja necessário para tanto introduzir parâmetros relativos à configuração da memória ou instruções para a movimentação explícita de blocos de memória. Uma outra alternativa que vêm ganhando ímpeto mais recentemente é o emprego de estruturas de dados ditas sucintas, ou seja, estruturas que representam a informação usando uma quantidade ótima de bits do ponto de vista da teoria da informação. Neste trabalho, foram implementadas três representações para os gdB, com objetivo de avaliar seus desempenhos em termos da utilização eficiente da memória cache. A primeira corresponde a uma implementação tradicional com listas de adjacências, usada como referência, a segunda é baseada em estruturas de dados cache-oblivious, originalmente descritas para percursos em grafos genéricos, e a terceira corresponde a uma representação sucinta específica para os gdB, com otimizações voltadas ao melhor uso da cache. O comportamento dessas representações foi avaliado quanto à quantidade de acessos à memória em dois algoritmos, nomeadamente o percurso em profundidade (DFS) e o tour euleriano. Os resultados experimentais indicam que as versões tradicional e cache-oblivious genérica apresentam, nessa ordem, os menores números absolutos de cache misses e menores tempos de execução para dados pouco volumosos. Entretanto, a versão sucinta apresenta melhor desempenho em termos relativos, considerando-se a proporção entre o número de cache misses e a quantidade de acessos à memória, sugerindo melhor desempenho geral em situações extremas de utilização de memória.