Stage Interno: valutazione di programmi per il calcolo della trasformata di Burrows-Wheeler

Descrizione

LightStringGraph è un programma sviluppato dal nostro gruppo di ricerca per l’assemblaggio del genoma a partire da dati derivanti dalle nuove tecnologie di sequenziamento. Questo programma è basato sull’algoritmo chiamato trasformata di Burrows-Wheeler, e incorpora un programma che implementa tale algoritmo.

Recentemente è stata proposta una nuova implementazione alternativa: ropebwt. Questo stage ha come obiettivo modificare LightStringGraph per utilizzare ropebwt, valutandone le conseguenze in termini di tempi di calcolo.

Luogo

DISCo – Unimib

Requisiti

Conoscenze basilari del linguaggio di programmazione C++.

Competenze acquisibili

Capacità di lavorare su programmi scritti in C++. Capacità di usare un sistema di controllo di versione (git). Capacità di relazionarsi con persone aventi competenze eterogenee, lavoro di team, tempistiche di consegna e valutazione di fattibilità.

Risultati attesi

Aggiornamento del programma LightStringGraph. Realizzazione di una sperimentazione per valutare le modifiche apprortate.

Per informazioni contattare

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

Tempo di realizzazione

3 mesi

Stage Interno: Rifattorizzazione programma per il calcolo di splicing alternativo

Descrizione

PIntron è un programma sviluppato dal nostro gruppo di ricerca per il calcolo della struttura esoni-introni di un gene. Questo software viene attualmente utilizzato per alimentare uno dei principali database biologici  dedicati agli effetti del fenomeno biologico chiamato splicing alternativo.

Per adattare questo software ai dati derivanti dalle nuove tecnologie di sequenziamento, diventa necessario pensare una rifattorizzazione del codice ed alla preparazione di un insieme di test (di regressione e unit test) per evitare di compromettere la qualità delle predizioni.

Luogo

DISCo – Unimib

Requisiti

Conoscenze basilari del linguaggio di programmazione C e di test dei programmi.

Competenze acquisibili

Capacità di lavorare su programmi scritti in C. Capacità di usare un sistema di controllo di versione (git). Capacità di relazionarsi con persone aventi competenze eterogenee, lavoro di team, tempistiche di consegna e valutazione di fattibilità.

Risultati attesi

Aggiornamento del programma PIntron. Realizzazione di una sperimentazione per valutare le modifiche apprortate.

Per informazioni contattare

Gianluca Della Vedova <gianluca.dellavedova@unimib.it> o Raffaella Rizzi <raffaella.rizzi@unimib.it>

Tempo di realizzazione

3 mesi

Stage Interno: Confronto di approcci per lo spliced alignment

Descrizione

Il problema dello spliced alignment consiste nel allineare una porzione di trascritto con un genoma di riferimento. II programma che affronta questo problema viene detto spliced aligner e realizza uno dei passi principali di un sistema di predizione di splicing alternativo: PIntron. 

L’obiettivo dello stage consiste nel sostituire in PIntron lo spliced aligner attualmente utilizzato con GSnap e verificare sperimentalmente gli effetti di tale sostituzione nei tempi di esecuzione e nella qualità delle predizioni.

Luogo

DISCo – Unimib

Requisiti

Conoscenze basilari del linguaggio di programmazione C.

Competenze acquisibili

Capacità di lavorare su programmi scritti in C. Capacità di eseguire e comprendere una valutazione statistica dei risultati di una sperimentazione. Capacità di usare un sistema di controllo di versione (git). Capacità di relazionarsi con persone aventi competenze eterogenee, lavoro di team, tempistiche di consegna e valutazione di fattibilità.

Risultati attesi

Aggiornamento del programma PIntron. Realizzazione di una sperimentazione per valutare le modifiche apprortate.

Per informazioni contattare

Gianluca Della Vedova <gianluca.dellavedova@unimib.it> o Raffaella Rizzi <raffaella.rizzi@unimib.it>

Tempo di realizzazione

3 mesi

