Descrizione
Le recenti tecnologie di sequenziamento sono in grado di produrre un’ampia quantità di piccoli frammenti di DNA. Tuttavia, la complessità del genoma, tra cui le enormi dimensioni e le diffuse variazioni, rende necessario il disegno di algoritmi avanzati per l’assemblaggio dei frammenti finalizzato alla sua ricostruzione (necessaria per le importanti applicazioni in campo medico). Inoltre, il genoma umano è composto da due filamenti di DNA per ogni cromosoma, uno paterno ed uno materno. Questo implica che i frammenti devono essere partizionati in due insiemi per ricostruire contemporaneamente il DNA paterno e quello materno. L’utilizzo di genomi di riferimento permettono di conoscere la posizione relativa dei frammenti e di rappresentarli come stringhe binarie, tuttavia, la presenza di errori rende il problema difficile a livello computazionale. Recentemente, alcune soluzioni, come ad esempio HapCol (Pirola et al., Bioinformatics, 2016), si sono rivelate in grado di ottenere risultati ad alta accuratezza sfruttando le caratteristiche delle nuove tecnologie di sequenziamento. Sfortunatamente, questi metodi non possono essere applicati per risolvere lo stesso problema quando il genoma è composto da più di due stringhe di DNA, come nel caso dei genomi di piante, animali, e nel caso di tumori.
La proposta di tesi è quella di disegnare avanzate soluzioni algoritmiche (partendo da soluzioni già proposte, come HapCol) per l’assemblaggio di più stringhe di DNA.
Il progetto prevede:
- la formulazione di una nuova variante del problema che sia motivata dalle caratteristiche del contesto (ed eventuale studio della relativa complessità computazionale).
- Il disegno di un algoritmo per la risoluzione esatta del problema.
- Implementazione di un prototipo dell’algoritmo e sua sperimentazione su dati simulati/reali, con eventuale confronto con i metodi attualmente proposti (questo punto non è necessario e può essere, eventualmente, una continuazione del lavoro di tesi)
Luogo
Laboratorio di Algoritmica Sperimentale — Algolab — http://www.algolab.eu
Requisiti
- Interesse per il disegno di algoritmi applicati.
- Conoscenza di base di complessità computazionale e teoria degli algoritmi.
Risultati attesi
La proposta di tesi è indirizzata a studenti interessati alla ricerca nell’ambito dell’algoritmica applicata. I risultati attesti includono: proposta di una nuova formulazione per il problema della ricostruzione di più stringhe di DNA, disegno di un algoritmo per la sua risoluzione ed, eventuale, implementazione/sperimentazione.
Per informazioni contattare
Paola Bonizzoni <bonizzoni@disco.unimib.it>
oppure Simone Zaccaria <simone.zaccaria@disco.unimib.it>
Tempo di realizzazione
4-6 mesi