Workshop on Combinatorial Algorithms in Bioinformatics

January 26th, 2018
Univ. Milano-Bicocca. Building U14 – Room Aula Seminari

Theme and scope

The ever increasing amount of biological data available requires more efficient tools for managing and analyzing those data. While a widely used line of attack is to throw huge computational resources at the problem and using known methods as black boxes (just think at the recent widespread use of machine learning techniques such as deep learning), this
approach can only be used by a few well-funded organizations, or via cloud computing — the latter possibility brings a plethora of privacy issues. In both cases, it will be hard to extend the results to the clinicians’ desks, where a standard workstation is the most advanced hardware that can be assumed to be available.

For this reason, highly efficient (from a computational point of view) methods are a precondition to translational medicine. In particular we need to compress and query a large set of biological strings (i.e. a pan-genome) and to reconstruct tumor evolutionary histories. The introduction of Burrows-Wheeler Transform (BWT) methods to index and query single strings has resulted in a tremendous progress in short-read mapping against a single (linear) genome: today all widely used programs to align High-Throughput Sequencing data are based on the BWT or on some related notion. This is especially remarkable as it shows how widespread the applications of theoretical results can be.

The aim of this workshop is to gather researchers that are exploring both theoretical and experimental sides of combinatorial algorithms in bioinformatics, to explore the possibility of a joint research proposal.

List of relevant topics

  • sequence alignment
  • sequence mapping
  • text indexing
  • phylogeny reconstruction
  • Burrows-Wheeler Transform and FM-index
  • haplotyping

Tentative schedule

10.00-10.30 Gianluca Della Vedova (Univ. Milano-Bicocca) Computational pan-genomics

10.30-11.00. Nadia Pisanti (Univ. Pisa) Exact and Approximate Read Mapping on Reference Pan-Genome

11.00-11.30. Cinzia Pizzi (Univ. Padova) Alignment-free sequence analysis: recent results and future perspectives

11.30-12.00. Marinella Sciortino (Univ. Palermo) Combinatorial method for sequence analysis

12.00-12.30 Tiziana Calamoneri (Univ. Roma – La Sapienza) Some Problems in (Co-)Phylogeny

14-17 Discussion on research directions and funding proposals

Venue and accommodation

The workshop will take place in Milano, at the Department of Computer Science (DISco), in the Seminar Room (Aula Seminari) located in the first floor of the U14 building (Edificio U14). (Google maps)

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 5-minute walk from the workshop site.

Scientific Committee

  • Paola Bonizzoni
  • Gianluca Della Vedova
  • Raffaella Rizzi