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:
- definire e studiare il problema computazionale quando il pattern a sua volta è un grafo.
- implementare un algoritmo di pattern matching con testo che è un grafo
- disegnare e implementare un algoritmo di allineamento di un read con un grafo
- 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