Practical Compressed Suffix Trees
Open Access
- 21 May 2013
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 6 (2) , 319-351
Abstract
The suffix tree is an extremely important data structure in bioinformatics. Classical implementations require much space, which renders them useless to handle large sequence collections. Recent research has obtained various compressed representations for suffix trees, with widely different space-time tradeoffs. In this paper we show how the use of range min-max trees yields novel representations achieving practical space/time tradeoffs. In addition, we show how those trees can be modified to index highly repetitive collections, obtaining the first compressed suffix tree representation that effectively adapts to that scenario.Keywords
This publication has 38 references indexed in Scilit:
- Fully compressed suffix treesACM Transactions on Algorithms, 2011
- Compressed representations of sequences and full-text indexesACM Transactions on Algorithms, 2007
- Compressed Suffix Trees with Full FunctionalityTheory of Computing Systems, 2007
- Replacing suffix trees with enhanced suffix arraysJournal of Discrete Algorithms, 2004
- New text indexing functionalities of the compressed suffix arraysJournal of Algorithms, 2003
- Space Efficient Suffix TreesJournal of Algorithms, 2001
- An analysis of the Burrows—Wheeler transformJournal of the ACM, 2001
- Reducing the space requirement of suffix treesSoftware: Practice and Experience, 1999
- Suffix Arrays: A New Method for On-Line String SearchesSIAM Journal on Computing, 1993
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976