Name
Abstract | ||
|---|---|---|
We describe succinct and compact representations of the bidirectional BWT of a string s is an element of Sigma* which provide increasing navigation power and a number of space-time tradeoffs. One such representation allows to extend a substring of s by one character from the left and from the right in constant time, taking O(vertical bar s vertical bar log vertical bar Sigma vertical bar) bits of space. We then match the functions supported by each representation to a number of algorithms that traverse the nodes of the suffix tree of s, exploiting connections between the BWT and the suffix-link tree. This results in near-linear time algorithms for many sequence analysis problems (e. g. maximal unique matches), for the first time in succinct space. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40450-4_12 | ALGORITHMS - ESA 2013 |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Substring,Burrows–Wheeler transform,Computer science,Wavelet Tree,Bidirectional search,Suffix tree,Traverse | Conference | 8125 |
ISSN | Citations | PageRank |
0302-9743 | 19 | 0.70 |
References | Authors | |
27 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Djamal Belazzougui | 1 | 437 | 32.23 |
| Fabio Cunial | 2 | 72 | 9.68 |
| Juha Kärkkäinen | 3 | 1354 | 95.20 |
| Veli Mäkinen | 4 | 1583 | 85.29 |