Advanced Techniques for Combinatorial Algorithms

In February-March 2016, we will give a PhD course on Advanced Techniques for Combinatorial Algorithms.

This course focuses on the design and the analysis of efficient algorithms, with a strong
emphasis on theoretical aspects.

The goal of the course is to give a broad coverage of the main techniques in algorithm
design and analysis, so that the course can be useful also for a researcher in a different
field. To this purpose, the computational problems tackled are among the most basic
problems on strings and graphs, such as pattern matching, vertex cover and max cut.

The official page is here.

Schedule

  • Feb. 2, 10:30-12:30 – meeting room III floor, U14, (lecturer Gianluca Della Vedova). Parallel Algorithms. (PRAM model, prefix sum algorithm, tree depth, connectivity). slides
  • Feb. 3, 10:30-12:30 – meeting room III floor, U14, (lecturer Gianluca Della Vedova). Randomized Algorithms. (Karp-Rabin algorithm for pattern matching). Succinct representations of data (Entropy, Huffman codes, Jensen’s Inequality, Elias’ gamma and delta codes) slides
  • Feb. 8, 14:00-16:00 – Seminar Room, U14 (lecturer Pawel Gawrychowski). Suffix arrays (construction and pattern matching) slides
  • Feb. 9, 14:00-16:00 – T014 (lecturer Pawel Gawrychowski). Suffix arrays 2 (Burrows-Wheeler transform and Lempel-Ziv factorization) slides
  • Feb. 11, 11:00-13:00 – Seminar Room, U14 (lecturer Pawel Gawrychowski). Indexing with errors (indexing with k mismatches, heavy path decomposition) slides
  • Feb. 16, 11:00-13:00 – meeting room III floor, U14 (lecturer Travis Gagie). Basic Lossless Data compression (The Kraft Inequality and Jensen’s Inequality; Shannon’s Noiseless Coding Theorem; Shannon and Huffman Codes; Canonical Codes; Elias Codes; empirical entropy; LZ77 and LZ78; BWT)
  • Feb. 17, 11:00-13:00 – meeting room III floor, U14, (lecturer Travis Gagie). Compressed data structures (Bitvectors; wavelet trees; compressed permutations; rank and select on sequences; succinct trees). voce enciclopedia articolo introduttivo slides
  • Feb. 18, 11:00-13:00 – Seminar Room, U14, (lecturer Travis Gagie). Self-Indexes for Strings and Graphs (LZ-based indexes; FM-indexes; LZ/FM-hybrid indexes; the XBWT for labelled trees; BWT-based representations of de Bruijn graphs; the GCSA for genomic graph references) articolo introduttivo slides
  • Mar. 1, 14:00 – 16:00 – meeting room III floor, U14, (lecturer Gianluca Della Vedova) Approximation Algorithms. (Algorithms for Vertex Cover, Satisfiability, Max Cut. Approximation Complexity)
  • Mar. 8, 14:00 – 16:00 – meeting room III floor, U14, (lecturer Gianluca Della Vedova) Approximation Algorithms. slides

An in-silico framework for comparing and validating transcripts predicted from single and paired-end reads

Anna Paola Carrieri, Stefano Beretta, Gianluca Della Vedova, Ernesto Picardi, Yuri Pirola, Raffaella Rizzi, Graziano Pesole, and Paola Bonizzoni, NGS 2012 (poster and abstract).

With the advent of high-throughput sequencing of transcriptome (RNA-Seq), different computational methods that use RNA-Seq data to assemble full-length mRNA isoforms have been proposed, albeit not solving completely the problem. We have analyzed some of the most used available tools, evaluating their performance and accuracy.

Our experimental analysis reveals that using GSNAP instead of TopHat gives more specific predictions with also a minor (but statistically inconclusive) improvement in sensitivity.

We plan to extend our study (i) by introducing some alternatives to EVAL for comparing predictions, (ii) by considering different kinds of simulated data (more coverage levels and/or errors), as well as real data, and (iii) by analyzing in more detail the structure of predicted transcripts since a preliminary study in this direction reveals that the actual methods have various shortcomings in assembling transcripts.

Detection of long noncoding (lncRNA) involved in RNA-Seq isoforms

 

  • Detection of long noncoding (lncRNA) involved in RNA-Seq isoformsHassan MahmoudDISCO, May 28, 2015 (slides).
    The recent discovery showed that the human and other mammalian genomes produce thousands of mRNA-like molecules namely, long noncoding RNAs (lncRNAs). Almost on a weekly basis, many biological studies detected that lncRNA is to be up or down-regulated in a particular disease. However, these lncRNAs which lack significant protein-coding capacity have been implicated in a wide range of biological functions through diverse and as yet poorly understood molecular mechanisms. The majority of human genes are alternatively spliced in a highly tissue and cell type–specific manner essential for generating protein diversity. The production of alternative splicing mRNAs is regulated by combinatorial use of multiple cis-acting RNA elements along the precursor mRNA (pre-mRNA). In this talk, I will show the concepts and subtypes of lncRNA, their role in gene regulation and their relation to alternative splicing, and the bioinformatics tools used for detecting lncRNA mainly from sequencing isoforms.

 

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

Stage Esterno: Gestione di sistemi di deployment basati su Docker in infrastrutture vincolate

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

Una libreria di configurazioni docker adatte al sistema di riferimento.

Per informazioni contattare

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

Tempo di realizzazione

3 mesi