https://www.dagstuhl.de/19241

June 10 – 14 , 2019, Dagstuhl Seminar 19241

25 Years of the Burrows-Wheeler Transform

Organizers

Travis Gagie (Universidad Diego Portales, CL)
Giovanni Manzini (University of Eastern Piedmont – Alessandria, IT)
Gonzalo Navarro (University of Chile – Santiago de Chile, CL)
Jens Stoye (Universität Bielefeld, DE)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 9, Issue 6 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
schedule [png]
birthday_photo [jpeg]
closing [jpeg]
Dagstuhl Seminar Schedule [pdf]

Summary

Dagstuhl Seminar 19241 marked the 25th anniversary of the publication of the Burrows-Wheeler Transform (BWT), which has had a huge impact on the fields of data compression, combinatorics on words, compact data structures, and bioinformatics. The 10th anniversary in 2004 was marked by a workshop at the DIMACS Center at Rutgers (http://archive.dimacs.rutgers.edu/Workshops/BWT ) organized by Paolo Ferragina, Giovanni and S. Muthukrishnan, and it is exciting to see how far we have come. In the past 15 years, interest in the BWT has shifted from data compression to compact data structures and bioinformatics, particularly indexing for DNA read alignment, but seven of the 33 participants of that workshop (including Giovanni) also attended this seminar. Unfortunately, Professor G{o}rtz fell ill at the last minute and emailed us on June 11th to say she couldn't attend, but everyone else on the final list of invitees was present for at least some of the seminar (although not everyone made it into the photo). In total there were 45 people (listed at the end of this report) from 13 countries, including ten women, six junior researchers and two researchers from industry. By happy coincidence, the seminar started the day after Gonzalo's 50th birthday, so we were able to celebrate that as well. We thank Professor Sadakane for the photos shown in Figures 1 and 2.

The schedule, shown in Figure 3, featured an introduction, 12 talks, three panel sessions and a closing. The talks were all timely and reflected the active and dynamic research being carried out on the BWT:

  • Giovanni's introduction was a more in-depth version of his invited talk from DCC '19;
  • Veli Mäkinen surveyed pan-genomic indexing, including work published in BMC Genomics last year;
  • Richard Durbin surveyed results based on the positional BWT, published in Bioinformatics in 2014;
  • Jouni Sirén presented work included in a Nature Biotechnology article last year;
  • Christina Boucher surveyed compact data structures for de Bruijn graphs, including work from an ISMB/ECCB 2019 paper;
  • Gonzalo Navarro reviewed BWT-based indexes, including work from a SODA '18 paper;
  • Sandip Sinha presented work from a STOC '19 paper;
  • Dominik Kempa presented work from another STOC '19 paper;
  • Sharma Thankachan presented work from an ESA '19 paper;
  • Marinella Sciortino gave a version of her invited lecture for IWOCA '19 a month later;
  • Giovanna Rosone presented results about two extensions of the BWT, including work from a WABI '18 paper, now published in Algorithms for Molecular Biology;
  • Dominik Klöppl presented work from a CPM '19 paper.

We later received all the abstracts but one.

Summary text license
  Creative Commons BY 3.0 Unported license
  Travis Gagie, Giovanni Manzini, Gonzalo Navarro, and Jens Stoye

Classification

  • Bioinformatics
  • Data Bases / Information Retrieval
  • Data Structures / Algorithms / Complexity

Keywords

  • Burrows-Wheeler Transform
  • Data Compression
  • Indexing
  • Sequence Alignment

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.