Reuniões

30/03/2022 (A+P)

Validação dos resultados prova de conceito -> Implementar a navegação em C++
Discussão sobre a narrativa do artigo
- Sketch CountMin funciona como um filtro mas, sendo navegável, pode ser utilizado diretamente
- Uma vez que as leituras acabam, o modelo HashTable pode ser utilizado para reduzir o tamanho do sketch
  - A HashTable é construída a partir da navegação no sketch, sendo adicionados os vértices que são encontrados
Continuar guardando todos os k-mers iniciais, e deixar para pensar em uma forma diferente de definir os k-mers iniciais da navegação quando isso se mostrar um problema
Usar o genoma da E. Coli [7] para o teste
- Primeiro simulando as leituras sem erro
- Depois usando um dataset de leituras reais do SRA [8]

Resultados da utilização da multiplicação e soma modular (o problema persistiu)
- Tentar ainda: a troca do tamanho da tabela para que não seja uma potência de 2, e exploração de outras possíveis fontes para o problema.

Conversa sobre resultados do hashing para o modelo CountMin (quantidade muito pequena de posições ocupadas em cada linha, resultando em muitas colisões)
- Possíveis soluções: Atualizar a função de hashing para usar multiplicação e soma modular, utilizar um W que não seja potência de 2
Investigação quanto as formas de definir um ponto de partida para a exploração
- Exploração do código fonte do Minia buscando como foi feito ali

Conversa sobre resultados da Hash Table e função de hash para o modelo CountMin + Filtro de Bloom
Planejamento para começo da escrita da monografia (começando pelos experimentos uma vez que as implementações dos dois modelos estejam finalizadas)
Conversa sobre possíveis próximos passos depois da avaliação desses dois modelos: apresenta-los comparativamente, e depois propor uma alternativa "meio-termo" fazendo uso dos dois
Usar o UFPEThesis como modelo e o professor compartilhou o documento de orientações gerais

Discussão sobre implementação da Hash Table usando Fibonacci hashing, avaliando quantidade de falsos positivos e colisões de hash e fingerprint simultâneas.
- Taxa de FP foi por volta de 10% para um alfa = 0.5, e tem relação linear com alfa.
- Fibonacci hashing oferece uma distribuição muito boa tanto de hash quanto de fingerprints
Discussão sobre o processo de estimativa do número de k-mers (e, consequentemente, do tamanho necessário da Hash Table) baseado num conjunto inicial de reads, dado o tamanho total da sequência, e a cobertura das leituras.
Estudar e implementar o modelo CountMin + filtros de Bloom
- Usar o CountMin de forma semelhante a [4] para fazer a contagem dos diferentes k-mers, considerando um k-mer presente quando essa contagem for superior a um determinado threshold (ex.: a cobertura). Guardar, junto com o count, 4 bits com as out edges num esquema semelhante ao filtro de Bloom (as arestas são marcadas em todos os buckets associados com o dado k-mer, e as arestas de um k-mer são encontradas fazendo um & entre esses bits de todos os buckets). Uma possibilidade sendo que essa informação de arestas só é adicionada uma vez que a contagem ultrapassa o threshold definido.
Concluir a proposta do TG (deadline 28/02/2022):
- Título
- Resumo (máx. 10 linhas)
- Possíveis Avaliadores
- Cronograma
- Assinaturas

Discussão sobre referência [4]
Explicação da modelo proposto usando uma hashtable
- Começar implementação da hashtable usando Fibonacci Hashing [6]
Estudar um modelo CountMin + Filtro de Bloom