计算原始eBWT的速度更快,更简单,并且使用更少的内存
Christina Boucher1, Davide Cenzato2, Zsuzsanna Lipták2
1Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, United States.
概括
这项研究引入了一个新的线性时间算法,用于扩展的Burrows-Wheeler转换 (eBWT),这对于基因组序列分析至关重要. 这种新的方法pfpebwt显著加快了对大型基因组集合的eBWT的构建速度,提高了效率和内存使用率.
科学领域:
- 生物信息学是一种生物信息学.
- 计算生物学 计算生物学
- 字符串算法 字符串算法
背景情况:
- 布劳斯-惠勒转换 (BWT) 对于基因组数据分析至关重要,使压缩和子字符串查询成为可能.
- 扩展的Burrows-Wheeler转换 (eBWT) 被定义为处理字符串的集合,保持顺序独立性.
- 现有的eBWT方法往往忽视了原来的独立顺序属性,需要改进的算法.
研究的目的:
- 介绍一个新的线性时间算法,用于构建原始扩展的Burrows-Wheeler转换 (eBWT).
- 开发一种有效的方法来计算单个字符串的BWT,而无需特殊符号或林登旋转.
- 通过将新的eBWT算法与无前解析 (PFP) 结合起来,使eBWT能够在大型基因组序列集合上构建.
主要方法:
- 一个新的线性时间算法用于原始的eBWT构建,避免预处理步骤.
- 一个线性时间算法用于单字符串BWT计算,省略字符串末尾符号和林登旋转.
- 集成eBWT算法与前免费解析 (PFP) 变异用于大规模基因组数据.
主要成果:
- 开发的算法 (pfpebwt) 在大型基因组集合上实现了eBWT最快的构建时间,速度可达7.6倍.
- pfpebwt的峰值内存使用率最多是第二个最佳方法的2倍.
- 与报告后数组样本的方法相比,pfpebwt在峰值记忆中提供了57.1倍的改进.
结论:
- 新的eBWT构建算法对于分析大型基因组数据集是高效和实用的.
- 在基因组序列分析任务中,pfpebwt在速度和内存效率方面取得了显著的进步.
- 公开可用的源代码有助于进一步研究和应用这些改进的BWT算法.
相关概念视频
Fast Fourier Transform
310
The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
The computational efficiency of the FFT becomes...
310
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
51
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
51


