Campus Event Calendar

Event Entry

What and Who

Compact Representation of Automata and Algorithms for its xBWT

Serikzhan Kazi
University of Helsinki
PhD Application Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience

Date, Time and Location

Monday, 19 May 2014
60 Minutes
E1 4


The celebrated Burrows-Wheeler Transform (BWT) has been applied to objects of increasing complexity, from strings through trees to certain types of directed acyclic graphs (DAG), called prefix-range sorted automata. The algorithmic significance of (Extended)BWT – xBWT – is that it enables one to search for a sub-path anchored anywhere in the tree or DAG – not only in its root or source vertex. We construct an automaton that stores (without redundancy) a collection of genotypes and known genetic variation. Its xBWT, then, is consulted during variation calling to (quickly) decide whether the found variation is known or new. We propose and implement a rank/select-based representation of such an automaton, plus two algorithms for building its xBWT table. The first – distributed – algorithm resembles most-significant-digit radix-sort, the second – sequential – is rather conceptual and is nothing but Karp-Miller-Rosenberg naming.

We also believe that our illustrated worked example contributes towards understanding by a wider audience of seemingly mysterious workings of backward search.

The work was supported by a contract with ALGODAN (Finland) and Finnish Center of Excellence in Cancer Genetics Research.


Jennifer Gerling
--email hidden
passcode not visible
logged in users only

Jennifer Gerling, 05/15/2014 11:34 -- Created document.