November 18th, 2016
Univ. MilanoBicocca. Building U24 – Room C02
Theme and scope
New and different sequencing technologies have appeared in the last few years with the promise of overcoming Illumina as the reference platform: PacBio, 10x Genomics, and MinION being the most relevant today. Those technological improvements have shown the limitations of managing linear strings instead of richer models that are usually graphbased. Transcriptomics was the first field where the need of imposing a structure over strings has become clear, leading to the notion of a splicing graph to represent all possible transcripts of a gene, as well as the exonintron structure. Genome assemblers are increasingly aware that a diploid organism has two different, but very similar, copies of each genome: hence the correct outcome of an assembly cannot be a single string. Finally, metagenomics studies different species that can share portions of the genome: another example where the correct representation of an assembly cannot be linear. Moreover, the 1000 Genomes project has generated new interest in the analysis of a population genome.
From a bioinformatics point of view, this results in the need for refining the classical approach where a genome is represented as a single string. Instead, some approaches based on graph representations have become more popular. For instance, some recent developments have been obtained on defining a common format (GFA – Graph Fragment Assembly) to represent an assembly graph.
The aim of this informal workshop is to bring together researchers from different, but correlated, areas under the widest possible notion of graph assembly algorithms, such as genome assembly, alternative splicing prediction, metagenomics, graph manipulation and representation, that are involved in the thorough investigation of these problems with both theoretical and experimental approaches. The goal is to brainstorm which challenges are the most important and can drive the research agenda in the next few years, and to jumpstart a proposal for a European Training Network (specific call) under the Horizon 2020 program and/or a COST action (call).
Nonexclusive list of relevant topics
 graph assembly
 variation graphs
 de Bruijn graphs
 string graphs
 alternative splicing
 metagenomics
 the population genome
 pangenome graph
 graph fragment assembly
Tentative schedule
99.30: Welcome and registration
9.3011.35: Session 1 (5 talks, 25 minutes each)

Alexander Schoenhuth (Centrum Wiskunde & Informatica). De novo assembly of viral quasispecies using overlap graphs (slides)

Leena Salmela (University of Helsinki). Path searching problems in de Bruijn graphs (slides)

Tomas Vinar (Comenius University). Probabilistic Models for Genome Assembly

Jouni Siren (Wellcome Trust Sanger Institute). Indexing Graphs for Path Queries (slides)

Guillaume Holley (Universität Bielefeld). Bloom Filter Trie: an efficient data structure for colored de Bruijn graphs (slides1 slides2)
11.3512.00: Coffee break
12.0013.40: Session 2 (4 talks, 25 minutes each)

Pierre Peterlongo (Université de Rennes 1). Graph assembly algorithms at the Genscale team (slides)

JeanFrançois Flot (Université libre de Bruxelles). Read compaction from a De Bruijn graph: a new paradigm for polymorphic genome assembly

Rayan Chikhi (CNRS). Efficient construction of compacted de Bruijn graphs (slides)

Rumen Andonov (Université de Rennes 1). Global Optimization Methods for Genome Scaffolding and Completing Genome Assemblies (slides)
13.4014.30: Lunch
14.3015.45: Session 3 (3 talks, 25 minutes each)

Tobias Marschall (Universität des Saarlandes). Computational pangenomics: status, promises and challenges (slides)

Eric Rivals (CNRS). Superstring Graph: an alternative to assembly with multiple de Bruijn graphs

Gianluca Della Vedova (Università di MilanoBicocca). BWT and Graph Algorithms
15.4517.30: Discussion
Venue and accommodation
The workshop will take place in Milano, at the Department of Computer Science (DISco), at the U24 building (Edificio U24).
Milan is easily reachable by all major European and main international airports. How to reach us
The suggested hotels are Starhotel Tourist and Hotel Arcimboldi that are both within a 5minute walk from the workshop site.
List of speakers
Scientific Committee:
Paola Bonizzoni
Gianluca Della Vedova
Raffaella Rizzi
List of partecipants
 Rumen Andonov
 Stefano Beretta
 Paola Bonizzoni
 Broňa Brejová
 Rayan Chikhi
 Gianluca Della Vedova
 Guillaume Holley
 JeanFrançois Flot
 Murray Patterson
 Pierre Peterlongo
 Nadia Pisanti
 Alberto Policriti
 Marco Previtali
 Eric Rivals
 Raffaella Rizzi
 Romeo Rizzi
 Giovanna Rosone
 Leena Salmela
 Alexander Schönhuth
 Marinella Sciortino
 Jouni Sirén
 Jens Stoye
 Tomáš Vinař