Repository navigation
Other Ideas
There are many ideas that could improve the GBWT, at least in principle. This page documents some of them and discusses their benefits and obstacles to implementation.
The BWT in the endmarker record stores the first node on each path. When the GBWT is bidirectional, each path is followed by its reverse complement. Hence the BWT in the endmarker usually consists of an alternating sequence of (small node id, forward), (large node id, reverse) pairs. Naive run-length encoding does not work with such sequences, but it would be easy to adapt it to encode runs of pairs. This could be useful if there are many paths in the GBWT.
PBWT construction does not have to buffer entire sequences before indexing them. At each step, it writes the next symbol in the each sequence and reorders the sequences. In principle, the same approach would work with the GBWT as well. This would enable inserting paths in larger batches, making construction faster and more space-efficient.
There are two obstacles to this approach. First, GBWT paths quickly get out of sync. While each PBWT sequence goes through the same positions, indels in the original sequences become indels on the GBWT paths. Hence some buffering would be necessary with direct construction as well. Second, in a bidirectional GBWT, the paths alternate between forward and reverse versions of the same path. Hence the direct construction would have to work in two passes. The first pass parses the input in forward direction and inserts the forward paths, while the second pass parses the input in reverse direction and inserts the reverse paths in the middle.
The r-index is incompatible with bidirectional search. In unidirectional search, when we extend the pattern backward with character c, we always know the text position i = SA[sp] corresponding to the first BWT offset sp in the range. The position is either i - 1 for the previous i if BWT[sp] == c or SA[j] - 1 for the first j > sp with BWT[j] == c, where BWT[j] is sampled.
In bidirectional search, we narrow the reverse interval down to a subinterval of the original. There we have no guarantees that we know the text position corresponding to the start of the new subinterval. If we use bidirectional search, we must either repeat the search unidirectionally with the final pattern before using the r-index locate() or start the locate() from the last run head before sp.