6
$\begingroup$

The Buttows-Wheeler transform is a function that takes a string $S$ to a new string $S'$ and an index $I$. The new string $S'$ is always an anagram (rearrangement) of the input string $S$.

However, if I pick a random string $S'$ and index $I$, the inverse Burrows-Wheeler transform usually fails. For example, if $S'$ is "QUICK", the (intuitive, block-sorting) inverse method results in the following block:

CQCQC
IKUIK
KUIKU
QCQCQ
UIKUI

Clearly, none of the rows is an anagram of "QUICK", no matter the choice of $I$.

What properties must the string $S'$ satisfy so that the block contains at least one anagram of $S'$? (I suspect that if one of them is an anagram, they all are, but I don’t know how to prove it.)

$\endgroup$
1
  • $\begingroup$ This is what happens to "aba". reverse_bwt("aba", 0) is "aaa", which is not an anagram. reverse_bwt("aba", 1) is "aba", which is an anagram. However, bwt("aba") is ("baa", 1). reverse_bwt("aba", 2) is "bab", which is not an anagram. It looks like there is not much interesting stuff here. $\endgroup$
    – John L.
    Mar 26 at 2:04

1 Answer 1

2
$\begingroup$

Consider a string with repeats of a letter, for example BANANA. The forward transform will create this block:

ABANAN
ANABAN
ANANAB
BANANA
NABANA
NANABA

Now imagine we label every occurrence of A with 1, 2 or 3 depending on which A in the original word it is.

Observe that the A’s in the leftmost column are in the same order as in the rightmost column. This is because they are both sorted by whatever text comes after them in the original string.

Now imagine we take an arbitrary string $S'$ of length $n$ and label the letters in alphabetical order, but identical letters in order of occurrence. For example, for BANANA the labeling would be:

BANANA
415263

AAABNN  (sorted)
123456

This list of digits from $1$ to $n$ can be interpreted as a permutation (rearrangement).

In order to be a possible output of the Burrows-Wheeler transform, the string $S'$ must have one of the following properties:

  1. all letters in the string are the same; or
  2. the permutation is a full cycle (i.e. it has order $n$).

For example, the word “QUICK” does not work because Q and C form a separate cycle from the rest of the letters:

“QUICK”: Example that does not work

By contrast, “QUIKC” works because the permutation of letters now forms a single complete cycle:

“QUIKC”: Example that works

This property of $S'$ is necessary because without it, the inverse BWT couldn’t reconstruct the string $S$: instead of visiting every character, it would visit only the characters contained in one of the cycles (and visit them multiple times).

This property of $S'$ is also sufficient because once it is met, the inverse BWT can be performed on it to produce a string $S_i$ (with any index $i \in \left\{0..n-1\right\}$). The result of this is a string which will reconstitute $S'$ when run through BWT again.

$\endgroup$
5
  • $\begingroup$ Can you share an example that illustrates the property at the end? A proof? $\endgroup$
    – John L.
    Mar 27 at 1:41
  • $\begingroup$ @JohnL. I added diagrams to show the cycles. An outline of the proof is already in there, but I’m finding it very hard to phrase coherently. The output of BWT necessarily forms a full cycle because of the properties I’ve described. $\endgroup$
    – Timwi
    Mar 27 at 14:45
  • $\begingroup$ It seems easy to understand the necessity of the property described. I do not see a proof that it is also sufficient. Can you add that? $\endgroup$
    – John L.
    May 24 at 6:23
  • $\begingroup$ @JohnL. Added :) $\endgroup$
    – Timwi
    May 27 at 14:24
  • $\begingroup$ Thanks for explaining the idea of a proof. With more effort, a full proof can be obtained indeed. Here is one observation. There are two inverse Burrows-Wheeler transforms. The one used in this answer comes from the last-to-first column mapping. The other one, "the (intuitive, block-sorting) inverse method" that appears in the question seems not useful here. These two inverse methods behave differently when the input string is not an output of BWT. $\endgroup$
    – John L.
    May 27 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.