Bidirectional BWT

The BWT index for two strands was too large and difficult to handle. Lam et. al. proposed a method, where they did not have to hold two different suffix arrays.

“The original BWT allows searching of a pattern in one direction, namely, from right to left (backward search). However, for efficient approximate pattern searching, we need a data structure that can support searching in both directions (forward and backward search) and allow us to switch from forward to backward search or vice versa in the course of aligning the pattern. This would enable us to start matching a pattern from the middle, then extend the search in either directions and switch directions in the alignment process. A seemingly trivial solution is to keep two BWTs, one for the original sequence and the other for the reversal. Then forward search can be done via a backward search on the reversal of the pattern based on the latter BWT.

However, this solution cannot allow interleaving the backward and forward search. And it deals with two separate searching space, demanding a lot more memory (see Section III for details). We develop a new indexing data structure, called bi-directional BWT, to solve this problem. Based on bi-directional BWT, we develop a new short read alignment tool 2BWT, which is faster than all existing tools.”