TRELLIS+: an effective approach for indexing genome-scale sequences using suffix trees.
With advances in high-throughput sequencing methods, and the corresponding exponential growth in sequence data, it has become critical to develop scalable data management techniques for sequence storage, retrieval and analysis. In this paper we present a novel disk-based suffix tree approach, called TRELLIS+, that effectively scales to massive amount of sequence data using only a limited amount of main-memory, based on a novel string buffering strategy. We show experimentally that TRELLIS+ outperforms existing suffix tree approaches; it is able to index genome-scale sequences (e.g., the entire Human genome), and it also allows rapid query processing over the disk-based index.


BACKGROUND
TRELLIS+ source code is available online at http://www.cs.rpi.edu/-zaki/software/trellis
Phoophakdee
Benjarath
B
Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. phoopb@cs.rpi.edu
Zaki
Mohammed J
MJ
D000043:Abstracting and Indexing; D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D003628:Database Management Systems; D015894:Genome, Human; D023281:Genomics / Q000706:statistics & numerical data*; D006801:Humans; D017421:Sequence Analysis / Q000706:statistics & numerical data; D012984:Software