search

davidecenzato / optimalBWT

A tool for computing the optimalBWT of string collections
8 stars 1 forks source link

The inverse transform of optBWT #2

Closed xiaoYu0103 closed 7 months ago

xiaoYu0103 commented 8 months ago

For example: M={TGA,CACAA,AGAGT,TAA,CGAGT,CCA,TA} optBWT(M)=TTAAAAAAAGCTTCC$GGCA$$$TCAAAGG$$$ How do I invert optBWT(M) back to M?

davidecenzato commented 8 months ago

Hello, I will split the answer in two. 1) Practical answer: We currently do not provide software for inverting the optBWT in this repository. However, you can invert the optBWT by using any software that works on the BWT given in output by the BCR algorithm (example: https://github.com/giovannarosone/BCR_QS_decode). 2) Theoretical answer: You can invert the optBWT by using the LF-property as we do with the classic BWT. The algorithm employed is very similar to the backward search; the only difference is that we have n strings here, so we will need to walk over n cycles. (You can find a nice explanation of this procedure in Chapter 4 of this paper, "Lightweight algorithms for constructing and inverting the BWT of string collections" Bauer et al. 2013)

xiaoYu0103 commented 8 months ago

Thanks, I have solved this problem through your help！