Fully-functional bidirectional Burrows-Wheeler indexes

01/29/2019
by   Fabio Cunial, et al.
0

Given a string T on an alphabet of size σ, we describe a bidirectional Burrows-Wheeler index that takes O(|T|σ) bits of space, and that supports the addition and removal of one character, on the left or right side of any substring of T, in constant time. Previously known data structures that used the same space allowed constant-time addition to any substring of T, but they could support removal only from specific substrings of T. We also describe an index that supports bidirectional addition and removal in O(|T|) time, and that occupies a number of words proportional to the number of left and right extensions of the maximal repeats of T. We use such fully-functional indexes to implement bidirectional, frequency-aware, variable-order de Bruijn graphs in small space, with no upper bound on their order, and supporting natural criteria for increasing and decreasing the order during traversal.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset