10. – 14. Juni 2019, Dagstuhl-Seminar 19241

25 Years of the Burrows-Wheeler Transform


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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 9, Issue 6 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]


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 ( ) 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;
  • Nicola Prezza presented work from a STOC '18 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


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


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


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.