• SNP
• BWT
• reference-free
• assembly-free
• prefix-free parsing

La presente tesi illustra una strategia che, senza la necessità di effettuare prima l’operazione di mappatura (reference-free) e di allineamento (assembly-free) con un genoma di riferimento, identifica i polimorfismi a singolo nucleotide (SNP) attraverso le informazioni calcolate dalla procedura di pre-processing denominata Prefix-Free Parsing. In letteratura gli eBWT cluster sono conosciuti come una tecnica di identificazione degli SNP basata sull'idea che i simboli che condividono uno stesso contesto risultano contigui in una sottostringa della extended Burrows-Wheeler Transform (eBWT). Presentiamo due metodi in grado di identificare gli SNP elaborando gli eBWT cluster, uno che sfrutta le informazioni contenute nelle strutture dati del PFP, e l'altro che le ottiene effettuando query efficienti sui dati del PFP.

This thesis illustrates a reference-free and assembly-free strategy that identifies single nucleotide polymorphisms (SNPs) through information calculated by the pre-processing procedure called Prefix-Free Parsing. In the literature, eBWT clusters are known as a SNP identification technique based on the idea that symbols sharing the same context are contiguous in a substring of the extended Burrows-Wheeler Transform (eBWT). We present two methods that can identify SNPs by processing the eBWT clusters, one that exploits the information contained in the PFP data structures, and the other that obtains it by performing efficient queries on the PFP data.