Analisi comparativa degli algoritmi di compressione spaziale di k-mer sets

Here’s the translation of your text: A well-known problem in bioinformatics is the efficient storage of data obtained from the sequencing phase of a particular genome. In fact, the length of the raw sequence represents a significant obstacle for both storage and processing. An initial phase of compression comes from the use of the well-known k-mers, which are subsequences of length k, decided beforehand, derived from a larger read. The aim of this thesis is to present and compare new techniques that can be used to optimally compress these k-mer sets, in relation to spatial occupation, the computational cost of compression, and the computational cost of using and analyzing the compressed data, considering the goals of the analysis. The research seeks to identify the most suitable algorithm and analyze how performance changes as the k parameter varies within the subsequences.

Un problema noto nell’ambito della bioinformatica consiste nell’efficiente memorizzazione dei dati ottenuti dalla fase di sequenziamento di un particolare genoma, infatti la lunghezza della sequenza grezza rappresenta un importante ostacolo sia alla memorizzazione che all’elaborazione di essa. Una prima fase di compressione deriva dall’utilizzo dei noti k-mers ossia sottosequenze di lunghezza k decisa a priori, derivate da una lettura di dimensione maggiore. L’obiettivo di questa tesi consiste nel presentare e confrontare nuove tecniche utilizzabili per comprimere al meglio codesti k-mer sets, in correlazione all’occupazione spaziale, il costo computazionale di compressione ed il costo computazionale di utilizzo ed analisi del dato compreso in relazione alle finalità su di esso, ricercando l’algoritmo più adatto e analizzando come le prestazioni mutano in funzione della variazione del parametro k all’interno nelle sottosequenze.