Compressed suffix tree—a basis for genome-scale sequence analysis

    loading  Checking for direct PDF access through Ovid



Suffix tree is one of the most fundamental data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length n from alphabet Σ={A, C, G, T } can be stored in n log |Σ|=2n bits, its suffix tree occupies O(n log n) bits. In practice, the size difference easily reaches factor 50.


We provide an implementation of the compressed suffix tree very recently proposed by Sadakane (Theory of Computing Systems, in press). The compressed suffix tree occupies space proportional to the text size, i.e. O(n log} | Σ |) bits, and supports all typical suffix tree operations with at most log n factor slowdown. Our experiments show that, e.g. on a 10 MB DNA sequence, the compressed suffix tree takes 10% of the space of normal suffix tree. Typical operations are slowed down by factor 60.

Related Topics

    loading  Loading Related Articles