Search-Optimized Disk Layouts For Suffix-Tree Genomic Indexes
Rajul D Bhavsar · 2011
Over the last decade, biological sequence repositories have been growing at an exponential rate. Sophisticated indexing techniques are required to facilitate efficient searching through these humongous genetic repositories. A particularly attractive index structure for such sequence processing is the classical suffix-tree, a vertically compressed trie structure built over the set of all suffixes of a sequence. Its attractiveness stems from its linearity properties – suffix-tree construction times are linear in the size of the indexed sequences, while search times are linear in the size of the query strings. In practice, however, the promise of suffix-trees is not realized for extremely long sequences, such as the human genome, that run into the billions of characters. This is because suffix-trees, which are typically an order of magnitude larger than the indexed sequence, necessarily have to be disk-resident for such elongated sequences, and their traditional construction and traversal algorithms result in random disk accesses. We investigate, in this thesis, post-construction techniques for disk-based suffix-tree storage optimization, with the objective of maximizing disk-reference locality during query processing. Specifically, we consider approaches based on (a) reorganizing the layouts, and (b) improving the physical structures of internal nodes of disk-resident suffix-trees. In marked contrast to prior techniques in the literature that modify the suffix-tree itself in order to gain performance (for example, by dropping the suffix-link edges), an important aspect of our work is that the logical structure is retained in pristine form, thereby retaining all the standard functionalities associated with these trees. We begin by focusing on the layout reorganization, in which (i) complete reworking of node-to-block assignments, and (ii) resequencing of storage blocks, are carried out. While the classical suffix-tree construction algorithms deliver a depth-first layout, our node-to-