Memory-Aware BWT by Segmenting Sequences to Support Subsequence Search

摘要: Nowadays, Burrows-Wheeler transform (BWT) has been receiving significant attentions in academia for addressing subsequence matching problems. Although BWT is a typical technique to sequence into new that "easy compress", it can also be extended as kind of full text index techniques. Traditional requires nlogn+nlogσ bits build with n characters, where σ size the alphabet. Building long on PCs limited memory great challenge. In order solve problem, we propose novel variation named S-BWT, which separates source segments. It reduce cost n(logσ+logn−logk )/k bits, k number However, querying each segment separately using existing approaches undertake risk losing some results. this paper, two query methods based S-BWT and guarantee find all occurrences. Our not only require small space, but are faster than state-of-art backward search method sequence.