25 Years of the Burrows-Wheeler Transform

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;
• 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.