Efficiently Merging r-indexes
Efficiently Merging r-indexes
复制标题
高效合并 r 索引
DOI：
10.1109/dcc50243.2021.00028
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Boucher, Christina
中科院分区：
文献类型：
--
作者：
Oliva, Marco;Rossi, Massimiliano;Siren, Jouni;Manzini, Giovanni;Kahveci, Tamer;Gagie, Travis;Boucher, Christina
大型测序项目，如GenomeTrakr和MetaSub，经常更新新数据（有时每天更新，就GenomeTrakr而言）。因此，对这些数据进行索引的任何数据结构都必须支持有效的更新。为了实现这一目标，Bannai等人（TCS，2020）提出了一种名为动态r-index的数据结构，它适用于大型基因组集合并支持增量构建;然而，它仍然不够强大，无法支持实质性更新。在这里，我们开发了一种新的算法来更新r-索引，我们称之为RIMERGE。我们的算法的基础是结合的基础知识的动态r指数与一个已知的算法合并Burrows-Wheeler变换（BWT）。因此，RIMERGE能够以利用并行性的方式执行批量更新，同时保持较小的内存开销。我们使用两个不同的数据集将我们的方法与Bannai等人的动态r指数进行了比较，并表明RIMERGE在合理的大输入上快1.88到5.34倍。
Large sequencing projects, such as GenomeTrakr and MetaSub, are updated frequently (sometimes daily, in the case of GenomeTrakr) with new data. Therefore, it is imperative that any data structure indexing such data supports efficient updates. Toward this goal, Bannai et al. (TCS, 2020) proposed a data structure named dynamic r-index which is suitable for large genome collections and supports incremental construction; however, it is still not powerful enough to support substantial updates. Here, we develop a novel algorithm for updating the r-index, which we refer to as RIMERGE. Fundamental to our algorithm is the combination of the basics of the dynamic r-index with a known algorithm for merging Burrows-Wheeler Transforms (BWTs). As a result, RIMERGE is capable of performing batch updates in a manner that exploits parallelism while keeping the memory overhead small. We compare our method to the dynamic r-index of Bannai et al. using two different datasets, and show that RIMERGE is between 1.88 to 5.34 times faster on reasonably large inputs.
登录
查看更多内容
影响因子：
48
作者：
Langmead, Ben;Salzberg, Steven L.
通讯作者：
Salzberg, Steven L.
影响因子：
7
作者：
Li, Ruiqiang;Zhu, Hongmei;Wang, Jun
通讯作者：
Wang, Jun
基于游程编码的简洁后缀数组
DOI：
--
发表时间：
2005
期刊：
Nordic Journal of Computing
影响因子：
--
作者：
V. Mäkinen;G. Navarro
通讯作者：
G. Navarro
通过 Burrows-Wheeler 变换对 LCP 阵列进行空间高效计算
DOI：
--
发表时间：
2019
期刊：
Annual Symposium on Combinatorial Pattern Matching
影响因子：
--
作者：
N. Prezza;Giovanna Rosone
通讯作者：
Giovanna Rosone
影响因子：
1
作者：
Boucher, Christina;Gagie, Travis;Mun, Taher
通讯作者：
Mun, Taher