2026-07-24T08:33:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18354 2024-03-06T11:01:35Z ddc:004 open_access

Subset Wavelet Trees Alanko, Jarno N. Biagi, Elena Puglisi, Simon J. Vuohtoniemi, Jaakko degenerate strings compressed data structures succinct data structures string processing data structures efficient algorithms Given an alphabet Σ of σ = |Σ| symbols, a degenerate (or indeterminate) string X is a sequence X = X[0],X[1]…, X[n-1] of n subsets of Σ. Since their introduction in the mid 70s, degenerate strings have been widely studied, with applications driven by their being a natural model for sequences in which there is a degree of uncertainty about the precise symbol at a given position, such as those arising in genomics and proteomics. In this paper we introduce a new data structural tool for degenerate strings, called the subset wavelet tree (SubsetWT). A SubsetWT supports two basic operations on degenerate strings: subset-rank(i,c), which returns the number of subsets up to the i-th subset in the degenerate string that contain the symbol c; and subset-select(i,c), which returns the index in the degenerate string of the i-th subset that contains symbol c. These queries are analogs of rank and select queries that have been widely studied for ordinary strings. Via experiments in a real genomics application in which degenerate strings are fundamental, we show that subset wavelet trees are practical data structures, and in particular offer an attractive space-time tradeoff. Along the way we investigate data structures for supporting (normal) rank queries on base-4 and base-3 sequences, which may be of independent interest. Our C++ implementations of the data structures are available at https://github.com/jnalanko/SubsetWT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jarno N. Alanko and Elena Biagi and Simon J. Puglisi and Jaakko Vuohtoniemi 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.4 urn:nbn:de:0030-drops-183549 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.4 eng https://creativecommons.org/licenses/by/4.0/legalcode