M.Tech. Jarno N. Alanko defends his doctoral thesis “Space-Efficient Algorithms for Strings and Prefix-Sortable Graphs” on Wednesday the 3rd of June 2020 at 16 o’clock. His opponent is Assistant Professor Sharma Thankachan (University of Central Florida, USA) and custos Professor Veli Mäkinen (University of Helsinki). The defence will be held in English.

The defence can be followed as a live stream here.

Summary:

Space-efficient data structures are an active field of research that has found many applications in combinatorial pattern matching and bioinformatics. The idea is to build data structures that occupy space close to an information-theoretic lower bound, or even less, but still support efficient query operations. In the past few decades, compact index structures have been designed for a variety of different types of data, including bit vectors, strings, trees and graphs, to name a few prominent applications.

In this thesis, we design and apply compact data structures for problems related to bioinformatics, and advance the theory of Wheeler graphs, which are a class of graphs that admit a compact indexing data structure. The work is based on four published papers.

In the first two papers, we propose compact solutions for two problems on strings. In Paper I, we design and implement an algorithm that computes the classical greedy approximation for the shortest common superstring problem. In Paper II, we design and implement data structures for storing a variable-order Markov model in a compact and queryable form.

The last two papers of the thesis expand the theory of Wheeler graphs. In Paper III, we extend the theory into finite state automata, leading to a number of interesting algorithms for recognizing, sorting, determinizing and minimizing automata that are Wheeler graphs. We also show how to turn any acyclic automaton into the minimum equivalent Wheeler graph automaton. In Paper IV, we propose a method to compress a Wheeler graph while retaining the indexing functionality, by generalizing a recently introduced method of tunneling from the Burrows-Wheeler transform to Wheeler graphs.