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