Improving Spaced k-mer Extraction and Hash Encoding for Bioinformatics Applications

This thesis focuses on improving the extraction and hash encoding of spaced k-mers for bioinformatics applications. It explores the concept of spaced seeds, which improve similarity detection by allowing nonconsecutive matches within k-mers, albeit at the expense of increased computational complexity. The main goal of this research is to develop advanced software capable of rapid forward and reverse complement hashing for spaced k-mer in nucleotide sequences. This includes optimizing the hashing process to better handle large genomic datasets and minimize processing time and computational resources. The work includes the introduction of the DuoHash tool, an improved version of Multiple Iterative Spaced Seed Hashing (MISSH), and we compare its performance with ntHash2. Results demonstrate how DuoHash performs on different datasets, showing its time efficiency and integrability with tools such as JellyFish. Finally, practical implications and suggestions for future research directions are discussed.

Questa tesi si concentra sul miglioramento dell'estrazione e della codifica hash di k-mers spaziati per applicazioni bioinformatiche. Esplora il concetto di semi spaziati, che migliorano il rilevamento della somiglianza consentendo corrispondenze non consecutive all'interno dei k-mers, anche se a spese di una maggiore complessità computazionale. Lo scopo principale di questa ricerca è sviluppare un software avanzato in grado di eseguire rapidamente l'hashing e l'hashing del complemento inverso per i k-mer spaziati nelle sequenze nucleotidiche. Ciò include l'ottimizzazione del processo di hashing per gestire meglio grandi insiemi di dati genomici e minimizzare il tempo di elaborazione e le risorse computazionali. Il lavoro include l'introduzione dello strumento DuoHash, una versione migliorata di Multiple Iterative Spaced Seed Hashing (MISSH) e ne confrontiamo le prestazioni con ntHash2. I risultati dimostrano come DuoHash si comporta su diversi set di dati, mostrando la sua efficienza in termini di tempo e l'integrabilità con strumenti come JellyFish. Infine, vengono discusse le implicazioni pratiche e i suggerimenti per le future direzioni di ricerca.