BuST-Bundled Suffix Trees
Posted by luca | On Saturday, 10 August 2013
Title | BuST-Bundled Suffix Trees |
Publication Type | Conference Paper |
Year of Publication | 2006 |
Authors | Bortolussi L, Fabris F, Policriti A |
Editor | Navarro G, Bertossi L, Kohayakawa Y |
Conference Name | IFIP conference on Theoretical Computer Science, IFIP-TCS 2006 |
Volume | 209 |
Pages | 91–102 |
Date Published | 24 Agosto 2006 |
Publisher | Springer Verlag |
Keywords | Algorithms for approximate string matching, bioinformatics, data structures, Suffix Trees |
Abstract | 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. |
URL | http://www.springerlink.com/content/c36x8230n44516u5/ |
DOI | 10.1007/978-0-387-34735-6_11 |