0123456789A missisippi$ c C[c] number of characters in missisippi$ that come before c $ 0 i 1 m 5 p 6 s 8 Rank_c(BWT,i) is the number of cs in BWT that preceed the c at position i i BWT SA LF[i] = C[c] + Rank_c(BWT,i) 0 i A $ 0 $ 1 = 1 + 0 1 p 9 i$ 1 i 6 = 6 + 0 2 s 6 ippi$ 8 = 8 + 0 3 s 4 isippi$ 9 = 8 + 1 4 m 1 issisippi$ 5 = 5 + 0 5 $ 0 missisippi$ 5 m 0 = 0 + 0 6 p 8 pi$ 6 p 7 = 6 + 1 7 i 7 ppi$ 2 = 1 + 1 8 i 5 sippi$ 8 s 3 = 1 + 2 9 s 3 sisippi$ A = 8 + 2 A i 2 ssisippi$ 4 = 1 + 3 How to reconstruct the initial string from the BWT only? BWT[i] i LF[i] $ 5 0 i 0 1 p 1 6 p 6 7 i 7 2 s 2 8 i 8 3 s 3 9 s 9 A i A 4 m 4 5 5 LF PSI i SA[i] LF[i] SA[LF[i]] PSI[i] SA[PSI[i]] 3 4 isippi$ 9 3 sisippi$ 8 5 sippi$ ========================================= c C[c] number of characters in missisippi$ that come before c $ 0 i 1 m 5 p 6 s 8 Select_c(BWT,n)=j if BWT[j]=c and it is the n-th occurrence of c in BWT (where the first one is the 0-th ones) let c s.t. i \in [C[c],C[c+1]) i BWT SA PSI[i] = Select_c(BWT,i-C[c]) 0 i A $ 0 $ 5 = Select_$(BWT,0-0) c=$ i\in[0,1) 1 p 9 i$ 1 i 0 = Select_i(BWT,1-1) c=i i\in[1,5) 2 s 6 ippi$ 7 = Select_i(BWT,2-1) c=9 i\in[1,5) 3 s 4 isippi$ 8 = Select_i(BWT,3-1) c=i i\in[1,5) 4 m 1 issisippi$ A = Select_i(BWT,4-1) c=i i\in[1,5) 5 $ 0 missisippi$ 5 m 4 = Select_m(BWT,5-5) c=m i\in[5,6) 6 p 8 pi$ 6 p 1 = Select_p(BWT,6-6) c=p i\in[6,8) 7 i 7 ppi$ 6 = Select_p(BWT,7-6) c=p i\in[6,8) 8 i 5 sippi$ 8 s 2 = Select_s(BWT,8-8) c=s i\in[8,B) 9 s 3 sisippi$ 3 = Select_s(BWT,9-8) c=s i\in[8,B) A i 2 ssisippi$ 9 = Select_s(BWT,A-8) c=s i\in[8,B) How to rebuild the initial message using PSI? BWT[i] i PSI[i] $ 5 4 m 4 A i A 9 s 9 3 s 3 8 i 8 2 s 2 7 i 7 6 p 6 1 p 1 0 i 0 5 $ 5