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

Stage Interno: Diff da Allineamento

Descrizione

Uno degli strumenti principali per il controllo di versione è diff, che permette di calcolare e visualizzare le modifiche fra due file. Diff deve riuscire a mostrare un insieme minimale di modifiche da apportare al primo file per ottenere il secondo file.

La strategia principale è basata sul problema del calcolo della sottosequenza comune più lunga, ma più recentemente sono state introdotto altre strategie più precise (sebbene con tempi di calcolo più elevati), quali patience diff e histogram diff.

La proposta di stage si prefigge di utilizzare algoritmi noti di allineamento di sequenze, inizialmente introdotti in Bioinformatica, per realizzare una nuova implementazione di diff che riesca a migliorare ulteriormente i risultati ottenuti da patience diff.

Luogo

DISCo

Requisiti

Conoscenza basilare di C. Conoscenza di git.

Competenze acquisibili

Capacità di progettare e realizzare una implementazione di un algoritmo

Capacità di collaborare in un progetto open source con gruppo di sviluppatori internazionali

Risultati attesi

Implementazione di un nuovo diff da incorporare in LibXDiff (https://github.com/git/git/tree/master/xdiff)

Per informazioni contattare

Gianluca Della Vedova <gianluca.dellavedova@unimib.it>

Tempo di realizzazione

3 mesi

Stage Esterno: Gestione di configurazioni Docker

Descrizione

All’interno dell’Istituto Nazionale di Genetica Molecolare (INGM), il laboratorio di Ricerca e Sviluppo di Bioinformatica, facente capo al programma “Integrative Biology”, ha l’obiettivo di sperimentare e sviluppare nuovi approcci alle analisi bioinformatiche, in particolare quelle relative al trattamento dei dati di Next Generation Sequencing (NGS). Una volta che i metodi e le procedure di analisi escono dalla fase sperimetale, queste devono essere consolidate e trasferite agli altri bioinformatici e/o analisisti presenti nel centro. Tali procedure potranno subire un utleriore raffinamento entrando poi a pieno titolo tra gli strumenti

utlizzabili da i ricercatori di INGM. Per far ciò è fondamentale che le installazioni dei software siano tracciate, gli ambineti di sviluppo e di analisi siano portabili e che le analisi bioinformatiche siano riproducibili. L’utilizzo dei sistemi di virtualizzaione (Proxmox/KVM) e di software deployment (Chef/Puppet) sono stati ampiamente esplorati e sono attualmente utilizzati con successo dal dipartimento Information Technology (IT) di INGM . Tali sistemi risultano però non sufficientemente flessibili e dinamici per le necessità di di frontiera per la ricerca. Di recente è stato introdotto nel mondo della virtualizzazione Docker, che riesce a combinare i vantaggi di un sistema di deployment portabile e riproducibile con la versatilità della virtualizzazione. Docker introduce il concetto di “contenitore” volto allo svolgimento di una unica funzione, nel nostro caso una analisi bioinformatica. Il contenitore è eseguito in un ambinete virtualizzato estremanente efficiente e leggero dove l’unica dipendenza richiesta con il sistema ospite è il kernel (GNU/Linux). La riproducibilità e tracciabilità della installazione è garantita da una immagine che viene creata a partire da un file (Dockerfile) che descrive nel dettaglio i componenti software, le modalità di

installazione e di esecuzione. In questo approccio ogni procedura di analisi può essere richiamata velocemente ed in maniera semplice. In questa ottica il laboratorio di R&D ha già iniziare la prototipizzazione di alcune procedure, un obiettivo parziale è la creazione di una libreria di Dockerfile per ognuna delle analisi da realizzare.

E’ in corso di realizzazione una nuova tipologia di cloud privato, su infrastruttura di proprietà di UniCredit che quest’ultima mette a disposizione di INGM, in orari di basso carico, per finalità di ricerca e nell’ambito delle proprie attività filantropiche. Diventa quindi importante sviluppare una strategia di deployment, basata su Docker, che tenga in considerazione i vincoli impliciti nell’utilizzo di un’infrastruttura che è sia sensibile che progettata per fini diversi dalla ricerca. Al tempo stesso, INGM e UniCredit stanno collaborando per esplorare come sia possibile ottimizzare l’utilizzo delle risorse dei due istituti.

La proposta di tesi prevede di sviluppare e implementare la strategia di deployment basata su Docker in modo da soddisfare le esigenze di INGM (principalmente facilità di adattamento a modifiche minori delle analisi da realizzare) e di semplificare la gestione, considerando la diversità delle risorse hw/sw da utilizzare.

Luogo

Istituto Nazionale di Genetica Molecolare  — Milano — http://www.ingm.org

Requisiti

Conoscenza di sistemi Linux

Competenze acquisibili

Utilizzo di Docker come sistema di deployment

Esperienza di utilizzo di infrastrutture private

Risultati attesi

Un sistema di gestione di tali configurazioni.

Per informazioni contattare

Gianluca Della Vedova <gianluca.dellavedova@unimib.it> oppure Raoul Bonnal <bonnal@ingm.org>

Tempo di realizzazione

3 mesi