English

CIn - Centro de Informática UFPE




Eventos Relacionados

Defesa de Dissertação de Mestrado Nº1.682: "Representações Cache Eficientes para Montagem de Fragmentos Baseada em Grafos de de Bruijn de Sequências Biológicas"

O aluno Jamerson Filipe Pereira Lima irá defender sua pesquisa no dia 20 de fevereiro às 9h, na sala D218 Início: 20/02/2017 às 09:00 Término: 20/02/2017 às 00:00 Local: Sala D218

Pós-Graduação em Ciência da Computação – UFPE
Defesa de Dissertação de Mestrado Nº  1.682

Aluno: Jamerson Filipe Pereira Lima
Orientador: Prof. Paulo Gustavo Soares da Fonseca
Título: Representações Cache Eficientes para Montagem de Fragmentos Baseada em Grafos de de Bruijn de Sequências Biológicas
Data: 20/02/2017
Hora/Local: 9h – Centro de Informática- Sala D218
Banca Examinadora:
Prof. Katia Silva Guimarães (UFPE / CIn)
Prof. Jeane Cecília Bezerra de Melo (UFRPE / DEINFO)
Prof. Paulo Gustavo Soares da Fonseca (UFPE / CIn)

RESUMO:

O estudo dos genomas dos seres vivos têm sido impulsionado pelos avanços na biotecnologia ocorridos a partir da segunda metade do Séc. XX. Em particular, o desenvolvimento de novas plataformas de sequenciamento de alto desempenho tem ocasionado a proliferação de dados brutos de fragmentos de sequências nucleicas. Todavia, a montagem do DNA, ou seja, a reconstituição da sequência original a partir dos fragmentos continua a ser uma das etapas computacionais mais desafiadoras. 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, novas soluções baseadas nos chamados 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, para o qual soluções polinomiais são conhecidas. Todavia, essas soluções, apesar de apresentarem um custo computacional teórico mais baixo, continuam a demandar, na prática, um consequente 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. Assim sendo, faz-se necessário 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 (latência), ou seja, diminui a velocidade. Portanto, o objetivo é manter a informação limitada o mais possível aos níveis inferiores e diminuir 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 nos últimos anos é o emprego de estruturas de dados ditas sucintas, ou seja, estruturas que usam 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 os 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 a 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 um melhor desempenho em termos relativos, considerando-se a proporção entre o número de cache misses e a quantidade de acessos à memória, o que sugere que um melhor desempenho geral em situações mais extremas de utilização de memória.

Palavras-chave: Grafos de de Bruijn, Algoritmos cache-oblivious, Estruturas de dados sucintas, montagem de fragmentos, tour euleriano
  • © Centro de Informática UFPE - Todos os direitos reservados
    Tel +55 81 2126.8430 - Cidade Universitária - 50740-560 - Recife/PE
Plano4 Consultoria Web