Metodi Logic Based per il tagging e la ricostruzione di SNPs

Gli SNPs sono posizioni nelle sequenze di DNA la cui individuazione risulta di cruciale importanza in quanto esse consentono di evidenziare differenze fra i vari individui. Sfortunatamente, anche nel caso in cui il numero di queste posizioni è basso (circa l’1% dell’intera sequenza), il costo legato all’estrazione dell’intera informazione è molto alto. Al fine di ridurre questo costo, recenti studi hanno evidenziato la possibilità di limitare l’analisi ad un sottoinsieme di SNPs chiamati Tag SNPs i quali contengono la maggior parte dell’informazione contenuta nell’intera sequenza. Per la selezione di Tag SNPs abbiamo progettato ed implementato un algoritmo basato sulla programmazione intera, mentre per la loro ricostruzione abbiamo proposto un metodo basato sul majority vote ed un metodo alternativo di tipo machine learning. I metodi proposti sono stati testati su due differenti dataset pubblici. I risultati ottenuti sono confrontabili con la letteratura ed evidenziano una interessante caratteristica delle nostre proposte algoritmiche: la possibilità di gestire set di SNPs di dimensione notevole ed al contempo esprimere regole di ricostruzione come formule di tipo logico.