An incrementally updatable and scalable system for large-scale sequence search using the Bentley–Saxe transformation
An incrementally updatable and scalable system for large-scale sequence search using the Bentley–Saxe transformation
复制标题
使用 Bentley Saxe 变换进行大规模序列搜索的增量更新和可扩展系统
DOI：
10.1093/bioinformatics/btac142
复制
发表时间：
2022
期刊：
影响因子：
5.8
通讯作者：
Boeva, ed., Valentina
中科院分区：
文献类型：
--
作者：
Almodaresi, Fatemeh;Khan, Jamshed;Madaminov, Sergey;Ferdman, Michael;Johnson, Rob;Pandey, Prashant;Patro, Rob;Boeva, ed., Valentina
在过去的几年里，研究人员提出了许多索引方案，用于搜索原始测序实验的大数据集。这些建议的指数大多是近似的（即有单侧误差），以节省空间。最近，研究人员已经发布了确切的索引Mantis，VariMerge和Bifrost，它们除了提供ask-mer索引外，还可以作为彩色de Bruijn图表示。这种新型的索引很有前途，因为它有可能支持比简单搜索更复杂的分析。然而，为了成为有用的索引为大型和不断增长的原始测序数据库，他们必须扩展到数千个实验，并支持有效的插入新data.ResultsIn本文中，我们展示了如何建立一个可扩展和可更新的准确的原始序列搜索索引。具体来说，我们使用Bentley-Saxe转换来扩展Mantis，以支持高效的更新，称为Dynamic Mantis。我们证明了动态螳螂的可扩展性，通过构建一个索引ofK样本从SRA添加样本一次10 K样本的初始索引。与VariMerge和Bifrost相比，Dynamic Mantis在索引构建时间和内存，查询时间和内存以及索引大小方面更有效。在我们的基准测试中，VariMerge和Bifrost分别仅扩展到5 K和80个样本，而Dynamic Mantis扩展到超过39 K个样本。Mantis中的搜索比Bifrost中的搜索快得多（VariMerge不能立即支持我们需要的一般搜索查询）。Dynamic Mantis索引大约比Bifrost的索引小，大约是VariMerge索引的一半。可用性和实现Dynamic Mantis实现可在https://github.com/splatlab/mantis/tree/mergeMSTs.Supplementary信息中获得补充数据可在Bioinformatics在线获得。
MotivationIn the past few years, researchers have proposed numerous indexing schemes for searching large datasets of raw sequencing experiments. Most of these proposed indexes are approximate (i.e. with one-sided errors) in order to save space. Recently, researchers have published exact indexes—Mantis, VariMerge and Bifrost—that can serve as colored de Bruijn graph representations in addition to serving ask-mer indexes. This new type of index is promising because it has the potential to support more complex analyses than simple searches. However, in order to be useful as indexes for large and growing repositories of raw sequencing data, they must scale to thousands of experiments and support efficient insertion of new data.ResultsIn this paper, we show how to build a scalable and updatable exact raw sequence-search index. Specifically, we extend Mantis using the Bentley–Saxe transformation to support efficient updates, called Dynamic Mantis. We demonstrate Dynamic Mantis’s scalability by constructing an index ofK samples from SRA by adding samples one at a time to an initial index of 10K samples. Compared to VariMerge and Bifrost, Dynamic Mantis is more efficient in terms of index-construction time and memory, query time and memory and index size. In our benchmarks, VariMerge and Bifrost scaled to only 5K and 80 samples, respectively, while Dynamic Mantis scaled to more than 39K samples. Queries were overfaster in Mantis than in Bifrost (VariMerge does not immediately support general search queries we require). Dynamic Mantis indexes were aboutsmaller than Bifrost’s indexes and about half as big as VariMerge’s indexes.Availability and implementationDynamic Mantis implementation is available at https://github.com/splatlab/mantis/tree/mergeMSTs.Supplementary informationSupplementary data are available atBioinformaticsonline.