Academic Journals Database
Disseminating quality controlled scientific knowledge

Practical Compressed Suffix Trees

ADD TO MY LIST
 
Author(s): Andrés Abeliuk | Rodrigo Cánovas | Gonzalo Navarro

Journal: Algorithms
ISSN 1999-4893

Volume: 6;
Issue: 2;
Start page: 319;
Date: 2013;
Original page

Keywords: suffix trees | compressed data structures | repetitive sequence collections | bioinformatics

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.

Tango Rapperswil
Tango Rapperswil

    
RPA Switzerland

RPA Switzerland

Robotic process automation