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, chiamati aplotipi, per ogni cromosoma, uno paterno ed uno materno. Questo implica che i frammenti devono essere partizionati in due insiemi per ricostruire contemporaneamente l’aplotipo 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 (derivanti dal sequenziamento) rende il problema difficile a livello computazionale. Nonostante ciò, 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 continuano a soffrire di problemi di performance quando grandi dataset di frammenti vengono considerati. Tuttavia, alti valori di coverage (il numero medio di frammenti che coprono una posizione) sono essenziali per poter ottenere un’accuratezza nei risultati che sia ritenuta sufficiente per identificare le mutazioni genomiche e correlarle con i corrispondenti effetti sulle cellule di un individuo.
La proposta di tesi è quella di disegnare avanzate soluzioni euristiche per l’assemblaggio di aplotipi che sacrifichino l’ottimalità della soluzione in cambio della capacità di considerare larghi dataset ed ottenere una buona accuratezza.
Il progetto prevede:
- Analisi del contesto dell’applicazione alla ricerca di motivate assunzioni più restrittive per trovare nel problema strutture combinatorie più forti che possano essere sfruttate da un algoritmo euristico.
- Disegno di nuovi algoritmi euristici basati su strutture a grafo.
- Implementazione di un prototipo dell’algoritmo e sua sperimentazione su dati simulati/reali, con confronto con i metodi attualmente proposti
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
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