资 源 简 介
Summary
This project is an implementation of the blockwise Burrows-Wheeler transform algorithm described in "Fast BWT in small space by blockwise suffix sorting," Karkkainen, (2007). This implementation is specialized for DNA sequences, meaning an alphabet consisting only of {A, C, G, T}. The advantage of the blockwise BWT over other algorithms is the space efficiency of the procedure, which is controlled by a user-specified parameter v. The complexity is O(nlogn + vn) time and O(nlogn/sqrt(v)) space in addition to storing the original string and the resulting BWT. Space efficiency is important in the analysis of DNA sequences, which can be long enough such that storing all of the sequences in memory is infeasible.
References
See the following paper by Juha Karkkainen, "Fast BWT in small space by blockwise suffix sorting," (http://www.cs.helsinki.fi/u/tpkarkka/publications/tcs07-revised.pdf) for the details of the algorithm.
<
