Abstract
Burrows-Wheeler Transform (BWT) is a popular algorithm applied in data compression and DNA sequence alignment. Due to the emergence of Next Generation Sequencing --- the latest DNA sequencing method that significantly reduces the cost of time and space required by traditional sequencing methods, DNA sequence alignment has become a subject of great concern in recent years. Currently, many of the sequence alignment tools, such as BWA, Bowtie and SOAP2, are based on BWT to reduce the memory requirement. However, it is not convenient for us to re-do the transform of whole collection of sequences while we only add or delete a sequence in the collection. In order to improve the time and space required for re-transform, we designed and implemented a dynamic BWT algorithm. With our method, we can get the same result as the static transform in a shorter time, and do not need to re-do the transform.