在压缩空间中基于RLBWT的LCP计算,用于特拉基基规模的泛基组分析
bioRxiv : the preprint server for biology
|February 6, 2026
概括
我们开发了新的算法来构建使用运行长度Burrows-Wheeler变换 (RLBWT) 的压缩全文索引. 这些方法显著减少了大型生物数据集的内存使用量,使复杂的分析更加可行.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 数据压缩数据压缩
背景情况:
- 无损全文索引对于生物信息学应用至关重要.
- 越来越多的生物数据需要对大型数据集进行有效的索引.
- 现有的运行长度Burrows-Wheeler转换 (RLBWT) 索引在计算上是昂贵的.
研究的目的:
- 介绍构建基于RLBWT的压缩全文索引和支持压缩空间中的数据结构的算法.
- 为了降低构建这些索引的计算成本和内存需求.
主要方法:
- 开发了对重复数据集的O (r) 空间复杂度和O (n) 时间的算法.
- 介绍了第一个算法,以O (r) 空间和最佳时间计算LCP相关信息.
- 定期使用反向后数组的r样本.
主要成果:
- 在重复的数据集上构建RLBWT索引的空间达到了0和n时间.
- 在人类泛基因组参考联盟发布2数据集 (从2,135 GiB降至170 GiB) 上,峰值内存使用量减少了12.6倍.
- 为LCP相关信息提供了第一个最佳时间和O (r) 空间算法.
结论:
- 新的算法为构建压缩的全文索引提供了显著的内存减少.
- 这些进步解决了索引大型生物数据集的计算挑战.
- 实施方案是公开的,这有助于在生物信息学研究中更广泛地采用.
相关概念视频
pH Scale
80.0K
Hydronium and hydroxide ions are present both in pure water and in all aqueous solutions, and their concentrations are inversely proportional as determined by the ion product of water (Kw). The concentrations of these ions in a solution are often critical determinants of the solution’s properties and the chemical behaviors of its other solutes. Two different solutions can differ in their hydronium or hydroxide ion concentrations by a million, billion, or even trillion times. A common means of...
80.0K
Space Trusses
1.3K
A space truss is a three-dimensional counterpart of a planar truss. These structures consist of members connected at their ends, often utilizing ball-and-socket joints to create a stable and versatile framework. The space truss is widely used in various construction projects due to its adaptability and capacity to withstand complex loads.
At the core of a space truss lies the fundamental unit known as the tetrahedron. This structure is composed of six members that form a three-dimensional shape...
At the core of a space truss lies the fundamental unit known as the tetrahedron. This structure is composed of six members that form a three-dimensional shape...
1.3K
State Space Representation
590
The frequency-domain technique, commonly used in analyzing and designing feedback control systems, is effective for linear, time-invariant systems. However, it falls short when dealing with nonlinear, time-varying, and multiple-input multiple-output systems. The time-domain or state-space approach addresses these limitations by utilizing state variables to construct simultaneous, first-order differential equations, known as state equations, for an nth-order system.
Consider an RLC circuit, a...
Consider an RLC circuit, a...
590
Scaling
596
In designing and analyzing filters, resonant circuits, or circuit analysis at large, working with standard element values like 1 ohm, 1 henry, or 1 farad can be convenient before scaling these values to more realistic figures. This approach is widely utilized by not employing realistic element values in numerous examples and problems; it simplifies mastering circuit analysis through convenient component values. The complexity of calculations is thereby reduced, with the understanding that...
596
Space Trusses: Problem Solving
913
A space truss is a three-dimensional counterpart of a planar truss. These structures consist of members connected at their ends, often utilizing ball-and-socket joints to create a stable and versatile framework. Due to its adaptability and capacity to withstand complex loads, the space truss is widely used in various construction projects.
Consider a tripod consisting of a tetrahedral space truss with a ball-and-socket joint at C. Suppose the height and lengths of the horizontal and vertical...
Consider a tripod consisting of a tetrahedral space truss with a ball-and-socket joint at C. Suppose the height and lengths of the horizontal and vertical...
913
Transfer Function to State Space
808
State-space representation is a powerful tool for simulating physical systems on digital computers, necessitating the conversion of the transfer function into state-space form. Consider an nth-order linear differential equation with constant coefficients, like those encountered in an RLC circuit. The state variables are selected as the output and its n−1 derivatives. Differentiating these variables and substituting them back into the original equation produces the state equations.
In an RLC...
In an RLC...
808


