2026-07-23T22:07:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13972 2024-03-06T10:53:02Z ddc:004 open_access

R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space Nishimoto, Takaaki Tabei, Yasuo Enumeration algorithm Burrows-Wheeler transform Maximal repeats Minimal unique substrings Minimal absent words Enumerating characteristic substrings (e.g., maximal repeats, minimal unique substrings, and minimal absent words) in a given string has been an important research topic because there are a wide variety of applications in various areas such as string processing and computational biology. Although several enumeration algorithms for characteristic substrings have been proposed, they are not space-efficient in that their space-usage is proportional to the length of an input string. Recently, the run-length encoded Burrows-Wheeler transform (RLBWT) has attracted increased attention in string processing, and various algorithms for the RLBWT have been developed. Developing enumeration algorithms for characteristic substrings with the RLBWT, however, remains a challenge. In this paper, we present r-enum (RLBWT-based enumeration), the first enumeration algorithm for characteristic substrings based on RLBWT. R-enum runs in O(n log log (n/r)) time and with O(r log n) bits of working space for string length n and number r of runs in RLBWT. Here, r is expected to be significantly smaller than n for highly repetitive strings (i.e., strings with many repetitions). Experiments using a benchmark dataset of highly repetitive strings show that the results of r-enum are more space-efficient than the previous results. In addition, we demonstrate the applicability of r-enum to a huge string by performing experiments on a 300-gigabyte string of 100 human genomes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takaaki Nishimoto and Yasuo Tabei 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.21 urn:nbn:de:0030-drops-139723 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.21 eng https://creativecommons.org/licenses/by/4.0/legalcode