Tesi: Algoritmi per l’assemblaggio di multiple stringhe di DNA

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:

  1. la formulazione di una nuova variante del problema che sia motivata dalle caratteristiche del contesto (ed eventuale studio della relativa complessità computazionale).

  2. Il disegno di un algoritmo per la risoluzione esatta del problema.

  3. 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

  1. Interesse per il disegno di algoritmi applicati.

  2. 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

Tesi: Euristiche applicate all’assemblaggio di aplotipi

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:

  1. 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.

  2. Disegno di nuovi algoritmi euristici basati su strutture a grafo.

  3. 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

  1. Interesse per il disegno di algoritmi applicati.

  2. 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