R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space
R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space
复制标题
R-enum：BWT 运行有界空间中特征子串的枚举
DOI：
10.4230/lipics.cpm.2021.21
复制
发表时间：
2021
影响因子：
0.5
通讯作者：
Yasuo Tabei
中科院分区：
文献类型：
--
作者：
Takaaki Nishimoto;Yasuo Tabei
枚举特征子串（例如，最大重复、最小唯一子串和最小缺失字）已经成为重要的研究课题，因为在诸如串处理和计算生物学的各种领域中存在各种各样的应用。虽然已经提出了几种特征子串的枚举算法，但它们的空间使用率与输入串的长度成正比，因此它们不是空间有效的。最近，游程编码Burrows-Wheeler变换（RLBWT）在字符串处理中引起了越来越多的关注，并且已经开发了各种RLBWT算法。然而，使用RLBWT开发特征子串的枚举算法仍然是一个挑战。本文提出了第一个基于RLBWT的特征子串枚举算法r-enum（RLBWT-based enumeration）。对于RLBWT中的字符串长度n和运行次数r，R-enum运行时间为O（n log log（n/r）），工作空间为O（r log n）位。这里，对于高度重复的串，r预期显著小于n（即，重复多次的字符串）。使用高度重复字符串的基准数据集的实验表明，r-enum的结果比以前的结果更节省空间。此外，我们证明了r-enum的适用性，以一个巨大的字符串进行实验的300千兆字节的字符串的100个人类基因组。
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.