Stage Interno: Sviluppo applicazione web per indentificazione di splicing alternativi

Descrizione

Vogliamo realizzare un’applicazione web che si interfacci ad un software esistente (PIntron) che predice la struttura esoni-introni di un gene. Questo software viene attualmente utilizzato per alimentare uno dei principali database biologici  dedicati agli effetti del fenomeno biologico chiamato splicing alternativo.

L’obiettivo dello stage consiste nella creazione di una interfaccia web per utilizzare il software. Nello stage è previsto l’utilizzo del framework di sviluppo web Ruby on Rails.

Luogo

DISCo – Unimib

Requisiti

Conoscenze basilari di programmazione web.

Competenze acquisibili

Capacità di sviluppare applicazioni web con Ruby on Rails. Capacità di usare un sistema di controllo di versione (git). Capacità di relazionarsi con persone aventi competenze eterogenee, lavoro di team, tempistiche di consegna e valutazione di fattibilità.

Risultati attesi

Progettazione e implementazione di un’applicazione web per la bioinformatica.

Per informazioni contattare

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

Tempo di realizzazione

3 mesi

Combinatorial Structures for Sequence Analysis in Bioinformatics

27 Novembre 2013
Aula Seminari
Dipartimento di Informatica, Sistemistica e Comunicazione (Edificio U14)
Univ. degli Studi di Milano-Bicocca

Presentazione

Nell’ambito del Progetto PRIN 2010/2011 “Automi e Linguaggi Formali: aspetti matematici e applicativi” si svolgerà il 27 Novembre 2013 presso il Dipartimento di Informatica, Sistemistica e Comunicazione dell’Università di Milano-Bicocca un workshop dedicato a strutture combinatorie per l’analisi di sequenze in bioinformatica.

L’incontro si propone l’obiettivo di dare la possibilità, sia ai ricercatori del progetto PRIN che ad altri che si occupano di algoritmi su stringhe e sequenze di riunirsi per presentare le proprie linee di ricerca, i risultati ottenuti e i problemi aperti al fine di iniziare nuove collaborazioni e rinforzare quelle già esistenti.

Programma

9.15 – 9.30  Apertura lavori

9.30 – 10.30 Gregory Kucherov: “Algorithms and data structures for Next-Generation Sequencing data”.

10.30 – 11.00  Discussione

11.00 – 11.30  Giovanna Rosone: “Extended Burrows-Wheeler Transform and analysis of biological sequences”

11.30 – 11.45 Discussione

11.45 – 12.15   Yuri Pirola: “Combinatorial structures and NGS data in Transcriptomics: some results”

12.15 – 12.45  Paola Bonizzoni: “Combinatorial structures and NGS data in Transcriptomics: some open problems”

12.45 – 13.00  Discussione

13.00 – 14.30  Pausa pranzo

14.30 – 15.00 Francesco Masulli: “Predicting microRNA Target Genes”

15.00 – 15.15  Discussione

15.15 – 15.45 Zsuzsanna Lipták: “Jumbled String Matching: Motivations, Variants, Algorithms”

15.45 – 16.00 Discussione

16.00 – 18.00 Apertura della tavola rotonda: presentazione di problemi aperti e discussione

Ulteriori informazioni

Il workshop si terrà nell’aula Seminari del Dipartimento di Informatica, Sistemistica e Comunicazione. Indicazioni su come raggiungere la sede del workshop sono disponibili a questa pagina.

Per ogni informazione, contattare gianluca.dellavedova@unimib.it

Abstract  degli interventi

Gregory Kucherov: “Algorithms and data structures for Next-Generation Sequencing data“.

In the middle of the 00’s, the whole area of bioinformatics, already under rapide development, underwent a new breakthrough caused by the advent of Next Generation Sequencing (NGS) technologies. I will give a very quick introduction to NGS for computer scientists, highlighting main involved computational challenges. Then I’ll survey some my contributions to the area, namely on read mapping on the one hand, and on storing de Bruijn graphs for genome assembly on the other hand.

Giovanna Rosone: “Extended Burrows-Wheeler Transform and analysis of biological sequences

