Stage: Paralellizazione algoritmo di Simulated Annealing per inferenza di progressioni tumorali

Descrizione

Recenti sviluppi riguardanti terapie specializzate per il trattamento di tumorali si basano su una accurata inferenza della progressione della malattia. Riuscire a capire l’ordine e la frequenza con cui le variazione somatiche vengono acquisite durante una progressione tumorale può aiutare a meglio definire strategie specifiche di trattamento della malattia.

Recentemente il laboratorio di ricerca AlgoLab ha sviluppato e proposto un algoritmo di Simulated Annealing in grado di ricostruire la storia evolutiva dei tumori partendo da dati di sequenziamento Single Cell. Tale algoritmo risulta essere molto competitivo ed é in grado di superare alcune delle limitazioni presenti nei metodi attualmente disponibili nella letteratura.

L’obiettivo di questo stage è di migliorare l’algoritmo esistente permettendo una computazione parallela della fase di ricerca ed esplorazione dell’insieme delle possibili soluzioni.

Obiettivi

L’obiettivo principale dello stage è lo studio e l’analisi dei metodi disponibili in letteratura per parallelizare algoritmi di Simulated Annealing.

Lo stage prevede inoltre l’implementazione ed il testing di uno di essi come estensione di un algoritmo già esistente nel contesto di ricostruzione di progressioni tumorali.

Requisiti

  1. Interesse per la definizione ed implementazione di algoritmi.
  2. Conoscenza del linguaggio di programmazione C.

Stage: Ottimizzazione algoritmo di Maximum Likelihood per inferenza di progressioni tumorali

Descrizione

Recenti sviluppi riguardanti terapie specializzate per il trattamento di tumorali si basano su una accurata inferenza della progressione della malattia. Riuscire a capire l’ordine e la frequenza con cui le variazione somatiche vengono acquisite durante una progressione tumorale può aiutare a meglio definire strategie specifiche di trattamento della malattia.

Recentemente il laboratorio di ricerca AlgoLab ha sviluppato e proposto un algoritmo di Simulated Annealing in grado di ricostruire la storia evolutiva dei tumori partendo da dati di sequenziamento Single Cell. Tale algoritmo risulta essere molto competitivo ed é in grado di superare alcune delle limitazioni presenti nei metodi attualmente disponibili nella letteratura.

L’obiettivo di questo stage é di migliorare l’algoritmo esistente utilizzando un algoritmo efficienti ed ottimizzato per il calcolo di una funzione di Maximum Likelihood Estimation.

Obiettivi

L’obiettivo principale dello stage è lo studio e la definizione di un algoritmo che possa rendere più efficiente il calcolo di una funzione di Maximum Likelihood Estimation applicato ad una struttura ad albero.

Lo stage prevede inoltre l’implementazione e il testing di tale metodo come estensione di un algoritmo già esistente nel contesto di ricostruzione di progressioni tumorali.

Requisiti

  1. Interesse per la definizione ed implementazione di algoritmi.
  2. Conoscenza del linguaggio di programmazione C.

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

Tesi: Algoritmi di indicizzazione del grafo del pangenoma

Descrizione

La tesi si occupa di modellare, disegnare e implementare nuovi metodi di pattern matching dove il testo non è più una struttura lineare, ma è rappresentabile da un grafo orientato aciclico dove i vertici corrispondono a porzioni di genoma condivisi da uno o più individui e gli archi identificano le varianti genomiche presenti in ogni persone.

L’ambito fornisce la possibilità di avere più tesi di laurea magistrale, anche coordinate fra loro. Ad esempio:

  1. definire e studiare il problema computazionale quando il pattern a sua volta è un grafo.
  2. implementare un algoritmo di pattern matching con testo che è un grafo
  3. disegnare e implementare un algoritmo di allineamento di un read con un grafo
  4. modellare e disegnare un algoritmo per il caso di genomi con variazioni strutturali

Luogo

Laboratorio di Algoritmica Sperimentale — Algolab — http://www.algolab.eu

Requisiti

Interesse ed entusiasmo per inventare nuovi algoritmi per indicizzare grafi basati su BWT (Burrows-Wheeler transform)

Risultati attesi

Nuovi modelli o algoritmi per l’indicizzazione e interrogazione di dati modellabili come grafi.

Per informazioni contattare

Paola Bonizzoni <bonizzoni@disco.unimib.it> oppure Gianluca Della Vedova <gianluca.dellavedova@unimib.it>

Tempo di realizzazione

6 mesi