用于构建大型BWTs的递归前免费解析
Marco Oliva1, Travis Gagie2, Christina Boucher1
1Department of Computer and Information Science and Engineering, Herbert Wertheim College of Engineering, University of Florida, Gainesville, FL, USA.
概括
递归无前解析显著减少了用于构建BWT的内存. 这种方法通过高效地解析和压缩数据结构来优化大型,重复的数据集.
科学领域:
- 计算机科学 计算机科学
- 数据压缩数据压缩
- 字符串算法 字符串算法
背景情况:
- 无前解析对于像BWT (Burrows-Wheeler Transform),后数组和压缩后树这样的数据结构至关重要.
- 现有的方法面临着解析大小的挑战,这对于大,重复的输入来说变得繁重.
研究的目的:
- 引入和实施一种新的算法,即递归前免费解析,以解决解析大小的可扩展性.
- 为了提高构建运行长度编码BWT的内存效率.
主要方法:
- 开发了无前解析的递归方法,将其应用于初始解析步骤生成的解析.
- 从解析的解析和相关字典中解决了构建BWT的复杂性.
主要成果:
- 递归无前解析有效地减少了构建运行长度编码BWT的内存需求.
- 实验结果验证了新算法实现的显著内存节省.
结论:
- 递归无前解析为在字符串算法应用中处理大,重复的数据集提供了可扩展的解决方案.
- 实施的开源解决方案为存储效率高的BWT构建提供了实用工具.
相关概念视频
¹H NMR: Complex Splitting
1.3K
A proton M that is coupled to a proton X results in doublet signals for M. However, NMR-active nuclei can be simultaneously coupled to more than one nonequivalent nucleus. When M is coupled to a second proton A, such as in styrene oxide, each peak in the doublet is split into another doublet.
Splitting diagrams or splitting tree diagrams are routinely used to depict such complex couplings. While drawing splitting diagrams, the splitting with the larger coupling constant is usually applied...
Splitting diagrams or splitting tree diagrams are routinely used to depict such complex couplings. While drawing splitting diagrams, the splitting with the larger coupling constant is usually applied...
1.3K
Radical Substitution: Allylic Bromination
5.0K
In organic synthesis, the formation of products can be altered by changing the reaction conditions. For example, a dibromo addition product is formed when propene is treated with bromine at room temperature. In contrast, propene undergoes allylic substitution in non-polar solvents at high temperatures to give 3-bromopropene. In order to avoid the addition reaction, the bromine concentration must be kept as low as possible throughout the reaction. This can be achieved using N-bromosuccinimide...
5.0K
Parseval's Theorem
473
Parseval's theorem is a fundamental concept in signal processing and harmonic analysis. It asserts that for a periodic function, the average power of the signal over one period equals the sum of the squared magnitudes of all its complex Fourier coefficients. This theorem, named after Marc-Antoine Parseval, provides a powerful tool for analyzing the energy distribution in signals.
Interestingly, Parseval's theorem also holds for the trigonometric form of the Fourier series, which...
Interestingly, Parseval's theorem also holds for the trigonometric form of the Fourier series, which...
473
Radical Chain-Growth Polymerization: Chain Branching
1.9K
The skeletal structure of polymers synthesized via radical polymerization is always branched. For example, the polymerization of ethylene by radical polymerization results in a low-density grade of polyethylene with a heavily branched skeletal structure. Here, the radical site abstracts hydrogen from the growing chain, and the radical site shifts from the end (a primary carbon center) to anywhere within the growing chain (a secondary carbon center). Consequently, the part of the chain from the...
1.9K
pre-mRNA Processing
52.8K
In eukaryotic cells, transcripts made by RNA polymerase are modified and processed before exiting the nucleus. Unprocessed RNA is called precursor mRNA or pre-mRNA to distinguish it from mature mRNA.
Once about 20-40 ribonucleotides have been joined together by RNA polymerase, a group of enzymes adds a “cap” to the 5’ end of the growing transcript. In this process, a 5’ phosphate is replaced by modified guanosine that has a methyl group attached to it (7-Methyl...
Once about 20-40 ribonucleotides have been joined together by RNA polymerase, a group of enzymes adds a “cap” to the 5’ end of the growing transcript. In this process, a 5’ phosphate is replaced by modified guanosine that has a methyl group attached to it (7-Methyl...
52.8K


