BuST-Bundled Suffix Trees

TitleBuST-Bundled Suffix Trees
Publication TypeConference Paper
Year of Publication2006
AuthorsBortolussi L, Fabris F, Policriti A
EditorNavarro G, Bertossi L, Kohayakawa Y
Conference NameIFIP conference on Theoretical Computer Science, IFIP-TCS 2006
Date Published24 Agosto 2006
PublisherSpringer Verlag
KeywordsAlgorithms for approximate string matching, bioinformatics, data structures, Suffix Trees

We introduce a data structure, the Bundled Suffix Tree (BUST), that is a generalization of a Suffix Tree (ST). To build a BuST we use an alphabet Sigma together with a non-transitive relation R among its letters. Following the path of a substring p within a BUST, constructed over a text t of length n, not only the positions of the exact occurrences of p in t are found (as in a ST), but also the positions of all the substrings p1, p2, p3, ... that are related with p via the relation R among the characters of Sigma, for example strings at a certain distance from p. A BuST contains O(n^(1+m)) additional nodes (m < 1) in probability, and is constructed in O(n^(1+m)) steps. In the worst case it contains O(n^2) nodes.