The advent of “next-generation” DNA sequencing (NGS) technologies has meant that collections of hundreds of millions of DNA sequences are now commonplace in Bioinformatics.
For instance, a human genome sequencing experiment might yield a billion or more sequences, each 100 characters in length. Such a dataset can now be generated in just a few days on a single sequencing machine.
Many algorithms and data structures for compression and analysis of a text have the BWT at their heart, and it would be of great interest to explore their applications to sequence collections such as these.
We describe and highlight an extension of the Burrows-Wheeler Transform (EBWT), of the suffix array and of the longest common prefix array to very large string collections.
We introduce a new methodology for computing the EBWT for 100 billion characters or more of data in external memory. We use the EBWT for applications in the context of string processing, such as large-scale compression of genomic sequence databases, compression of sequence quality scores and comparison of DNA Sequence Collections.

Yuri Pirola: “Combinatorial structures and NGS data in Transcriptomics: some results”

Next-Generation Sequencing (NGS) technologies need new methodologies for Alternative Splicing (AS) analysis.
In this talk we discuss a combinatorial structure that gives a compact representation of gene structures—called  splicing graph—and investigate the computational problem of building a splicing graph that is compatible with NGS data. More precisely, a fundamental question we are going to investigate is: under which conditions can the reconstruction of a gene structure be efficiently accomplished using only information provided by RNA-Seq data?
In order to partially answer this question, we introduce the formal definition of the computational problem of reconstructing the gene structure from RNA-Seq data when the solution is represented by a splicing graph and we give some necessary conditions under which the reconstructed splicing graph represents the real (unknown) gene structure. Finally we describe an efficient algorithm that, under some conditions, is able to exactly solve our problem but that is also able to achieve good accuracy on real genes violating such conditions.

Bonizzoni Paola: “Combinatorial structures and NGS data in Transcriptomics: some open problems”

In this talk we discuss new approaches to the comparison of short sequences (RNA-Seq sequences) produced by NGS technologies when applied  to transcriptomic data. We discuss the computational problem of assembling a string-graph from RNA-Seq data using the Burrows Wheeler transform and a space efficient FM-index to detect overlaps in a collection of sequences.

Francesco Masulli: “Predicting microRNA Target Genes”

miRNA (microRNAs) are a class of short, non coding RNA capable of base-pairing with imperfect complementarity to the transcripts of animal protein-coding genes (targets). In such a way, they negatively regulate gene expression; however, the exact mechanism remains still unclear. Since each miRNA targets several hundreds of transcripts and each transcript can be the target of multiple miRNAs, the complexity of this class of RNA is remarkable. miRNA are in involved in the pathway of several biological processes, including tumors such as prostate cancer, lung cancer, breast cancer, and colorectal cancer, as well neurogenesis and synaptic function. Computational prediction of miRNA targets is not an easy task. In the last few years, more than 10 target prediction programs have been developed. They typically analyze sequences by a sliding window and, in order to reduce false positive predictions, they test each site of the gene with some algorithms in cascade. miRanda, proposed in 2003, is the most popular miRNA target prediction method. It splits the target site prediction task into three distinct steps carried out in sequence: (a) Homology evaluation; (b) Free energy computation; (c) Evolutionary conservation computation. The parameters used in miRanda have been manually optimized according to biological knowledge and software tools available in 2003 (with some updates).
We present an approach to improve the computational estimation of target sites, maximizing the adherence of results to biological evidence. The proposed method provides some improvements on the original miRanda program. In particular, we employ the new RNAcofold routine for free energy computation and we improve the match between the set of estimated target genes and the set of biologically validated target genes nowadays known by using a genetic algorithm. Our method is more selective than miRanda. The validated targets with the proposed method have consistently better free energy than the others in the list; this is not true for miRanda. The increased selectivity of the method may also be used to guide experimental validation in a more focused direction.

Zsuzsanna Lipták: “Jumbled String Matching: Motivations, Variants, Algorithms”

