Mini-course on Compressed Text Indexes by Prof. Gonzalo Navarro

Prof. Gonzalo Navarro (University of Chile, Santiago) will give a mini-course on Compressed Text Indexes on Monday, Tuesday, and Wednesday, 22, 23, 24 Jan. 2024: 

Mon 22 Jan. 14.30-16.30: FM-index

Tue 23 Jan. 11.30-13.30: Runlengh FM-index and r-index

Wed 24 Jan. 10.30-12.30: suffix trees on repetitive string collections 

The course is given within the second-year masters course "Computational Analysis of Genome-Scale Sequences" (LM Medical Bioinformatics). All lectures will take place in room T.06 (CV3). 

Everyone is welcome to atttend. 

Abstract: 
The amount of publicly available biological data has been increasing in recent decades at a breathtaking pace, for instance GenBank contains sequences totaling around 2.5 terabases. As far as non-biological text is concerned, it is estimated that Google indexes currently around 60 billion webpages. 

In order to be able not only to store, but also query, mine, and process this rapidly growing data, dedicated data structures (so-called text indexes) are needed. Fortunately, much of this data is highly repetitive, thus text indexes that take advantage of this repetitiveness are particularly suitable. These include those based on the Burrows-Wheeler Transform (BWT) [Burrows and Wheeler, 1994], such as the FM-index [Ferragina and Manzini, SODA 2000, JACM 2005], the RLFM-index [Maekinen and Navarro, 2005], and the r-index [Gagie, Navarro, Prezza, SODA 2018, JACM 2020]. 

In this mini-course, the main ideas behind these data structures will be introduced. 

Brief bio: 
Gonzalo Navarro is full professor at the University of Chile. He is author of the book "Compact Data Structures" (CUP, 2016); editor-in-chief of the ACM Journal of Experimental Algorithmcs; member of the editorial board of ACM Transactions on Algorithms and of the Steering Committees of SEA (Symposium on Experimental Algorithms) and ESA (European Symposium on Algorithms). He is regularly keynote speaker at international conferences, most recently at ICDT & EDBT 2023, AofA 2022, and DCC 2022. He has co-authored 196 articles in international journals and 272 in international conferences, among these the journals Algorithmica, ACM TALG, JACM, ACM Comp Surveys, ACM TOIS, ACM CSUR, SICOMP; and conferences SODA, SIGIR, STACS, ICDE, ICDT, SIGMOD.