Department of Computer Science, Johns Hopkins University, Baltimore, Maryland 21218, USA;
Department of Computer and Information Science and Engineering, Herbert Wertheim College of Engineering, University of Florida, Gainesville, Florida 32611, USA.
Genome Res. 2023 Jul;33(7):1069-1077. doi: 10.1101/gr.277642.123. Epub 2023 May 31.
Tools that classify sequencing reads against a database of reference sequences require efficient index data-structures. The -index is a compressed full-text index that answers substring presence/absence, count, and locate queries in space proportional to the amount of distinct sequence in the database: [Formula: see text] space, where is the number of Burrows-Wheeler runs. To date, the -index has lacked the ability to quickly classify matches according to which reference sequences (or sequence groupings, i.e., taxa) a match overlaps. We present new algorithms and methods for solving this problem. Specifically, given a collection D of documents, [Formula: see text] over an alphabet of size σ, we extend the -index with [Formula: see text] additional words to support document listing queries for a pattern [Formula: see text] that occurs in [Formula: see text] documents in D in [Formula: see text] time and [Formula: see text] space, where is the machine word size. Applied in a bacterial mock community experiment, our method is up to three times faster than a comparable method that uses the standard -index locate queries. We show that our method classifies both simulated and real nanopore reads at the strain level with higher accuracy compared with other approaches. Finally, we present strategies for compacting this structure in applications in which read lengths or match lengths can be bounded.
用于将测序reads 与参考序列数据库进行分类的工具需要高效的索引数据结构。-index 是一种压缩的全文索引，可以在与数据库中不同序列数量成比例的空间中回答子串存在/不存在、计数和定位查询：[公式：见正文]空间，其中 是 Burrows-Wheeler 运行的数量。到目前为止，-index 缺乏根据匹配所重叠的参考序列（或序列分组，即分类群）快速分类匹配的能力。我们提出了新的算法和方法来解决这个问题。具体来说，给定一个由 文档组成的集合 D，[公式：见正文]在大小为 σ 的字母表上，我们通过 [公式：见正文]个额外的单词扩展 -index，以支持针对在 D 中的 [公式：见正文]个文档中出现的模式 [公式：见正文]的文档列表查询，查询时间为 [公式：见正文]，空间复杂度为 [公式：见正文]，其中 是机器字长。在细菌模拟群落实验中应用时，我们的方法比使用标准 -index 定位查询的可比方法快三倍。我们表明，与其他方法相比，我们的方法在分类模拟和真实的纳米孔读取时具有更高的精度。最后，我们提出了在可以限制读取长度或匹配长度的应用程序中压缩此结构的策略。