In the classical exact string matching problem, we are given two strings s (the text) and t (the pattern), and we want to find all occurrences of t as substrings of s. In jumbled string matching, the goal is to find all occurrences of substrings t’ of s with the same multiplicity of characters as the pattern, i.e. all permuted (or jumbled) versions of the pattern. Alternatively, the pattern can be given as a vector specifying the character multiplicities (a so-called Parikh vector), and we want to find all occurrences of substrings with this Parikh vector.
For example, the text s=baacabccab has two occurrences of the pattern (2,1,1), i.e. of substrings consisting of two a’s, one b, and one c: in position 1 and in position 3. The online version of the problem can be solved optimally in O(n) time with a simple sliding window algorithm. However, the indexed version, where we want to answer multiple queries fast, using an index of the text, has proved challenging.
Variants of this problem are motivated by applications in mass spectrometry data interpretation, by gene clusters, and by motif search in networks. I will talk about different algorithms for several variants of the problem, including the case of binary alphabets, which has very specific properties, and which has aroused much interest in recent years.

Our Git branching model

The main inspiration is A successful Git branching model by Vincent Driessen. The main difference is that we do not want (and cannot) manage different releases. Therefore we always have one current and supported version, stored in the master branch.

The main branches

t the core, the development model is greatly inspired by existing models out there. The central repo holds the master branch with an infinite lifetime. At each time master is deployable and must pass all tests.

We consider origin/master to be the main branch where the source code of HEAD always reflects a production-ready state. In fact, each time when changes are merged back into master, this is a new production release by definition. We tend to be very strict at this, so that theoretically, we could use a Git hook script to automatically build and roll-out our software to our production servers everytime there was a commit on master. We plan to integrate Travis CI into our workflow.

Feature branches

Branch off from: master
$ git checkout -b myfeature master
Switched to a new branch "myfeature"
Must merge back into: master
$ git checkout master 
Switched to branch 'master'
$ git merge --no-ff myfeature
Updating ea1b82a..05e9557
(Summary of changes)
$ git branch -d myfeature
Deleted branch myfeature (was 05e9557).
$ git tag -a v1.2.3
Branch naming convention: anything except master

Next to the main branch master, our development model uses only a set of feature branches devoted to the development of distinct features. Unlike the main branch, these branches always have a limited life time.

The essence of a feature branch is that it exists as long as the feature is in development, but will eventually be merged back into master (to definitely add the new feature to the public release) or discarded (in case of a disappointing experiment). Feature branches typically exist in developer repos only, not in origin, except for those features that requires a collaboration between multiple developers.

Incorporating a finished feature

Finished features may be merged into the master branch definitely add them to the upcoming release.

The –no-ff flag causes the merge to always create a new commit object, even if the merge could be performed with a fast-forward. This avoids losing information about the historical existence of a feature branch and groups together all commits that together added the feature.

In the latter case, it is impossible to see from the Git history which of the commit objects together have implemented a feature—you would have to manually read all the log messages. Reverting a whole feature (i.e. a group of commits), is a true headache in the latter situation, whereas it is easily done if the –no-ff flag was used.

Yes, it will create a few more (empty) commit objects, but the gain is much bigger that that cost.

Also, we tag each deployable version according to Semantic Versioning.

Documentation

Update the documentation residing in the gh-pages branch. Remember to bump the version number.

$ git checkout gh-pages
[edit]
$ git commit -a

At the end we push the update versions to the shared repos (usually github under the AlgoLab organization)

$ git push origin; git push --tags

Issue tracker

All defects found must be added to the issue tracker. All possible improvements should be added to the issue tracker.

Bugfix commits can be applied directly to master.

Commit message

The first line of the message must be a capitalized, short (50 chars or less) summary. The first line must be separated from the remaining part by a blank line. The body of the message should be wrapped at 72 chars. The final paragraph should be a line with the list of bugs closed by the commit. I.e. Fix: 1234, 1235

Credits

Heavily inspired from http://nvie.com/posts/a-successful-git-branching-model/ and http://tbaggery.com/2008/04/19/a-note-about-git-commit-messages.html

Licence

CC-SA