Postdoctoral researcher Djamal Belazzougui got a paper accepted to STOC, The ACM Symposium on the Theory of Computing, that stands as the top forum for theoretical computer science research. The paper consists of optimal space-efficient randomized algorithms for constructing compressed suffix arrays and compressed suffix trees. Space-efficiency of the construction algorithms means that the peak space is asymptotically bounded by the input and the output. In this context, the size of the output (compressed data structure) is itself asymptotically bounded by the size of the input (string).     

The research results can be applied to a variety of domains. For example, one can now construct the bidirectional Burrows-Wheeler transform (BWT) -based indexes proposed in ESA 2013, in order to solve problems related to the analysis of set of sequences, such as discovering maximal unique matches (MUMs) between two input sequences.  Such MUMs are exploited in popular tools for comparative genomics, as they provide anchors for genome-wide alignments.

Department's software engineering project has currently a group of students dedicated to implementing the above kind of sequence analysis algorithms on top of the bidirectional BWT.

The manuscript is available in ArXiv.