Implementazione e analisi di uno hierarchical overlap graph

L'avanzamento delle tecnologie nel campo del sequenziamento del materiale genetico ha reso possibile un accesso sempre più economico a tali risorse. Di conseguenza, la mole di materiale sequenziato e di dati da analizzare, è in costante aumento. Ciò ha posto la necessità di sviluppare algoritmi e strutture dati efficienti per elaborare in modo ottimale questo crescente volume di informazioni. In particolare, tutte le moderne tecniche di sequenziamento richiedono successivamente una fase cruciale detta "assemblaggio", in cui le cosiddette "read" (brevi frammenti di materiale sequenziato) devono essere elaborate al fine di ricostruire la sequenza completa del materiale genetico di partenza. Attualmente, esistono diverse metodologie per effettuare questo processo di assemblaggio, ma le due più utilizzate si basano su due tipi di grafi: i "De Bruijn Graph" e gli "Overlap Graph". Recentemente, in letteratura è stata presentata una nuova struttura dati chiamata "Hierarchical Overlap Graph" che offre un significativo miglioramento in termini di efficienza rispetto ad esse. L'obiettivo principale di questa tesi è l’implementazione di questa nuova struttura, nonché la conduzione di analisi sperimentali mirate a verificarne l'efficienza.